ABC425 （2025/09/27）
〇A問題
まーす.icon $ iにおける符号と$ i ^ {3}を分けて考えてた．
tako.icon久しぶりに参加。やるだけ
CarpDay.icon久しぶり！久しぶりなのに，解くの速いなぁ！
Kaplam.icon同上
N_N.icon i の偶奇性で足すか引くかを判断．
N_N.icon CarpDay.icon さんに対抗して，Javaでストリームを使って 1-liner で書き直してみた．（実戦では絶対に使えない．．．）
CarpDay.icon ＼(^o^)／
CarpDay.icon久々の1-liner（わざわざ書き直した）．嬉しい．
〇B問題
まーす.icon $ A = -1 のところに，まだ$ Aにない値を昇順に入れた．
tako.icon タイトルがPermutationだったのでpermutation使ったが使わなくても行けるんかなとか思った。確認するところは関数に分けましょう
Kaplam.iconまーす.iconさんと同じ
N_N.icon 出力する解はまーす.iconさんと同じだけど，ややこしい処理をしてた．
CarpDay.icon tako.iconさんと同じ．オーバースペックだけど，B問題からitertoolsにお世話になる．
〇C問題
まーす.icon まず，$ Aの2周分の累積和をとって，クエリ1は，どこが先頭かという情報$ sの変更．クエリ2は，累積和と先頭の情報$ sを用いて計算．
tako.icon 今どこが頭か持つ累積和
Kaplam.iconついこの間も似たようなのやった気がする、スタート地点をmodで管理する
N_N.icontako.iconさんと同じ．競プロ的には，まーす.icon さんのように2週分とるといいんだよね．それよりも，累積和を取らずに1回TLE，Java なので和を long で宣言せずに WA1回．競プロ脳になりきれない．．．
CarpDay.icon上3名と同じかな．累積和対応のために1-indexで管理したため，少し混乱．
〇D問題
tako.icon 計算量適当でいけるやろと思ったがいけなかった
tako.icon 普通に探索済みのところを管理していなかっただけだった... やはり衰えている...
Kaplam.icon素直にシミュレーションすれば通る、最初に書いた探索だとなぜかサンプル3が少し合わなかったのでもっと素直な書き方したら合った、時間かかり過ぎたけどこれ以上早解き出来ても大して順位変わらなかったっぽい？
まーす.icon E と見比べて，Eの方がおもしろそうだったのでEへ．
CarpDay.icon途中まで組んで，面倒になってE問題へ．戻ってから頑張って組んで意外とすんなりAC．結果論だが，E問題行かずに頑張って正解時間早くするべきだった．
CarpDay.iconと思ったけど，Kaplam.iconさんの順位でもランクダウンなら，早くしても大差なかったっぽい．それより，E問題・F問題解くことが重要．
CarpDay.icon コンテスト中，サンプルの実行を確認するために，Excelでハンドシミュレーションしました．
https://scrapbox.io/files/68d80a5aa1fd4ba58e1aa427.png
N_N.icon Cで手こずったので，時間内にバグが取れず．冷静に考えると，問題としては難しくなかったかも．幅優先探索のように，新しく黒くなったマスの周囲で条件にあうものを黒くしてキューに積んでいく．キューに積むマスがなくなれば終了．
〇E問題
tako.icon Mが998244353固定なら簡単。 「階乗 MOD 素数以外 競プロ」とかでググると出てくるのでそれを使う。pythonの実装が見つからなかったのがつらい
tako.icon 解説見たらもっと簡単にできたらしい。 E問題で中国剰余定理 なんてインフレ進んだなぁと思ったがさすがに
CarpDay.iconさすがに（＾＾；
Kaplam.iconなんとかなりそうな気もしたけど数学系のEで通ったことあんまりないのとFが希望見えたからそっちやってた
まーす.icon 制約的に計算量が見積もりにくいが，1つのテストケースで$ O(N)程度のアルゴリズムを考えれば良さそうだけど......．これ以上計算量の改善の仕方が分からん......
まーす.icon $ O \left( N_{t} \cdot \sum_{t = 1} ^ {T} \sqrt{ \Sigma_{i = 1} ^ {N_{t}} C_{i} } \right)想定のプログラムをずっと投げていたけど，AC かどうかは抜きにして投げたところ，17件のTLE は無くならなかったので，撤収！撤収！
まーす.icon 解説見た．これは，できないといけないですね（反省）．解析入門I，杉浦でも帰納的集合（数学的帰納法）を用いて，形式的に証明できることを知っていた（つまり，記憶には残っているはず）のにねぇ......
まーす.icon 私は，素因数分解で思考ロックしていたので，発想自体はよかったっぽい．けど，toam さんの解説の方針を思いつかなかった点は，解析を専門としている身としては，よろしくない
CarpDay.icon 某必修科目で扱う問題そのまま．計算式は簡単だけど，tako.iconさんのいう通り，Mが素数でないので除算が入る（まーす.iconさん，「体ではない」ということで合ってる？）と単純でないので，諦めてD問題に戻る．
まーす.icon Yes．体は乗法についても群であることが担保されています．
CarpDay.iconありがと！
まーす.icon <(_ _)>
CarpDay.iconまーす.iconさんの終了後コメントに激しく同意．解説見て「できないといけない」と反省．完全に階乗求めて割り算することで頭が固まってしまっていた．場合の個数の基本的な関係式なのに．．．この式を使えば，計算式自体には割り算が入らないので，途中でＭの剰余求めても問題ないんだね．
〇F問題
Kaplam.iconDPで素直めにやってサンプル3が実行時間30秒程度、ただ高速化しても限界がありそうだったので、1回しか出てこない文字について着目すれば解けると思ったんだけど答えが合わなかった_(:3」∠)_
CarpDay.iconこんな古いABC問題，よく見つけてきたね．解説見たから気付いているだけなんだけど，この古い問題との大きな違いが，この問題を解く鍵になる，ということだね．
まーす.icon Atcoder Probrems のあの感じを見ると，どうしても埋めたくなっちゃうので，結構昔の問題もやってました．この問題が解けたら，Completed Contests になるので，記憶に残ってます．
CarpDay.iconアルファベット26文字の出現回数を状態としてBFS的な探索を実装したけど，同じ文字が連続する場合のみ特別扱いすることに気付いてやり直し．more_itertools.run_length使って対応した（つもり）ら，サンプル3すら終わらない．．気になるので，もう少し解説見ずにやってみる．
CarpDay.iconやってみたけどTLE（ｘｘ）．解説見る．実装上は異なる（bitDP or メモリ付き再帰関数）けど，方針としては同じやり方でも，後者（しかもmore_itertools使っている）から重いんだろうね．DPと異なり，同じ状態をまとめていないので遅い．DPのこと，まだしっかり理解できていない．反省．
CarpDay.icon別解の$ O(N^3)解法の理解に丸一日かかる．「トポロジカル順の個数」と関係あるらしいから，他の問題にも応用（内部で使用している区間DPはもちろん応用可能だけど）できる考えなのかも．
〇G問題