hotpepsiの練習帳

SRM 523 Div2

03:36

Easy (250) AlphabetPath

問題

• AからZまでが1文字ずつ書かれた迷路がある。
• AからZまでたどれるかどうかを求める。

方針

• 処理時間は十分あるので、ループで回すことにした
• 次の文字の位置を(x',y')として、|x-x'|+|y-y'|が1かどうか見る
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_523/AlphabetPath.cpp

Medium (500) CountingSeries

問題

• 1以上の数a,b,c,d,upperBoundが与えられる。
• 1からupperBoundまでの間でa+b*xとc*d^yのいずれかを満たす数の個数を求める。

方針

• a+b*xの方の数を求めておく
• c*d^yの方は、1回ずつかけて、a+b*xを満たすか調べる
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_523/CountingSeries.cpp

Hard (1000) SmallBricks31

問題

• 1x1x1、1x1x2、1x1x3の3種類のブロックがある。
• ブロックの上には1x1x1のブロックを積むことができる。
• 連続する2ブロックの上には1x1x2のブロックを積むことができる。
• 連続する3ブロック、または、1個あけた2ブロックの上には1x1x3のブロックを積むことができる。
• 幅と高さが与えられる。ブロックの積み方が何通りあるかをmod 1000000007で求める。

方針

• 素晴らしい問題。書けず。
• LayCurseさんのコードでやっと理解。
• 1段上になったときに、どのパターンがいくつになるか、というのをテーブルで持つ
• 一つもおかないやつも1通りと数える
• 置かない場合、それぞれのブロックを置いた場合でテーブルを生成
• H回ループでまわす

結果

ox- 239.30+50 rating 1146 -> 1179

a>upperBoundを考慮しなかったため死亡。甘い。

その後、他の人のを見て気づいてchallenge成功。