2018/1 solved(2)
1/17
水の量と砂糖の量を全探索する。砂糖の量は、bool配列などにその量が作れるかを持っておけば計算量的にOK(submission)。
Warshall-Floyd法によって、最短距離を計算して、入力と一致するかをチェックする。一致すれば、それは入力として妥当なものであり、あとは各頂点対の間に本当に道があるのかを判定する必要があるが、Warshall-Floyd法の更新と同じ要領で、他の頂点を経由してその最短距離を実現できるかを判断材料にすると良い(submission)。
dp[i][j] := 頂点iを色j(黒or白)で塗る時のもう片方の色の重みの最小値を計算する。最初は、もう片方の重みがkの時、到達可能かを持とうとしたが、間に合わない。でも、できるだけ小さくしとけば今注目している頂点でいくらでも調整が効くので、最小値だけで良いということに気づく(submission)。
1/18
1/19
UF + 並列二分探索。ある距離以上の頂点同士を結ぶグラフを考え、その頂点のみを使って移動可能かどうかは、UFで判定できる。それを一辺に二分探索するために並列二分探索にする(submission)。
1/20
COLOCON -Colopl programming contest 2018- Finalに参加
ABCDの4完。Cに時間かかりすぎ。ConvexHullTrickよく分かってなかった(反省)。
1/21
1/22
setで約数の位置に各値を入れて管理しておくと、次に入るべき値が何になるかは、最後に入れた値の約数ごとに最小値を取っていって(同じ約数を持っている中では小さいものを取ったほうが得なので)、LCMが小さくなるものをとれば良い(submission)。
1/23
CF #451(Div.2) Virtual
ABCDEの5完、Fもあらかたの方針は立ってたけどPythonで突っ込んだのはアホだった(入力サイズがなので)。
1/24
aとbの桁数が多い方とcの桁数は同じor1だけ大きいという関係から、+と=の位置の組み合わせの候補は通りになる。後はそれぞれの場合について、a+b=cが成り立つかをチェックする必要があるが、pythonだとTLEした(参考)(まあ
だしなあ...)。10をbaseにしたローリングハッシュをつかうことによって、この判定を高速にできるようになる(submission)。
頂点をprince、辺をprincessに対応させたグラフを考えると、連結成分(頂点数)に対して、辺は
本までしかはることが出来ないことが分かる(princeとprincessを対応させるので、それはそうで、
本はってあるときには対応のさせ方がちゃんとある)。なのでUnionFindをつかったKruskal法を少し工夫して、UnionFind内で、1回だけ同じグループ内で辺を繋ぐことを許す(実装だと
namoriというフラグでUF内に実装してある)ことにしたMSTみたいなことをやる(submission)。
1/25
1/26
とりあえず最低限必要な量を埋めて、後は容量の多い方から貪欲に入れていく(submission)。
要素を取ったら右にしか動かせないことにする(反転した数列に対しても反転すればこれは問題の条件を損ねない)。すると、番目を動かすことにしたら、その後挿入する位置が分割地点にならないと動かした意味が無いのでそこが分割地点になると考えると、
番目の要素を含んでいるprefix sumの中から、その要素を引いたものがちょうど半分になるものを見つけるという問題になり、setで管理すれば良い(submission)。
1/27
1/28
1/29
1/30
下の位から払う額を決めていく桁dpをする(submission)。
CF #455(Div.2) Virtual
ABCDEの5完。DもEも厳密には分かってなかったけど、気持ちを実装したら通った。
1/31
筆算の要領で割り続けていき、循環したら打ち切れば良い(今回は十分な回数のloopを取った)(submission)。
番目の要素を取り除いた時にどうなるかを順番に走査しながら最大値を更新していく。この時必要になるのが、左側の値の最大値
とその時のレコード数、右側については
以上の値で最も近いものとその時のレコード数である。左側については貪欲に更新しておけばよく、右側はindexをsegtreeで管理すると見つけることが出来る(submission)。
