脳log[20260204]

2026年02月04日 (水) [AtCoder] 先週末にあったらしいデンソークリエイトプログラミングコンテスト2026（ABC443）。都合の悪いことは見ないことでなかったことにできます。■A 問題 Append s。はい。■B 問題 Setsubun。とても難しい。N と K の上限がとても大きい(10 の 8 乗)のを見て全探索を諦めたけど、実は食べた豆の積算は２乗のオーダーで増えていくので何も問題がなかった。本番ではしかたなく 1 年目に N 個食べて、1+t 年目に N+t 個食べるなら、累計は (初項+末項)×項数÷2 だから……と考えていって、でも必要なのは 1+t 年後ではなく t 年後の累計だから t=t-1 を代入して……と補正して、サンプルの答えが１合わないから問題を読み直したら、0 年目に N 個食べるって書いてある！ (初項+末項)の立式からやり直そうとして、実は出てきた答えを単にマイナス１するだけで補正できるなと気が付いて、修正に次ぐ修正でやっとの提出だった。７分かかった。■C 問題 Chokutter Addiction。シミュレートするだけ。３分半。■D 問題 Pawn Line。上に移動させるということは、入力された値(R_i)をマイナス１するということです。実装を終えてからサンプルが合わないことでこれに気がついて、どうやって書き直しをせずに修正するかを考えた。入力された R_i を N+1-R_i に変換するとその他の修正が不要だった。B 問題からこんなんばっか。提出したら TLE。処理内容は、高い山から順番に、左右にある低い山を１低い高さまで引き上げるという処理を繰り返す。山の高さの上限が N なのでプライオリティキューはいらない。全部の高さを処理対象にできる。各駒(山じゃなかった)が処理対象になるのは、初期の高さと、引き上げられた結果の高さの計２回であり、その処理では左右２つの高さを見るだけなので、O(N) であって TLE になる理由がわからなかった。TLE×2 と AC、差分は２バイト×２か所。実は最初に書いたときから、同じ駒が左右の駒から２回参照されてキューに２回登録されることがあるのは知っていた。左右の高さを参照するときに、現在の駒より低い位置にあるかを条件にしていて、現在の駒より２つ以上低い位置にあるかを条件にはしていなかったから。１低い位置にある隣の駒を１低い位置に移動する無駄な操作をキューに入れても害はないと思ってそのままにしていた。どういう入力でこのサボりが２乗のオーダーの計算に繋がるか。最初から操作の必要がない階段状の入力で１、２、３番目の駒が１、２、３回キューに入れられることで全体の処理量が (1+2+3+……+N) = N(N+1)/2 になる。■E 問題 Climbing Silver。BFS でも DFS でもいいからグリッドに結果を書き込んでいくことでグリッドの大きさ(最大で 900 万)に比例した計算量で答えが出せる。しかしとにかく壁破壊がやっかいだった。各列一番下の壁の位置を予め調べておいて、壁破壊ができる状況なら即座に最上段まで壁を破壊して結果を書き込んでしまえば良かった。６分オーバーで提出した #72910971 (WA×26) の間違いは、壁破壊が可能なのはスタート地点(N,C)から連続する左右の範囲に限られると勘違いしたこと。そうではない。壁を縫って到達した遠くの列の下半分が道ばかりだったら、そこでも壁破壊ができる。50 分近くあって時間内に実装しきれなかったうえに勘違いで WA とは何にも惜しくなくて逆に悔しくない。■■■精進。E 問題。提出 #72939980 (AC / 2313 ms)。完全に書き直したこれは行ごとの DP。マス目に４つの状態を持たせた。すなわち、「ゴール未達_道」「ゴール未達_壁」「ゴール到達」「ゴール到達_破壊」。初期状態で壁は ゴール未達_壁 となり、道は ゴール未達_道 となり、スタートマス (N,C) が ゴール到達_破壊 となる。あとは各行各マスで下の行の３マスを参照して、一番下にある壁の位置も{記録/参照}して、if 式が３重の複雑な状態遷移を書いた。Ruby で３桁 ms の爆速で通している人がいて (提出 #72911773)、ビット演算がその秘訣らしい。自分の複雑な遷移がビット演算にできるわけがないから、たぶん２種類の DP を平行してやるという噂の解法が、ビット演算に分解＆合成するのに向いていたのかなと思う。あるいは全然別の解法なのかもしれないけど、一緒でも別でもどちらも知らない解法です。