ABC466 （2026/07/11）
〇A問題
まーす.icon $ \max X \geq 0で判断．
まーす.icon 大暴落......．やっぱり実装グダるとそこから，パニックになるな．
Kaplam.icon for i in ls: if i >= 0:print("Yes") みたいな
Kaplam.icon先週で本当に辞めるつもりだったんですけどchokudaiさんが最強コン出してやるからまだやれっていうので2か月延長します...
CarpDay.icon Welcome!!
CarpDay.icon 日曜日にバチャコン．まーす.iconさんと同じ．
〇B問題
まーす.icon 各クエリに対し，$ \operatorname{ans}_{C} := \max \{\operatorname{ans}_{C},\ S \}で更新．なお，各$ \operatorname{ans}_{c}の初期値は$ -1とする．
Kaplam.icon dic(c) = max(dic(c),s) として、 if i in dic: みたいに
CarpDay.icon 完全にまーす.iconさんと同じ．
〇C問題
まーす.icon 方針は二分探索？インタラクティブ形式が苦手すぎて，コンテストの大半をこの問題に費やす......．（大戦犯）
まーす.icon この問題許すまじ......．瓦1枚消えた......
まーす.icon N_N.icon さんの伏字を見た後に実装したら，意外と素直にAC出た．尺取りはよく使ってるのにインタラクティブになったとたん解けなくなる．あら不思議
Kaplam.icon st,en(初期値st+1)として、もしtrueならans += en-st(st から en-1,en の組み合わせを足す)してst+1、falseならen+1、st == enになったらen+1、毎回stとenどちらかが+1されるので比較回数は2N以下、ペナはinputだかoutputの形式がうちが普段使いしているものとインタラクティブで相性が悪いっぽい、かと思ってたから一部設定変更解除してたんだけど足りなかったらしく
N_N.icon 尺取り法ですね．だけど，無駄があったのか，REが取れませんでした．
まーす.icon 伏字見ました......．なるほど，この問題普通にいい問題ですね．私の解法の場合，最悪の質問回数が，$ N \log N回となり，そこが不安ながらずっとコードと格闘していました．
Kaplam.iconコード読みました、iを1からNまでのループと、jをi+1からNまでのループでO(N**2)の2重ループになっていて、jがNにたどり着いた場合のbreak処理を踏まない、例えば点1から6までが(1,1,1,1,1,3)という位置にあるケースでクエリ回数が12を超えます
kakip.iconinput()で出力すると自動的にflushするらしい このTipsが活きる日はくるのか
CarpDay.icon ( ..)φメモメモ
CarpDay.icon 初めは二分探索を考えていたけど，Yesのときのメリットが大きすぎなのに違和感を覚える．全部1以上離れたときでも2N回で終わる必要があるので悩む（変にこの問題にこだわって時間を溶かす）．VSCodeの環境をABC特化したため，デバッグ環境がインタラクティブに対応できていないことに気付き，諦めてD問題へ．終了後に尺取り法でシンプルに解けそうなことに気付て実装．
〇D問題
まーす.icon Cよりも簡単．よくある縦と横を分けて考える手法
N_N.icon 後ろから考える．
Kaplam.iconあるh,wに置いてあるコマにIDを振って、それに基づいて消したり
CarpDay.icon 逆順にしたらシンプルに解くコードがWA．原因分からず微修正してまたWA．どうしようもないので，別方法で実装．各行・列に置いたコマの番号を保存する．各コマに対して後から置いたコマによって削除されたかどうかを表す変数を用意しておいて，新しく置いたコマと同じ行／列のコマがあれば，それらのコマに削除フラグを付ける．
CarpDay.icon 終了後，WAの理由判明．どうして気付かなかったかなぁ．．
〇E問題
まーす.icon 多分，Cより簡単．方法はDP？
まーす.icon スクラップボックスに書き込んだ後，すぐにAC．絶対にCで粘るべきではなかった．（DやEにも目を通すべきだった）
まーす.icon $ O(K ^ {2} N)解法．
まーす.icon DP の定義：$ dp_{i, j, k} := (i番目までのカードで，ひっくり返す区間うちの左端点がj個あり，\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ そのうち右端点がk個ある時の，表になっているカードの総和の最大値)
N_N.icon はい．DPですね．
Kaplam.iconひっくり返す操作を棒2本入れると考えると、表裏表裏...表裏表、という区間が合わせてひっくり返した回数 * 2 + 1個出来るので、見た枚数と、ひっくり返しているかと、何巡目かでDP、Cよりは難しいです
Kaplam.iconと思ってたけどCのAC5500人止まりでE3500人通してるし読んだ人数考えると本当に難易度逆転してる説ある...？
まーす.icon そのうちの一人でーす......．Cは多分インタラクティブなのが，正答率下げてる要因．他にも解法として，尺取りくらいしか許されていないのも要因？
Kaplam.iconむしろ割と考えないといけないと思うEで3500人も通ってるのがわるい
まーす.icon Eは割とすぐに方針立ったよ．DPとしては結構素直な気がする．もちろん，計算コストが怖いけどね．
Kaplam.iconこれの方針すぐ立てられる人はCの方針も出しましょう...ひっくり返す操作で分割されるって少なくともCの話と比べたら出すの難しいと思うんだけども個人差ある部分だしわかんない...
まーす.icon うーんと恐らく，Kaplam.iconさんと私の解法違うかも......
Kaplam.icon解説もそうなの！
まーす.icon コードチラ見したけど，3次元のDPを考えている点では同じ．だけど，DPの定義の仕方が異なる．
CarpDay.icon自分も3次元DPだけどまーす.iconさんとちょっと異なる．$ dp_{i,k,flag}で，i番目まで見てk回反転使ってi番目が反転している／していない場合における，元の表面の合計からの最大改善量としました．
〇F問題
kakip.iconなんかにぶたんでとばしながら再帰したら通った 6完してたら青上位かちょっともったいない
Kaplam.icon値毎に、値-1と、modとった値の2個に分かれるからそんな感じで再帰してTLE*6、解説も似たようなことしてると思うんだけど...priority queue って書いてるしそこかしら
まーす.icon チラ見しました．面白そうなのでやるかも．
〇G問題