CF #500

大失敗。

記念すべき500回目らしい
出ちゃうか
6問

C読む
うーん
とりあえずAに行く

A:
Aにしてはむずくない?
AGCのyosupo回でみた
mxとmnが同じ側なら幅N最小で違う側なら半分ずつだな

B:
できる限り操作をすると長方形いくつかになる
これを得れば答えもすぐわかりそう
(x,y) と (x,y') に辺を生やせば
冷静に考えると x-y で辺を生やせばいいな
答えは連結成分-1

C:
取るべき値は少ないので現在の値を持ってDP?
ちょっと面倒そう
選ぶやつを固定すると、適切な位置でコストを発生させれば (何個選んだか, 直前選んだか, 2狛江選んだか) でやれるな
TLE
は?
内側でK * 3 の vectorを毎回宣言してたのを外側にしたらTLEが取れた
5000 * 2500 * 3 でこんなに遅いのか・・・

順位絶望だったが順位表見てもD以降全然解かれてなくてたまげる
とりあえずD読む
D:
はえー
とりあえず手でいろいろ試す
連結成分の数は高々2しか減らないことによる下限があるな
(abab,baba) みたいなのならこれを達成できる
2kなら一回使えば↑の王道ルートに乗せれそう?
2k+1 も一回使えばいけそう こっちはこれで最適
逆から考えると場合分けがわかりやすいな

何通りか場合分けして書く
WA
えー
場合分けが足りてないことに気づく
書く
WA
えー
手元で試すとまだ場合分けが足りてないことに気づく
終了

結局a abab みたいなケースは2回ですら無理だったのでまだおかしかったんですね

異常な場合分けによらない解法:
2減らせるなら2減らす, みたいな貪欲を実装すればよかったっぽい?
yosupoのコードはかなり短かった

反省:
実装方針(こいついつも同じ反省してんな(いや今回は行けると思ってしまったのがなあ... 実際もうちょい時間あれば行けたとは思う))

E,F: まだ読んでない