ABC419 （2025/08/16）
〇A問題
まーす.iconif文で一個ずつ丁寧に．
まーす.icon寝過ごして，Unratedで参加．結果としてよかった．
wataumi.iconKaplam.iconまーす.iconさんと同じ。
CarpDay.icon wataumi.iconさん，連続の大幅ランクアップで，まーす.iconさんに届きそう！（いずれ自分にも．．）
CarpDay.icon 問題文コピペして，辞書作った！
N_N.icon if 文で単純に文字列の比較．
Kaplam.iconTwitterでA問題について、なぜかred,blue,greenだけでなくif yellow:print("RRR")とするWAが散見されているとの情報が流れていましたが、コンテスト中の問題文(自作ツールで入出力抜く時に取ってた)にだけ以下の対策文字列があったみたいですね、ABC実況動画を見てもここに余計な行は見えないので多分文字サイズ1かつ白文字とかになってた様子
https://scrapbox.io/files/68a4b390b473a818ae798910.png
CarpDay.iconおおお！すごいね！コンテスト終了から5日後の本日に問題文コピペしたけど，そんな記述ありませんでした．学校の宿題に応用するケース出てきそうだね！
N_N.icon Twitter で話題になってたらしいね．なるほど．文字サイズ1かつ白文字かぁ．でもコピペしたときに気付きそうなものだけど．．．
〇B問題
まーす.iconクエリ２にて，最小値の削除忘れで2WA．はやとちり．けど，Unratedだから痛くもかゆくもない．
CarpDay.icon先週先々週の教訓を生かして，素直にremoveしました．
Kaplam.iconCarpDay.iconと多分同じくset使わずlistでremoveした
wataumi.iconlist管理。removeの代わりに、上界の200に置き換え。（1 ≤ x ≤ 100）
N_N.icon 自作の SortedList 使用．
〇C問題
CarpDay.icon「次元を減らして1次元で考える」の原則に従うも迷走．平均？中央値？を経て，やっと正解に辿り着く．仲間内ですでに4人ACで焦る．
まーす.icon$ \max\left(\frac{\max R - \min R + 1}{2}, \frac{\max C - \min C + 1}{2}\right).
wataumi.iconまーす.iconさんと同じ。
CarpDay.iconそんなにシンプルに解けるんだ．．． ((max(R) - min(R)) / 2, (max(C) - min(C)) / 2)考えて，実数になる場合もあるからRもCも+1するバージョン，合計4通りのゴールを考えて，各点からゴールまでの最小移動時間を各ゴールについて求めて最小のを出力した．確かにまーす.iconさんたちの方法で十分だ．．
まーす.icon$ \min\{集合場所から\red{一番遠い人}がたどり着く時間 \}を求めればいいですね．
CarpDay.icon言われてみれば，おっしゃる通り．それに気付かなかったのが残念（だけど，少しのロスで済んでよかった）．
Kaplam.icon最大とか最小とかをこねこねする
N_N.icon 斜め方向に進むことができるので，まーす.icon さんと同様に解く．
〇D問題
Kaplam.iconimos[ 序盤の順位結構よかった気がする
貼った記憶ないので誰かのカーソルが当たった形じゃないかと_(:3」∠)_
ありがとう！
wataumi.iconKaplam.iconさんと同じ。
CarpDay.iconimos法のXORバージョン．
まーす.icon imos法．PyPy だとTLE．
CarpDay.iconPyPy使ったけど，問題なかったよ～
まーす.icon$ O(N)解法でしたけど，なぜかTLEになって焦りました．CPython だとAC．なんでや？
まーす.icon恐らく，私の解法は一文字ずつ文字を連結していったから？
CarpDay.iconそうそう！文字列連結は，''.join(リスト)を使いましょう！
まーす.icon前に''.join(リスト)の方が速いと聞いたことがあったけど，+=で連結する方が楽だったから，ずっと後者を採用してたんだよね......
N_N.icon しばらくセグメント木を使うのかな？と思って迷走する．ちなみに， imos法 は覚えてないけど，多分同じようなことをして解いた．Lの値とR+1の値（つまり領域の境界）を小さい順に覚えて，境界を何回跨いだかの累積和を取る．累積和の偶奇性を使ってその領域をSから取ってくるかTから取ってくるか判断する．
〇E問題
Kaplam.iconDPだな～って思ったけどイマイチ解法思いつかないしG見たら解けそうな気がしたので思い切って行ってみた
CarpDay.icon何となく思いつくも自信がなくF・Gを覗くがもっと分からなかったので戻る．Lごとにグループ作って，各グループの数をすべてk（mod M)にするために必要な個数作っておく．その後，DPで最初からi番目のグループまでの合計がk（mod M)になるのに必要な最小数を計算する．O(N M^2)じゃないかな？．計算量心配だったけど，意外にAC．2週連続あれで嬉しい．
wataumi.iconPyPyでTLE×３、AtCoder生成AI対策ルールに従いPython で書いたコードを C++ に変換してAC。方針は、繰り返し二乗法＋極小畳み込み'。本当はPythonで通したかった……。
wataumi.icon再提出でPythonで通せました。'繰り返し二乗法'要らなかったわ！
まーす.iconもしかして，$ O(N M ^ 2)解法間に合う感じ？
CarpDay.iconそんな感じ．
まーす.icon$ \max_{1 \leq N, M \leq 500} N M ^ 2 > 10 ^ 8だから，思い付きはしたけれど，TLE怖くて実装しなかった感じ．けど，まだ工夫が必要そう......
N_N.icon ICPCの過去問に似たような問題があったかと．計数カウンタの問題．解法は読んだことがないけど．．．
CarpDay.iconMODを考える点やDPを使う点は似てますね．あれはボタン単体でみると不要な1周を何回するか，という点がポイントでした．
N_N.icon 今回もDPを使うのかな？と思いつつ，使い方が思いつかなかったので，解くまでに至りませんでした．途中までの自分の迷走具合がICPCの過去問のときと似ていたので，何となく似た問題なのかなと思ったのですが．．．
〇F問題
CarpDay.icon単純に文字と文字に重なりがなかったとしても解けない．全部の文字をLの中に入れて，先頭か間か最後かに適当な文字を入れる組合せってどうやって計算するんや？ネットで調べたら「分割数」がそれに近いみたい．まーす.iconさん好きそう．
まーす.icon分割数はDP で求めることが出来そうだけれど，それを定義したとして何が都合がいいのだろうか......？もしかして，長さ$ Lの文字列を$ 26進数の正整数とみて分割数を適用するとか？
CarpDay.icon例えば全体の長さL=10で，文字の種類がN=２つ，２つの文字列S1，S2の長さがともに3とします．簡単のため，S1とS2は重なりがないとすると，S1とS2はそのまま含まれるので3+3＝6文字分は確定．残り4文字は小文字26種類の何でもいい．仮にS1，S2の順に左から登場するとすると，残り4文字が入る位置は，S1の前（先頭），S1とS2の間，S2の後ろ（末尾）の3か所．よって，「4を3か所に分割する組合せがいくつあるか？」という問題が解ける必要があるのかな？と思ってネット検索したら「分割数」が出てきた訳です．でも分割数は，上の例だと3か所に少なくとも1つは入る必要があるようなので，分割数関係ありませんでした！
CarpDay.icon諦めて解説見る．やっぱり分割数無関係でした．．．解説読んでもよく分からんな．．
まーす.icon数え挙げ問題は結構発想力がいるので難しいですね💦
CarpDay.icon1週間遅れで解説の理解に努める．DPで解くけど，本質はその前に行う文字列処理エイホーコラシック法みたい．とりあえず理解したので，今後使う機会があるか分からないけど文字列アルゴリズムのページに追記しておきました． 〇G問題
Kaplam.iconMの制約的に意味のない辺 がいっぱいありそうだからそれ消したら分岐だけになって実質的なマス数大分少ないから後は素直に探索で計算量足りると思ったんだけどもう一工夫必要だったらしい？ よくわかんない
Kaplam.icon方針合ってるみたいだからpythonに加えて見るからに定数倍悪い実装したせいっぽい？ 気が向いたらupsolveする
Kaplam.icon方針そのままで通った(3940msのギリギリだけど) 元々はBFSで通った所をそれぞれdequeで持ってたんだけど再帰DFSで通った所はsetで、あと不要な辺に対するワープをdefaultdictで管理してたところから辺を繋ぎなおすように、コンテスト中に通せたら気持ちよかっただろうに..._(:3」∠)_
CarpDay.iconG問題ACですか！コンテスト後で素晴らしい！