脳log[20260208]

2026年02月08日 (日) [AtCoder] 今日は AtCoder Regular Contest 214。■A 問題 Same Sum Grid Path。分かれてすぐに合流する最少の４マスを考えると、あるマスの右と下が同じ数字でないといけないとわかる。４マス１単位をオーバーラップさせながら視野を広げると、スタートから等距離にあるマスが同じ値を持っていないといけないとわかる。そこまでやるならどのパスも同じ値を持つとわかる。実装ミスでペナルティを１回出しながら 18 分で AC。まあ 300 点問題なので (かなり遅い)。■B 問題 Missing Number in Graph。１からのパスを考えると、各頂点の番号と頂点１の番号との２つの値の XOR が N-1 個わかる。この N-1 個の値から頂点１の値がわかるだろうか。しばらくわからなくて N-1 個の XOR された値を眺めていた。それらの数字の中には N を超える値もある。たとえば N=4 だとして 3^4 = 7 なので頂点１の値が３か４ならそういうこともある。そういうのをヒントにして候補を絞りながら現実的な時間で頂点１の値を探索できるだろうか。N を超えてはみでたビットが M 種類あるなら 1<<M 通りの探索をして許されるだろうか。ダメっぽい。うーん。ここでちょっと飛躍をして、N-1 個の値全部の XOR を計算してみた。サンプルの３ケース目だから N=4 で、３つの値の XOR で、これは頂点１の値を含む４個の値の XOR と同じということになる。３個の値には頂点２と３と４の値と、奇数個の頂点１の値が含まれているから、そうなる。これと１から N までの N 個の値の XOR (０からの N+1 個の値の XOR でもいいけど同じこと)と XOR を取ると、食べられた数があぶり出されてくる。次は N が奇数の場合。サンプルの２ケース目がそうだけど N=1 でありあまり一般的なケースではない。同じ手法で N-1 個の値の XOR を計算したとき、偶数個の頂点１の値が相殺されて頂点１の値が消えてしまうから、あぶり出されてくるのは２つの値の XOR となり、そのどちらの値も頂点１の値として有効なので確定できない。-1 で良さそう？ 他に確定する助けになる情報や方法はない？ 投げたら AC だったので結果オーライ。■D 問題 Distinct Sum Grid Path。A 問題と同じ見た目。N<=13 だけど「全て 6000000 以下である」が難しい。電気毛布をオンにしたお布団があったかくて寝落ちしているあいだに終わっていました。今日は積もる勢いで一日中雪が降っていて帰り道が怖かった。信号で止まろうとしている車が黒い地面をひっかきながら 30 cm ほど滑って前の車にゆっくり迫っていくのが見えた。ノーマルタイヤのこの自転車ならどうなる。白い歩道がサクサク音を立てている。■自分のすべての提出。コンテスト成績証。AB どちらも灰 diff で(ABC の diff と ARC の diff はそのまま比較できない印象)、茶パフォもありうるかと思ったけど、意外に昨日と同じような結果だった。つまり良くはない(「ぼちぼち」)。実際の diff は知らないけど、簡単な問題しか解けないのが自分です。