hotpepsiの練習帳

SRM 564

03:41

Div1 Easy (250) KnightCircuit2

問題

• w×hのサイズのチェス盤がある
• 左上からナイトが到達可能な升目の総数を求める

方針

• wとhの小さいほうをa、大きいほうをbとする
• aが1のときは1 (最初の点から動けない)
• aが2のときは(b+1)×2
• aが3のときは...bが3なら8、それ以外はa×b
• aが4以上のときはa×b
• 提出
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_564/KnightCircuit2.cpp

Div1 Medium (500) AlternateColors2

問題

• R、G、Bの三色のボールが、合計N個かある
• ボールをR、G、Bの順番で破壊するロボットがいる
• K番目のボールはRであるとき、ボールの個数の組み合わせの総数を求める

方針

• 最大で3色使えて、使える色は減っていくこともある
• 色は順番に選ばれる。存在しない色は飛ばされる
• DPかな
• (終了後)
• dp[x番目][使える色のビットマスク][終端の色]
• K番目の場合だけRしか処理しない
• 色がなくなるときに場合わけしてカウントを増やす
• すごく面倒な感じに書けた
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_564/AlternateColors2.cpp

結果

o-- 204.77pt 382nd rating 1250 -> 1302 (+52)

場合わけとか判定が入るやつは苦手。3×3はたまたま気づいたが落としてもおかしくなかった。

同室の診断人さんには負けてしまったが、200点取れたのでなかなか良かった。

提出後いまいち自信がなかったので総当りの関数を書いて比較したら、そっちがバグっていて時間を食った。

mediumは力技で何とか解いた。DP力は多少上がっていると思う。

場合の数など、これ以外の方法で解いているコードは理解できなかった。