Hatena::Grouptopcoder

hotpepsiの練習帳

2011-11-14

SRM 523 Div2

03:36

Easy (250) AlphabetPath

問題

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

方針

Medium (500) CountingSeries

問題

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

方針

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成功。

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20111114