ネタバレ込み
60分のバチャでまさかのABCのみ。ひどすぎた。
全体的にスマートさに欠ける実装が多く、「機械を信用して適切にサボる」力をもっと身につけた方がいいな、となった。
A
地味に2分とかかかってるけどいいのか？
B
地味に9分かかってるなぁ。
「たとえば11月なら1か11があるよね」みたいに月毎に判定したけど、それが面倒だったか。
日付を全列挙してゾロ目かどうか判定した方が速かったなぁ。
C
地味に8分かかってるなぁ。
累積和なのはいいとして、添え字で微妙に悩んでてよくない。
さびとる。
D
バグがとれませんでした。は？？？
シミュレーションで解けるのはいいとして、処理にstack2個使ったのは良くなかった。
「文字をstackに追加していって、ABCができたら2つpushし、さらに後ろ2つを戻す」という作戦にしたが、後ろ2つを戻すを真面目にやろうとして入力用のstackも用意したのだが、それがバグを生んでしまった。
「文字を1個ずつ入れるとき、ABCの除去は高々1回」というのは気づいていたが、それなら解説のようなスマートな書き方もできたなぁ。
あとはバグについて。2つ戻すときにrep(i, min(2, size(stack)))のようなコードを書いていたが、repの中身でstackをいじっていてsizeが変わってしまっていておかしな挙動になった。正確にはmin(2,size(stack))をrepの前に取っておかないといけなかった。
気づきづらいバグな気もするので書くときに注意するということと、発見のきっかけはテストを投げまくったことだったので、バグの箇所がわからなかったらテストを投げまくる、というのを忘れないようにしよう。
E
バチャ後失意のAC.
modをとったminなので普通のmstアルゴリズムは効かないが、今回はサイズが小さいのでmst全列挙ができそうとなる。
実際、辺の取り方_M C_{N-1} 通りが十分小さいので、それぞれについてtreeかどうか判定し、treeならcost modを計算して更新するとよい。
F
数列のindexを頂点とするグラフに順に辺を引いていくイメージ。
頂点にはエネルギーXが定まっていて、それと整合性のある辺 (コストとエネルギー差が一致するもの) のみ引ける。
連結成分でないものも結ぶことができるが、ナイーブにやるといちいちエネルギーを更新しないといけなくてO(N^2)とかかかる。そこをどうするか。
実はコストが無ければただのUnion-Find. ということでコストを管理した変形Union-Findで解ける。
Union-Findの構成で、親の頂点の他に、親まで至る時のコストも管理する。
また親を経路変更して更新する際に、関わるコストも変更するようにする。
参考実装：https://atcoder.jp/contests/atc001/tasks/unionfind_a
これを元に改変。おそらく1操作O(logN)かかる雑な実装だったが、十分高速だった。
ユーザー解説が賢かった。別にもう一回クエリ見ればいいじゃんね作戦。そっちの方がスマートだった。
G
解けずに解説open
考えたこととしては、切れ目をfixして判定できないかとか、全部切れ目入れた場合はソートで最小値の計算ができるなとか。
ただ切れ目fix作戦は、その後のコスト最小値を求めるパートがしんどかった。
順列を決めれば切れ目のコストは後で計算できる、というところで、そこからbitDPに行くというのが模範解答。困ったらDPだなぁ。
変に実装するとO(N^2*2^N)かかりそうなので怪しいが、また後日考えることにする。。。
