ABC149 D - Prediction and Restriction
相変わらずD問題が鬼門で時間内に解けず。難易度的には茶くらい? 今回はシステムに問題があってunratedになるらしい、参戦して初めての経験である。
時間内に提出したのが以下のコード。 提出した段階での方針は
- K個前に同じ手を出していなければ勝てる手を出す
- そうでなければそれ以外の何かしらの手を出す(コードだとあいこにしている
一応方向性としてはDPに近い感じ。
結果的にこの考え方は間違っていて例えば(N=3,K=1)でssp
のときにrss
となるがpに対してsを出せるのはrps
のときだけなのでもうちょっと工夫が必要だった。
Submission #9226702 - AtCoder Beginner Contest 149
上記の問題点を修正して
- K個前(i%k)に出した手と同じ手を出す必要があった場合に別途フラグを立てる
- 前回と同じ手
v.at(i%k) == sc
かつフラグが立っていないvb.at(i%k)
場合は処理をスキップする
という感じに修正したものが以下。
Submission #9231525 - AtCoder Beginner Contest 149
本日の気づき
回答にも書いてあったが貪欲法だと簡潔に書ける。 コードが簡潔だとミスにも気づきやすいしシンプルなコードを心がけたい、 そのためにもこのレベルの問題ならパターンマッチで最適な解法を選べるようになりたい。
インプットとしてnが与えられていると脳死してnでforループ回しがちなんだが一旦落ち着いて網羅できるかつ処理が簡潔になるようなループの仕方を考えたい。(今回でいうとKで回しつつnで回す)