- 2008-11-13 (木) 3:43
- TopCoder
Rating: 1918 → 1915
レート少し落ちました．前回200あがっているのでまだ良いですが，次はがんばりたいところ．
TopCoder SRM 425, DIV I, 250, CrazyRobot
Overview
東西南北それぞれ移動する確率が与えられる．同じマスを二度踏まない確率を求めよ．
Comment
最初DP的な何かを考えてしまってそれではまり込み時間をロスすることに．結局後回しにしたので残念なことに90点ほどしかとれなかった…orz．解法は純粋に深さ優先の全探索です．
001: struct CrazyBot {
002: int a[30][30];
003: double de, dw, ds, dn;
004: double prob(int k, int x, int y) {
005: if (a[x][y]) return 0;
006: if (k == 0) return 1; k--;
007: a[x][y] = 1;
008: double p = prob(k, x - 1, y) * dw
009: + prob(k, x + 1, y) * de
010: + prob(k, x, y - 1) * dn
011: + prob(k, x, y + 1) * ds;
012: a[x][y] = 0;
013: return p;
014: }
015:
016: double getProbability(int k, int e, int w, int s, int n) {
017: de = e / 100.0, dw = w / 100.0,
018: ds = s / 100.0, dn = n / 100.0;
019: rep(i, 30) rep(j, 30) a[i][j] = 0;
020: return prob(k, 14, 14);
021: }
022: };
002: int a[30][30];
003: double de, dw, ds, dn;
004: double prob(int k, int x, int y) {
005: if (a[x][y]) return 0;
006: if (k == 0) return 1; k--;
007: a[x][y] = 1;
008: double p = prob(k, x - 1, y) * dw
009: + prob(k, x + 1, y) * de
010: + prob(k, x, y - 1) * dn
011: + prob(k, x, y + 1) * ds;
012: a[x][y] = 0;
013: return p;
014: }
015:
016: double getProbability(int k, int e, int w, int s, int n) {
017: de = e / 100.0, dw = w / 100.0,
018: ds = s / 100.0, dn = n / 100.0;
019: rep(i, 30) rep(j, 30) a[i][j] = 0;
020: return prob(k, 14, 14);
021: }
022: };
TopCoder SRM 425, DIV I, 500, PiecesMover
Overview
5×5の盤面に点が5個以下ある．それを一つ隣に移動するのにコスト1がかかる．全てが隣接するには最低どれだけのコストが必要か．
Comment
ライブラリそのままひっぱってDijkstraで解けばとりあえずどうにかなった．しかし他の人を見る限り普通の幅優先が主流かな？（まぁ当たり前だけど）私のライブラリだと辺書くだけで楽ができるので使っただけです．とりあえず以下のコードを書いて350点ほど貰った．
001: #include "dp_dijkstra.h"
002:
003: struct PiecesMover: public dp_dijkstra<int, int> {
004: void pt(int &n, int x, int y) {
005: if (n & (1 << (y * 5 + x))) {
006: n ^= 1 << (y * 5 + x);
007: if (0 < x) pt(n, x - 1, y);
008: if (x < 4) pt(n, x + 1, y);
009: if (0 < y) pt(n, x, y - 1);
010: if (y < 4) pt(n, x, y + 1);
011: }
012: }
013:
014: map<int, int> edge(int n) {
015: map<int, int> ret;
016: // 終了ノードからは辺を出さない
017: if (n == -1) return ret;
018: // 終了状態の確認
019: rep(i, 25) if (n & (1 << i)) {
020: int m = n; pt(m, i % 5, i / 5);
021: if (m == 0) return ret[-1] = 0, ret;
022: break;
023: }
024: // 次の状態のリストを生成する
025: rep(i, 25) if (n & (1 << i)) {
026: int m = n ^ (1 << i);
027: int x = i % 5, y = i / 5;
028: if (0 < x) ret[m | (1 << (i - 1))] = 1;
029: if (x < 4) ret[m | (1 << (i + 1))] = 1;
030: if (0 < y) ret[m | (1 << (i - 5))] = 1;
031: if (y < 4) ret[m | (1 << (i + 5))] = 1;
032: ret.erase(m);
033: }
034: return ret;
035: }
036:
037: int getMinimumMoves(vc<str> b) {
038: int n = 0;
039: rep(y, 5) rep(x, 5) if (b[y][x] == '*')
040: n |= 1 << (y * 5 + x);
041: solve(n);
042: return d[-1];
043: }
044: };
002:
003: struct PiecesMover: public dp_dijkstra<int, int> {
004: void pt(int &n, int x, int y) {
005: if (n & (1 << (y * 5 + x))) {
006: n ^= 1 << (y * 5 + x);
007: if (0 < x) pt(n, x - 1, y);
008: if (x < 4) pt(n, x + 1, y);
009: if (0 < y) pt(n, x, y - 1);
010: if (y < 4) pt(n, x, y + 1);
011: }
012: }
013:
014: map<int, int> edge(int n) {
015: map<int, int> ret;
016: // 終了ノードからは辺を出さない
017: if (n == -1) return ret;
018: // 終了状態の確認
019: rep(i, 25) if (n & (1 << i)) {
020: int m = n; pt(m, i % 5, i / 5);
021: if (m == 0) return ret[-1] = 0, ret;
022: break;
023: }
024: // 次の状態のリストを生成する
025: rep(i, 25) if (n & (1 << i)) {
026: int m = n ^ (1 << i);
027: int x = i % 5, y = i / 5;
028: if (0 < x) ret[m | (1 << (i - 1))] = 1;
029: if (x < 4) ret[m | (1 << (i + 1))] = 1;
030: if (0 < y) ret[m | (1 << (i - 5))] = 1;
031: if (y < 4) ret[m | (1 << (i + 5))] = 1;
032: ret.erase(m);
033: }
034: return ret;
035: }
036:
037: int getMinimumMoves(vc<str> b) {
038: int n = 0;
039: rep(y, 5) rep(x, 5) if (b[y][x] == '*')
040: n |= 1 << (y * 5 + x);
041: solve(n);
042: return d[-1];
043: }
044: };
Comments:0
Trackbacks:0
- Trackback URL for this entry
- http://imoz.jp/2008/11/topcoder-srm-425/trackback/
- Listed below are links to weblogs that reference
- TopCoder SRM 425 from 超現実いもす(imos)の日記