ABC434 （2025/11/29）
〇A問題
Kaplam.icon横浜では私はやるつもりないので(まーす.iconはやるかもとか言ってたけど)ICPC前最後でした、wktk
CarpDay.icon 横浜，楽しんで頑張ってね～！
Kaplam.iconヾ(=・ω・=)o
まーす.icon 今回は私事で書き込みしない<(_ _)>（ちょっと病み期入るカモ．大会までに気分を立て直す）
まーす.icon Eはいけそうな感じがしているので，もう少し粘ってみる．
CarpDay.icon 気分転換されることを願ってます！自分もEもう少し粘ります！
まーす.icon ありがとうございます<(_ _)>
まーす.icon AC出た問題だけ報告．A, B, C, E（E はコメント付けた）
CarpDay.icon 先週は定式化して解いたけど，今週はプログラミング的に解きました．
N_N.icon W * 1000 / B + 1 で求めました．
〇B問題
Kaplam.icon鳥さん毎に数数えて
CarpDay.icon 鳥さん毎に，個数と合計を辞書で保管
N_N.icon CarpDay.icon さんと同じです．
〇C問題
Kaplam.icon今までの操作であり得る下限と上限を持っておく、サンプル弱すぎて前回の時間を更新してないのと、上限下限について更新してないと通るわけない提出2回した('ω')
CarpDay.icon Kaplam.iconさんと同じ．時間更新してなくてWAくらったのまでおんなじ！
N_N.icon CarpDay.icon さん Kaplam.iconさんと同じ．WA×1回分まで同じ！だけど，さらに入力しながら計算してたので，途中でループを打ち切って入力がずれてしまうという不具合になかなか気付かず．．．
〇D問題
Kaplam.icon二次元累積和でそれぞれのマスについてかかっている雲の個数を求めてから、1個だけかかっているマスについてもう一度二次元累積和して、それぞれの雲の範囲で1個だけかかっているマスの個数を求める
CarpDay.icon基本的にKaplam.iconさんと同じ．後半を2個以上雲が掛かっている方を求めたため，最後の計算ややこしくなった．
N_N.icon imos 法かな？UnionFind ではなさそうだな，セグ木かも？などと思いながら，自分なりのデータ構造を考えて書いてたけど，いずれにせよ時間切れ．
〇E問題
kakip.icon辺(x_i-r_i, x_i+r_i)を張る。頂点数の合計から、木の個数を引いたのが答え
Kaplam.iconグラフ的に持てそうとか思ったけどぱっと思い浮かばずFが一瞬見えた気がしたからやってた、順位表見ましょう
CarpDay.icon出発するウサギのindexの集合をX（こちらは座標同じでも別とするので大きさN），到着する座標の集合をYとして，XとYの対応を考える．Xの1つの要素からYの2つの要素に線が引かれた二部グラフで考える．最初はYの座標の小さい方からGreedyに決定（サンプルもOK）するがWA．WAの理由分かってYの次数が小さい点から決定する方法（次数にheapqを使って動的に最小次数のYを獲得）する方法にするもまたWA．ふとこの問題は最大マッチング問題であることに気付き，pulp使って数理計画問題として定式化してコーディング中に時間切れ．完成して投稿するもTLE．．次に最大マッチング問題は最大流問題で解けることを思い出してコーディングするもまたTLE．（←いまここ）
CarpDay.icon 自分の3・4番目の方法（ともにTLE）はアルゴリズムのオーダ確認したら$ O(N^2)は確実なのでそもそも無理な手法でした．
CarpDay.icon 自分の2番目のコード（WA）見直したら，一方確定させたあとの他方を削除するのを忘れていることを発見．それを修正したらACでした．．．うーん．コンテスト中に気付きたかった．．
CarpDay.icon AC出たのでみなさんの伏字を見る．よく分かりませんでしたが，下のとおりまーす.iconさんのおかげでやり方理解しました．ありがとうございます．
CarpDay.icon 解説見る．多分kakip.iconさんは解法1なんだろうね．極大木を考えるという説明でよく理解できました．一方，解法2は自分の3・4番目！オーダ$ O(N\sqrt{N})で解けるアルゴリズムがある？？知らなかったよ！
CarpDay.icon 上のアルゴリズムは（解説にも記してありますが）二分グラフの最大マッチングに特化したHopcroft–Karp法で計算量$ O(|E|\sqrt{|V|})です（解説ではnとmが逆になっている．多分間違い）．
まーす.icon 涙を流しながらAC．嬉しいのやら辛いのやら......方針は恐らくほとんどkakip.icon さんと同じ．異なる点はindexでのグラフを考えていた点．
まーす.icon コメント付けたコードを提出してみました．
CarpDay.icon ありがとう．確認してみます．
まーす.icon 私もCarpDay.icon さんのコードを見てみます<(_ _)>
CarpDay.icon確認しました．なるほど．到着地点をノードとして，ジャンプするウサギが同じノードは枝で結んで連結成分を考える．各連結成分に対してジャンプしたウサギが何匹いるか求め，各連結成分に対してmin(ジャンプしたウサギの匹数，到着地点の個数）を求めているということかな？
まーす.icon Yes! 方針はコンテスト中に浮かんでいたのですが，Cでやらかしてパニックになっていました
CarpDay.icon最後の発想，気付けば当たり前だけど，思いつかなかったなぁ．今でもまだ少ししっくりいっていない．反例本当にないんかな？でもなさそうだよなぁ．．という感じ．
まーす.icon 証明が難しそうですね．各連結成分に対する辺の自由度のようなものを考えたことがきっかけです．
CarpDay.icon背理法でできそうではあるけど．．まず連結成分1つだけを考えたとき，答えがウサギの匹数より大きくならない（ウサギは匹ではなくて羽だっけ？）ことは自明なので，答えがウサギの匹数より小さくなる場合考えると，どちらに跳んでも既に別のウサギが跳んでいることになる．もしいずれかが誰も跳んでいないというウサギがいると仮定すると，そのウサギはそちらに跳べば答えが増加するけど．．．うーん．うまく証明できない．．解説見ます．
まーす.icon 問題文では「匹」でした．
CarpDay.icon ほんとだ！ありがとう．
まーす.icon $ 私の解法 \implies 解説1の証明は$ \minの定義からいけそう？（背理法では無く直接に証明する）
CarpDay.icon結果的には同じこと言っていますね．木になる場合は，ウサギ（枝）の数＝到着地点の数ー１なので，minとるとウサギの数になるし，木にならない場合は，ウサギ（枝）の数≧到着地点の数なのでminとると到着地点の数になるので，同じことになります．
まーす.icon そうですね．
〇F問題
Kaplam.iconソートして、ある文字と前方一致しているものについてまとめて前方部分を切り取ってソートして～って再帰的にやれば出来るのではと思って頑張って実装してたけどデバッグの段階でダメなケースに気付いた、途中で順位表見て触れちゃいけないやつって気付くべきだった
Kaplam.icon終了直前の順位表で1,2位にAIがいたけど、人類が殆ど解いてないGは通してたのにF両方ペナ付き(片方3ペナ)で通せてなかったのでAI独力では解けないらしい
CarpDay.icon「AIがいた」ってどういう意味？AtCoderオフィシャルのAIアカウントが参加しているの？
Kaplam.iconAI不正ユーザーが毎回のように上位にいるのでそいつらのことです...露骨に怪しいのは終了直後すぐにBANされて順位表からいなくなります
CarpDay.icon 回答ありがとう．そんなのいるんだ．コンテスト中に確認する余裕ないから，自分は見ることできないなぁ(^^;
kakip.iconA1とA2の候補持っていろいろとか考えたけど問題の色的に無理そう
〇G問題