ABC461 （2026/06/06）
〇A問題
まーす.icon if文の動作確認．
まーす.icon 大暴落......．頼む，軽症 (-30程度) で済んでくれ(懇願)
まーす.icon -19 でした．なんとか耐えた感じ？
Kaplam.icon a <= b
N_N.icon 同じく．
CarpDay.icon 同じく
〇B問題
まーす.icon すべての$ i \ (i = 1, \dots, N)について，A[B[i] - 1] == i + 1(0 - indexed) が成り立つかどうか．
Kaplam.icon同上
N_N.icon 同じく．BがAの逆写像になっているか？
CarpDay.icon 同じく．問題文の意味が読み取れず，何度も確認する．読解力落ちてる．．
〇C問題
まーす.icon まず，価値が大きいものから$ M個を選ぶ（ただし，このとき種類が被ってはいけない．）．その次，上で選んでいないもののうち価値が大きいものから$ K - M個選んでいく．
Kaplam.icon種類毎に1番価値の高いものからm個とった後、残りの全体の宝石から高いもの順にとる
N_N.icon Kaplam.iconさんと同じ．
CarpDay.icon 既に選んでいる色を選んでいい個数が$ K-M個なので，価値の大きい順に個数が$ N個になるまで宝石を選んで，既に選んでいる宝石を選ぶ個数が$ K - M個を超えるなら加えない．
〇D問題
まーす.icon imos で考えていたが，どうしても$ O\left( (H \times W) ^ 2 \right)解法しか思いつかない......
まーす.icon こういう高速化の詰めを主軸においてそうな問題苦手なんよな......．解いてて苦しい
CarpDay.icon 同感です．TLE×2がなかなか取れなかった原因が，defaultdictでした．そろそろC++に変更するべきなんでしょうね．．．
Kaplam.iconまず二次元累積和をとってから、長方形範囲のH座標を上から1個ずつ下げていく、各Hについて下限Hを決めて範囲を探索した後、長方形範囲の一番上を削除するようにして二次元累積和を更新、探索操作がO(H*H*W)、更新操作も各HにW*H回かかるのでO(H*H*W)、pythonくん遅いのでdictで誤魔化してた処理を一次元listにしたり高速化しないと通らなかった、最終的にCodonだと余裕出来たけどコンテスト中盤ではCodonでも間に合わなくてE行ったぐらい
N_N.icon たぶん，あと少しだと思う．細かな条件分岐で失敗中．もう少しデバッグしてから書き込みます．
N_N.icon 尺取り法と1次元累積和を使うと，$ O(H^2 \times W) で行けると考えてる．だけど，尺取り法 では実装が重たくなってしまうみたい．どちらにしろ，これでは時間内に解けないわ．
N_N.icon 尺取り法の頭を動かしても尻尾を動かしても値が変化しないときの処理がしんどい．プログラムがどんどん汚くなっていくのにバグが取れない．．．誰の役にも立たないプログラム書きはこれくらいにしておきます．
Kaplam.iconそれぞれの値の出現回数を数えておいて、ans += (見ている値 + k)が後ろに出てくる回数 とするのが楽かもです
CarpDay.icon まーす.iconさんと同じく$ O((H\times W)^2地獄．制限時間が4秒だから単純な方法で解ける？と最後に記念投稿したが案の定TLE．コンテスト終了後，早々に解説を見る．苦手なやつだ．．
〇E問題
まーす.icon D が思いつかなかったのでE を見てた．こいつもかなり曲者で，一度黒にした後に，白になる部分の処理が上手く高速化ができない．
Kaplam.icon黒を引く時は、前にその行で黒を引いてから何種類白くなったか、白を引く時は前にその列で白を引いてから何種類黒が引かれたかをBITで管理する
CarpDay.icon まーす.iconさんと同じくEに重きを置く．過去に行った同じ操作から今回の操作の間に，別の操作を何回行ったかが分かればいいのでセグメント木で実装しようとするも，過去にどの行／列を扱ったかを扱うにはセグ木に集合を乗せる必要があり諦める．コンテスト終了後，早々に解説を見る（その２）．うーん．残念．
〇F問題
Kaplam.icon1024*1024*1024の約数の個数見てこれ再帰探索すれば通るのでは？ と書いてみたら16/22 までさくさく進んで笑ってたけど当然落ちた、16*27*25*49*121みたいに色んな種類の素数を混ぜるようにして約数出してみたら相当数出てきてこりゃむり、その後少しやっていた方針自体は少し合ってそうだけどACはむり
まーす.icon D, E 分からんかったので，Fもチラ見．数列$ Aの並び順も答えに影響するのがしんどくて，Eを考察．
CarpDay.icon またもまーす.iconさんと同じく，D・E分からず覗きに来る．数学的に奇麗そうだったので「こんなの解けるようになったらいいなぁ」と嘆いてE問題に戻る．
kakip.iconNの約数の個数はO(N^(1/3))ぐらいらしい
〇G問題