Hatena::Grouptopcoder

minus9dの記録

2012-03-24

Round #113 (Div. 2)

| 20:57 | Round #113 (Div. 2) - minus9dの記録 を含むブックマーク はてなブックマーク - Round #113 (Div. 2) - minus9dの記録

3つの撃墜に成功し自己最高順位(45位)。o-o-o。R1523→R1654(+131)。

A. Rank List

スコア = 解いた問題数 * (十分大きな数) - 経過時間数

というスコアを定義してソートすると簡単に順位付けができる。

A.のPretestが意地悪で、「解いた問題数が同じ場合は経過時間数が大きいほど良い順位」という風に問題文を誤読した人でもAcceptされるようになっていた。この誤りを犯しているコードを見つけて3つ撃墜。

http://codeforces.com/contest/166/submission/1390322

C. Median

  • ret = 0
  • 与えられた配列の中にxが入っていない場合は、xを配列の末尾に加え、++ret。
  • 配列をソート。
  • 配列の中間値がxに等しくなるまで、配列の先頭、または末尾に要素を挿入し、++ret。
    • 実際に要素を挿入する必要はない。配列の中で、値がxに等しいindexの範囲を管理しさえすればよい。
  • return ret

http://codeforces.com/contest/166/submission/1392758

E. Tetrahedron

Aから長さnのパスを通ってAに戻ってくる場合の数
= Bから長さn-1のパスを通ってAに到達する場合の数
+ Cから長さn-1のパスを通ってAに到達する場合の数
+ Dから長さn-1のパスを通ってAに到達する場合の数

と再帰できる。また

Aから長さnのパスを通ってBに到達する場合の数
= Bから長さn-1のパスを通ってBに戻ってくる場合の数
+ Cから長さn-1のパスを通ってBに到達する場合の数
+ Dから長さn-1のパスを通ってBに到達する場合の数

と再起できる。すべての頂点から他の頂点へ移動できるので対称性があることに注意すると、

dp[n][0] = ある頂点から長さnのパスを通って同じ頂点に戻ってくる場合の数
dp[n][1] = ある頂点から長さnのパスを通って異なる頂点に到達する場合の数

と定義したとき

dp[i][0] = 3 * dp[i-1][1];
dp[i][1] = dp[i-1][0] + 2 * dp[i-1][1];

と漸化式が書けることが分かる。後はmodをとればOK。他のコードを見ていて、配列にする必要はなかったと気付いた。メモリを157900 KB消費していて危なかった。

余談だが、Pythonで同様のコードを書くとnが大きいときTLEしてしまうらしい。こういう話を聞くと動的言語は怖いなと思ってしまう。

http://codeforces.com/contest/166/submission/1394197

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/minus9d/20120324
リンク元