ABC424 （2025/09/20）
〇A問題
Kaplam.iconlen(st) != 3
まーす.iconlen(set(list(map(int, input().split()))) < 3かどうかで判断．
まーす.icon 制約に" 三辺の長さが $ a, b, c であるような三角形が存在する "とあり，安心した．
CarpDay.icon まーす.iconさんと同じ
wataumi.icon合奏が早く終わり急いで参加、ぎりぎり間に合わずUnrated。
愚直にif a == b or b == c or c == a:
N_N.icon wataumi.icon さんと同じ．
〇B問題
Kaplam.icon何問正解したか持っとく
CarpDay.iconKaplam.iconさんと同じ．正解数しか気にしない．
wataumi.iconKaplam.iconに同じ。
まーす.icon 参加者$ iが問題$ jを正解したか，していないかのフラグ（した場合は$ 1，していない場合は$ 0）を持って，$ iの正解数が$ Mかどうかで判断．
N_N.icon 何問正解したかを持っていたらいいだけなのに，正解した問題集合を持つようにした．問題の条件は読んでいたけど，そうしたかっただけ．
〇C問題
Kaplam.icon取得したスキルから、それを取得した場合に取得できるようになるスキルを探して～って感じ
CarpDay.icon修得したスキルを始点，そのスキルを修得したら新たに修得できるスキルを終点とした有向グラフを作ってDFS
まーす.icon Kaplam.iconさんとほとんど同じ．
wataumi.iconN_N.iconに同じ。
N_N.icon CarpDay.icon さんと近いけどBFS．
〇D問題
Kaplam.icon左上から探索して2*2を検知したら右下を白くすればいい気がする、10分4完! とか言ってたら落ちた, .##\n##.\n##. とかで落ちる,再帰した、2*2を検知したら4個のうちどれかを消す、としてTLE、左上の探索が不要に気付いて3個にしてTLE、右上も不要なのに気付いて通った
CarpDay.icon自分も「右下だけでいいやん！」って思ったけど，たまたまエラーケースに気付きました．
CarpDay.icon左上から右下に走査する． 2×2が黒の箇所見つけたとき，上の2つを白にしてもメリットないので，下の2つの左右について，それぞれを白にした場合を作ってDFSする．座標を2次元でなく1次元にしたけど，1次元から2次元に戻すときにWで//と%をするところ，Hでしてしまって1ペナ．ケアレスミスをなくしたい．
CarpDay.icon解説見たらditDPが本流の様子．自分たちの解法の場合，枝刈りが重要みたい．時間内に収まってラッキー．
CarpDay.icon解説の2番目の方法で実装．1番目のwataumi.iconさんの方法よりオーダーが小さいはずなのに，遅かった（自分の実装が悪いのだろうけど）．．しかも実装ややこしい．この方法を採用するなら，2番目より1番目をお勧めします．
wataumi.iconビットDP
CarpDay.iconさすが！1ペナのせいで，また負けました．
CarpDay.iconコードを拝見．元の状態から目標の状態にすることができるかの判定，目標の状態にするのに必要な手数の計算（bitcoutメソッド使う手もあるよ），黒の2×2が存在するかの判定など，ビット演算を巧みに使いこなしていて，すごい！
まーす.icon 貪欲に考えてずっとWA．「$ \mathbb{Q} の濃度が$ \mathbb{N}と等しい，つまり，$ \mathbb{Q}が可算集合である」という命題を証明するときにとるような全単射な写像$ \varphiを考えて，その写像を用いてやってみたけれどWA．
CarpDay.icon「・・・という命題を証明するとき」と言われても．．．（^^; 「濃度」も分からん．．
まーす.icon 濃度はざっくりと説明すると，集合の要素の個数です．基数などとも呼ばれたりしますが，或る集合$ Xが可算か不可算か，はたまた，それよりももっと個数が多いのかという指標にも用いられたりする文献も見かけたので，「濃度」と「基数」の違いは自分の答えは出ていない感じです．
CarpDay.icon 解説ありがとう．ﾒﾓﾒﾓφ(•ᴗ•๑)
まーす.icon Kaplam.icon さんとCarpDay.icon さんの伏字見た．はなから左下を白にするメリットないやんと思ってました......．私は，$ 3 \times 3（一回の変更で寄与する範囲）まで広げて考えてました．
N_N.icon 結局解けてない．最初，2×2の黒マスに対応した頂点群と，1×1の黒マスに対応した頂点群の間の二部グラフの最大マッチング問題か，最小頂点被覆問題になるのかなと思ってしばらく考えてたけど，多分違う．
〇E問題
CarpDay.iconちょっと考えたけど分からぬ．Nが少なくてもKが多い場合あるから，まとめて処理する必要あるけど．．
CarpDay.icon解説見る．yuichang.iconさんが得意なこの解法，自分はすぐ忘れてしまうんだよね．
CarpDay.icon解説に従ってあの解法で実装するもTLE．logとか使ってwhileループ削除する努力するも3ケースTLE．諦めて別解の方法使ったらすんなりAC．当初，heapqに同じ長さの要素が複数入ったときに，連続してpopするようにdefaultdictでheapq内に入っている各長さの要素数を保持する工夫をしたがそれが仇となって2ケースTLE．シンプルに実装したらAC．うーん．不思議な問題．
Kaplam.icon最大から半分に折った長さまでは全部折れて、その状態の最大から～って考えたら折る本数自体は簡単に求まりそうな気がしたけど上手くまとまらなくてFやってた メモ含めて考察あってたらしいし時間もあったからFよりEやるべきだったかも
wataumi.icon E以降 "頭痛が痛い" 状態で、半ば諦めモード。
〇F問題
CarpDay.icon円なので，2周分考えれば区間と同じじゃね？と各点に対して現在属するグループを表す整数を用意して，弦によって2つに分割されるたびに新しいグループに変更．一括変更するために遅延セグ木を利用したけどWA．発想自体NG？
CarpDay.iconKaplam.iconさんのご指摘のおかげで自分の方法がNGなことを理解したので諦める．解説読んだ後でまーす.iconさんの方法が最も納得できたので，解説2を参考に少しだけアレンジを加えたらシンプルにACできました．まーす.iconさんの重み付きのカッコを表すセグメント木にカッコの個数を表すセグメント木も併用したら，よくあるMOD = 998244353でACでした！
CarpDay.icon解説の解法3の意味をようやく理解してAC．解説中の「Rの最小値」は「Rの最大値」の間違いだと思う．この方法が一番シンプルでお勧めかも．
Kaplam.icon線を引くのを範囲を分割すると考えて、セグ木で範囲二つを塗り替える...としてWA、解けてる気がしてたけど今書いててWAケースに気付いた_(:3」∠)_
CarpDay.icon多分自分はそのケースに気付いていないんだろうなぁ．．
Kaplam.iconhttps://scrapbox.io/files/68cee8b4c51c0db926fdf528.png
小さく書きすぎて見辛いですが私の場合はこのケースの考慮が抜けていました、a～bを奇数、外側を偶数として区間分けした時、他の区間にぶつかるまでSortedSetを使って区間を広げたんですが3手目の後4と6を結ぼうとすると結べない判定になってしまっていて、これに近い方針で4のところまで6を塗るのは難しそうです、6を塗った場所に4を塗る方針は出来なくはないのかもしれませんが実装もかなり重そうだし速度も危うくなる気がします_(:3」∠)_
CarpDay.icon確かに！このケースは対応できてなかったです。また、追加する区間が既存区間を含む場合、上図の最後で言えば離れた6と6を両端とする区間を加えた時、内部を全部7にしてしまうので、5の区間を考慮できなくなる、ということにも気付きました。説明ありがとう！
まーす.icon （遅延ではない）SegTreeを使ってAC．直線にindexによる重みづけをすることにより引いた直線の区別を行う．そして，交差している直線があるかを判断する．正直，Dより考えやすかったかも......．なお，直線の区別には，素数の性質を用いた．
CarpDay.iconコード拝見しました。直線と言うより、解説の解法2の考えに近い？重みの付け方、あの方法だと交わるのに合計が0になる場合もあり得るのでは？という気がしましたが、絶対そんなこと起こらないのかな？
まーす.icon 結論は，「確実にはAC出ないが，計算量的に余裕があるのでWAが出るの確率をかなり小さくできる．」です．試しに，MODに$ 10 ^ 6以上の最小の素数を代入してやってみましたが，WAでした．なので，ある意味 hash による解法も近いように感じます．因みに，MODは$ 1 \times 10 ^ {18} + 1程度が限界でした．（それ以上はTLE）
CarpDay.icon情報ありがとう．本番で「できれば1発でAC」取るには，勘と経験が必要な手法，ということですね．
CarpDay.iconあとついでに質問していいですか？MODに素数を指定する理由は何ですか？例えばACになったMOD=1999993にするのと，素数でないMOD=1999994の違いは？前者の方が，交わるのに合計が0になる確率が少なくなる，ということ？（ABCでよく「・・・で割った余りを求めよ」という問題あるけど，何であんな中途半端な数なのかな？と思いつつ，きちんと理解していませんでした．）
まーす.icon $ pを素数として，$ \mathbb{Z}_{p} := \{ n \in \mathbb{Z} \mid 0 \leq n < p \}とすると，$ \mathbb{Z}_{p}は体だからです．
CarpDay.icon回答ありがとう．勉強しないと理解できないことが分かりました．．
Kaplam.iconよく見る998244353に関しては(2^23) * 119 + 1だからFFTでの利便性がとても高いらしくて、逆にFFTでないなら適当な大きい素数(一昔前には使われてた1000000007とか)で問題ないけど、そうすると998244353→FFTだな！ というメタ読みが出来てしまうのでどの問題でも998244353が使われるようになったとかなんとか
CarpDay.icon情報ありがとう．確かに昔は10^9⁺7のような設定多かった気がします．FFTもよく聞くけど手つかず．．
〇G問題