ABC429 （2025/10/25）
〇A問題
まーす.icon Pythonは0-indexなので，お気をつけて～
Kaplam.iconひっっっさしぶりにまともに勝ててうれしい +73で再入水しました、ICPCまでratedしません
まーす.icon 途中，順位が2桁でビビった．
Kaplam.icon実は途中でいいなら意外とあったりする(そこから最終2000より下になるのもありがち)
まーす.icon へ～，なるほど．
CarpDay.icon 入水カムバック，おめでとう！
Kaplam.iconありがとうございます(*'ω'*)
CarpDay.icon相変わらず読み違いして，「まずM個OK」だと思って，入力例2で（？？）．読み直して〇
N_N.icon N回ループを回して判定．
〇B問題
まーす.icon $ S := \sum_{i = 1} ^ {N} A_{i}と置いて，for文で$ S - A_{k} = Mを満たす$ kが存在するかどうかを判断．
Kaplam.icon sum-ai == m になるか
CarpDay.iconまーす.iconさんと全く同じ．リストに対してin使っていたわ．全然意識しなかった．こわっ！
N_N.icon CarpDay.iconさんまーす.iconさんと全く同じ．
〇C問題
Kaplam.iconそれぞれ出てくる個数についてまとめて、2個以上あった値について、個数C2 * それ以外の数字のsum
まーす.icon $ D_{i} := \operatorname{Card}(\{k \mid i = A_{k} \})と置くと，答えは$ \sum_{i = 1} ^ {N} {}_{D_{i}} C_2 \times (N - D_{i}).
まーす.icon 今気が付いたけれど，Kaplam.iconさんのコメントを単に数式化しただけでした．
CarpDay.icon Kaplam.iconさんと同じっぽい．
N_N.icon 皆さんと一緒だと思う．ただし無駄な場合分けをしてた．
〇D問題
Kaplam.icon実装めんどそうだったのでEやってからにした 要するに、ある座標にいる人数+c人を超える一番小さい人数について考えればいいので、2周分について累積和してからにぶたんする
CarpDay.icon 人のいる地点から，次の人のいる地点までを対象にして，累積和とってどこでc以上になるか二分探索で確認．cを超えた値と，次の人のいる地点までの距離を掛けて合計
まーす.icon 考え方は上の2人と同じ．異なる点は尺取り法で考えた点．
N_N.icon Eの方が解けると思って後回しにしたけど，結果的にこっちの問題を先に解いておけば良かったと後悔．時間内に最後まで書ききれず．．．解き方は，まーす.icon さんと同じ．
〇E問題
Kaplam.icon 多始点BFS、Sの点を全部始点として、全ての頂点について、ある始点から始めた時の最短距離、について2始点分求める、既に2始点分ついてたところに来た探索はそこで止めたりとか気を付けましょうって感じ
CarpDay.icon いろいろ考えたけど方針立たず．Kaplam.iconさん速いし，まーす.iconさんも解けたので，自分も！と頑張ったが時間切れ．
CarpDay.icon コンテスト翌日，諦めてみなさんの伏字を確認．危険なノードからの多点BFSで解けそうと思って実装するも泥沼．解説コード確認して安全なノードからの多点BFSなら解ける理由を熟考して，恐らく理解．3つの並びを考えるときに真ん中を固定するように，経由点である危険な点からBFSしたら解けそう，という発想から切り替えることができなかったのが敗因．頭固いなぁ．
CarpDay.iconsounansyaさんのユーザ解説の方法が面白い．乱択アルゴリズム的な方法だけど，異なる点番号ならどこかのbitは必ず異なることを使って乱択性を排除している．計算時間は劣るけど，どこかで使える方法かも．
まーす.icon 自分がD問題解けたくらいにKaplam.iconさんがこの問題を通していてビックリ．使ったアルゴリズム：多始点BFS
まーす.icon 具体的な方法：安全な頂点を始点とする多始点BFSを用いて，危険な頂点$ uに対して，安全な頂点の中で一番近い頂点を$ v_{u, 1}，その次に近い頂点を$ v_{u, 2}として，$ u, v_{u, 1}の距離，$ u, v_{u, 2}の距離の2つを求める．ここで，注意しないといけないのは，BFS に始点の情報を持っておかないと$ v_{u, 1} = v_{u, 2}となる場合がある（これに気が付いていれば，初の3桁いけたのに......）． CarpDay.icon伏字の中でも，リンク（半角各括弧で囲む）にすると赤字になるのね．おもしろい．リンク自体は無意味だけど，メリハリ付けるのにいいね． N_N.icon 危険なノードから幅優先探索を使って最も近い安全なノードを2個見つければよいと思って書いたけど，WAやTLEが取れず．皆の伏字を読んだけど，あまり違わないような気がするなぁ．．．もうちょっと頑張れば良かったかな．
〇F問題
Kaplam.icon削除可能UnionFindというかonline dynamic connectivityを使って、スタートとゴールについて連結がどうかと、頂点の更新毎に4辺分更新入れたら解けそうと思ったけど、C++しか実装例見つからないし、うまく使えなくて諦めた、解説見たらもっとちゃんとした方法で解いててなるほど～って、↑ので本当に解けるか知らんけど
Kaplam.icon繋がってるかどうかの検証と思ってた、距離求めないといけないじゃん無理だわ
CarpDay.icon E問題分からなかったから覗く．面白そう！前から＆後ろから計算したのを利用するかと思ったけど，それでも全盤面更新するので，諦めてE問題に戻る．
CarpDay.icon まったく解法思いつかないので，すっぱり解説見る．解説見ても意味が分からず，サンプルコードをGPTにPython変換＋説明してもらってやっと理解．で，変換してもらったコードはTLEで，そこからTLE地獄．データを2次元→1次元にしたり，タプルをリストに変えたりしてやっとAC．AC-LIBRARYでなくて自作だとやや速くなるけど，2次元リストではやっぱりTLE．はやくCodon使えるようになって！！
まーす.icon 自分は，ランレングス圧縮のようなことをしてから，二分探索を用いていじいじする方法を考えていた．
〇G問題