脳log[20230802]

2023年08月02日 (水) [AtCoder] 精進。ARC010-C「積み上げパズル」(黄 diff)。色ボーナスもコンボボーナスも全色ボーナスもマイナスになりうるのがゲームのルールとして直感に反する。でも DP をするならそこは問題にならない。DP 配列を埋める初期値にだけ注意したらあとの遷移では比較して大きい方をとるだけ。どういう DP をするか。コンボボーナスを加算するために最後に積んだ色が何色かで M 通りに分類する。全色ボーナスを加算するためにこれまでにどの色を使ったかを 2^M 通りのビットフラグで分類する。M の上限が 10 なので組み合わせた状態数が最大で 10240 通りになる。遷移の回数 N が 5000 以下だからおおよそ 5000 万の処理量は Ruby には厳しいかと思ったけど、テストケースが制約の上限を攻めていないのか処理時間には余裕があった。定数倍２分の１のために必ず立っている１ビットを効率的に省略する方法を考えていたけど必要なかった。■WA×41、WA×18、WA×3 のち AC。■41→18 で解消したバグは、色ボーナスとして加算する値が落ちてきたブロックではなくすでに積まれている一番上のブロックの色によって決まっていたうっかりミス(21 行目)。■18→3 で解消したバグは、ブロックが１つも積まれていない状態(スコア０)が存在していなかったこと。■3→AC で解消したバグは、それまではちゃんと対策できていたのに他のバグを解消したときに不要になった気がして省略した処理がやっぱり必要だったために生じた新しいバグで、最初のブロックの扱いをどうするかに関わること。色数 M が１より大きいなら特別扱いは必要なくて、他の色の空の状態(スコア０)から遷移してくることでコンボボーナスなしの色ボーナスだけを加算することができる。しかし使われている色が１色だけのときに特別扱いなしでは最初のブロック(コンボボーナスなしの色ボーナスだけ)がうまく扱えていなかった。M+1 色目が追加できたらややこしいことは何もなかったけど、TLE が怖くて１ビットだって削りたかったときにそれは取れない選択肢。