脳log[20251108]

2025年11月08日 (土) [AtCoder] 今日はトヨタシステムズプログラミングコンテスト2025（ABC431）があった。■A 問題 Robot Balance。頭でっかちはダメです。■B 問題 Robot Weight。N 種類のパーツを付けたり外したり。なんかせこい方法ないかなって考えて思いつかなかったから 01 配列を別に持ったんだけど、重さの値を -1 倍しながら足せば良かったんかな。■C 問題 Robot Factory。A 問題の発展。重いボディ K 個と軽い頭 K 個の一意な組み合わせ。これを実装するにあたり、ソート列から重い K 個と軽い K 個を取り出すメソッド(shift/pop)を取り違え、頭と体を比較する演算子の向きを間違えるのが自分です。■D 問題 Robot Customize。B 問題の発展。DP をしたいけど状態をどうするか。頭の重さに対して頭に取り付けたパーツとボディに取り付けたパーツの嬉しさの合計の最大を記録した。頭に取り付けなかった時点でそれはボディに取り付けることが決定しているのでその嬉しさを即座に合算してしまって総合的な優劣を比較すれば良い。しかしこれは TLE×3 だった。計算量を見積もってみると、N=500, sum(W)=500*500 のとき、ループ全体で 500 の３乗(=１億2500万)。頭の重さの最大が sum(W)/2 なのでざっくり半分にして 6250万。これは Ruby には厳しい。ここで見かたを変えて、ボディに取り付けた場合の嬉しさはただで手に入る嬉しさであり、頭に取り付ける場合は重さにハンデを抱えるけどボディに取り付けた場合の嬉しさにさらに嬉しさを付け加える行為だと考えた。そうするとボディに取り付ける場合の嬉しさは必ず得られるベースラインなのでいちいち計算して比較する必要がなくなる。頭に取り付ける場合の嬉しさはボディに取り付ける場合よりどれだけ大きいかで評価されるので、そもそもボディに取り付けた場合より嬉しさが低いなら頭に取り付ける理由がないとわかってループが省略できる。よく知らない用語を雰囲気で使って説明すると、２か所からもらう DP をしていたものが１か所からもらうだけで済むようになった。実際の計算量は入力の傾向に依存するような気もするけれど、これらでおよそ半分に時間が節約できて AC になった (#70786365)。他の言語では必要のない苦労だったかもしれない。入力の傾向に関係なく状態空間のサイズ(と遷移)に応じた決まった時間で答えが出るのが DP であるので、何をやってもそれは定数倍の改善か入力依存のアドホックな改善でしかない。■E 問題 Reflection on Grid。同配点の F 問題も一応読んだ。トポロジカルソート的な感じで場合の数を数えたいけど「徒競走」に比べて制約が大きすぎる。見込みがないと思って E 問題に専心した。その E 問題。重実装の気配がビンビンしています。それどころか実装に取りかかれない。これは頭を使う必要があるなと一度立ち止まって考えることにした。盤面のマスの数が多すぎるので１マス１マスああしてこうしてと試行錯誤することができない。１か所変更してみた結果青木君に光が届くかが即座にわかると仮定してみたら答えられるだろうか。たとえば初期盤面の経路の１マス目を変更して結果を見る。ダメなら１マス目はそのままにして２マス目を……。これの何がダメか。盤面の外に飛び出さない限りおよそどんな経路を選んでも青木君にはたどりつく。ただし操作手順が増える。操作手順の少なさが問われているのに手数を度外視した解法はいけない。方向を加味して盤面を４倍した状態を持つということは考える前から決まっていた。BFS をしたいですね？ 手探りで書いているこれは 01BFS ですか？ 提出 #70805678 (AC)。１時間あっても完成しなかったからこれは終了後の提出。鏡の向きの変更を記録して考慮しないでいいのはなぜか。一度鏡の向きを変更して進路を変えたマスに紆余曲折の末再進入するケースを考える。鏡の向きを変更することで３方向どれでも好きな進路を選べるわけだけど、過去に左から入ってどこかへ出て行っていた場合、再進入して左以外のどこかへ出て行くケースは紆余曲折を省いて最初の進入時にそこへの進路を選んでいたことにすればいい。左側に出て行きたいときは？ 他の経路を通って初めての進入が左側以外になったときに考えましょう(そのように取り扱えるようになっています。そしてどんな紆余曲折をたどっても U ターンして左方向へ出ていく経路はないのでこれ以外のケースは想定しません)。