FC2ブログ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

SR 147 DIV1 Dragons

6面体の上のそれぞれの平面に住んでる6匹のドラゴンは、腕を4つもっている。そして1回の戦いで、接している4側面のドラゴンが持っている食料を4分の1ずつ取ってくる。食料の初期値と、戦う回数Nを与えられたとき、あるドラゴンの最終時点での食料の量を求めろという問題。


他の人の回答読んでて、目からうろこが出まくった pieguy という人のソースを転記。


スポンサーサイト

SRM 400 DIV1 Refersal Chain

0と1で構成されたある文字列のi番目からj番目を反転(配列の並びを逆転)させて、目的の文字列にすることは可能か?可能ならば最小の反転回数を、不可能ならば-1を返せ、という問題。
ただし反転操作reverse(i,j)のi,jにはi0<=i1...im, j0>=j1...jm、という制限が付く。

最初は幅優先で探索した。そちらでも通った。がDPが想定回答らしい。

d[L][I][J][R] は ( R ? init.substr(I,L) : reverse(init.substr(I,L)) ) と goal.substr(J,L) を一致させる反転回数。

xyz と abc を一致させるための回数は
1) x == a なら yz と bc の一致回数
2) x == c なら yz と ab の一致回数+1
3) z == a なら xy と bc の一致回数+1
4) z == c なら xy と ab の一致回数
になる。



なにか余分な気がする。

SRM 384 DIV2 1000 PowerGame

典型的(?)な石取りゲーム。動的計画法。
山からn^2個の石(石というか棒)を取っていき、取れなくなったほうが負け(0個にしたほうが勝ち)というルール。
山が2つあるけど、それぞれの山で任意の個数を取ることが出来るので余り関係ない。
状態は「d[残っている石の数] = 終了までのターン数」。

SRM 400 DIV1 250 StrongPrimePower

ある数値nが与えられるので、n = p^q かつ p が素数となる p,q を求めよ、という問題。q > 1という条件と、2 <= n <= 10^18 という条件がある。
nの最大値が10^18だったので、エラトステネスのO(N^0.5)でもメモリも時間も足らんから数論かと思ってすぐ諦めた。が、答えをみると全然数論じゃなかった。情けない。
解法は大別して下の2種類。

■解法その1
p^2 となるパターンを先に検証すればあとは p^q (q>=3) だけになる。
そうするとpが検証可能な値になるので普通に判定するだけ。



■解法その2
pow。検証(s!=n)のときforでまわしてsを求めてるのはpow(p,q)にしたら最後のテストケースが通らなかったため。解法その1のL65をみるに、両方long doubleにしてしまえば問題ないっぽい。本番じゃ精度が怖くて書きたくないかも。

TopCoder SRM466 div2

■LotteryTicket
4種類の通貨の組み合わせで指定された金額のチケットが買えるかどうか判定する問題。
全パターンを直にコーディングか、フラグか、再帰の3パターンが多かった。

■LotteryCheating
チケットを当たりにするまでに何回書き換えればいいかを計算する問題。当たりの条件は、「全部0」「約数の個数が奇数」の2つ。
約数の個数が奇数になるのは平方数のときだけらしい。知識問題。
wikipeida 約数#約数の個数
検索フォーム
ユーザータグ

ICPC 2009 国内予選 ゲームプログラミング 

カテゴリ
最新記事
月別アーカイブ
最新コメント
最新トラックバック
リンク
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。