ABC431 （2025/11/08）
〇A問題
まーす.icon $ \max(H - B, 0).
Kaplam.icon if a-b >= 0:
N_N.icon まーす.iconさんと同じ．今日は（今日も？）ダメダメでした．
CarpDay.icon 出先だったので翌日バチャコン．まーす.iconさんN N.iconさんと同じ．
〇B問題
まーす.icon 各部品$ iに対して，ロボットに取り付けられているか，いないかのflagを考える．
Kaplam.icon同上
N_N.icon たぶん同上．
CarpDay.icon 同じっぽい．
〇C問題
まーす.icon 尺取り法で，小さい部品からマッチングする．
Kaplam.iconsortして、今見てるbodyでheadを支えられるなら採用、支えられないなら1個大きいbodyを持ってくるって感じ もしCからやってたらFAだったらしいし来週以降Cからやってもいいかも、Aは対抗が多いし
N_N.icon 重い頭から順に自分よりも重い体がいくつあるかを調べていく．自分より重い頭の数が，自分より重い体の数より大きければ，その頭は使えない．というロジックで書いたけど，WA×12だったので，次の問題に進む．
まーす.icon WAケース見つけました．
code:WAケース
4 3 3
1 6 8 9
7 7 20
code:想定解
Yes
N_N.icon まーす.iconさん，ありがとう！今から試してみます．（親切に，コピーまでできるようにしてくれて助かります！！）
まーす.icon <(_ _)>
N_N.icon ああそうか？バグの原因はわかりました！
まーす.icon お役に立てて良かったです！
N_N.icon 通りました！<(_ _)>
まーす.icon <(_ _)>
CarpDay.icon 3問連続まーす.iconさんと同じ．
〇D問題
まーす.icon 解法が思いつかなかったので，E問題へ．結果として，この選択は間違いでした......（∵解いている人が多かった）
Kaplam.icon片側だけを考える、head側としてあり得る重さは全体の重さ//2までなので、ある個数まで見た時のhappy度合いのmaxをDPで
N_N.icon 最初からDPだよな，と考えて取り組む．頭の重さの合計をキー，嬉しさの合計をバリューとして持つ写像を持って，N回ループするDPを使ったけど，TLE×30までしか届かず．C問題もD問題もダメダメでした．
N_N.icon Java だと配列を使うと定数倍高速化で通るらしい．アルゴリズム的には間違ってなかったんだけど．定数倍で TLE は辛い．．．
CarpDay.icon 今度はKaplam.iconさんと同じ．実装力弱い．
〇E問題
まーす.icon 最初，入射方向と座標の情報を入れたBFS（ギラティナ？みたいなやつ）を考えていたのだけれど，大きな考え漏れがあって，ずっと苦しんでいた．
まーす.icon 解説見た．後もう少しだった考えれば解けた問題だった．敗因：光の入射だけを考えていた点
Kaplam.iconどこから入ってきたかと座標を持ってBFS、今ある盤面で進めるところまで進んで、進んだ所全てについて、進んだのと違う方向(入ってきた方向の真逆は除いて)には1回追加の変更で行けるので、その辺を持ってうんにゃら、計算量的には足りるはずだけど数件TLEが出て、雑な実装しているところがあったのでそこを直してもTLEが消えず、codonを試したら少しの修正でコンパイル通ったけどTLE+MLE、色々直しても件数が変わらないのでよく見たら1か所フラグ抜けがあったのでそれ修正して100ms台で通った、pypyで出したら600msで普通に通った('ω')
CarpDay.icon BFSかUnionFindかな？と思うも，方針が定まらずF問題へ．
CarpDay.icon上の伏字見たけど，例えばスタートから到着できる地点が複数あったとき（大抵そう），どの鏡を変更したかによってそのあとのBFSの結果違ってこない？と考えて，その方法でも解き方わからず解説見る．あああ．敗因：BFSで最短求めるのだから，どの鏡でもいい（というか目の前の鏡）という当たり前の事実に気付かない頭の固さ
CarpDay.icon解説見て実装．解説に0-1BFSって書いてあるのに，heapqに4次元積む（しかも1つは文字列）実装してTLE．解説のサンプルコード見てdequeにして0は前から1は後ろから追加する，という0-1BFSの基本をようやく理解する．無事AC．
〇F問題
Kaplam.iconEがぱっと出てこなかったので見に行ったけどDPなんだろうな～って思った程度でわからなかったので戻った
CarpDay.icon 問題の形式的にDP．Counterで同じ数字まとめて，小さい順に追加．入れる数をXとすると，X-DとXが入る位置を二分探索で求めれば，重複組合せでできそう！と思うも，残り時間少なくて諦める．昔作ったことあるから，ライブラリ化しておけば良かった（やり方合っているか分からんけど）．
CarpDay.icon実装してサンプルとって投稿したらWAだらけだったので諦めて解説見る．条件あるのは隣接2項だけで，自分Xより右隣がX-D以上であればいいのに，自分より右のすべての項がX-D以上であると勘違いしていた！やり方はほぼ上のやり方と同じ．残念！
〇G問題