Google Code Jam 2012 1B Tide Goes In, Tide Goes Out

参加録

今年はCode Jam参加しない予定でした。予選のとき旅行に行っていたので。しかしホテルでネットが使えるand友人がPC持ってきていたおかげで予選に参加できました。なんとか予選を通過しRound 1です。Round 1Aは解けた問題数的にはよかったのですが、バグにはまり時間的なペナルティで通過できませんでした。Round 1Bは2small、1large解いて何とか通過できました！去年は1Cでの通過だったので、この一年間の成長が確認できました。

問題概要

で、タイトルにある問題です。地下の洞窟でカヤックをしています。潮が満ちてきて閉じ込められました。しばらくすると潮が引き始めるので、潮が引き始めてから移動した場合、最短で何秒で洞窟の外にでれるでしょうか？洞窟の状態は地図で与えられます。

方針

現地点からゴールまでの最短パスを求める。条件が少し複雑なので注意。あと小数の演算があるので丸め誤差にも注意。

反省

「ある潮の高さにおいてある地点から別の地点に移動できるかどうか」という思考パターンでいったのが、実装を困難にした原因。移動している時間の間に潮の高さ変わってしまうので、状態数が（現在の潮の高さ、現在の場所）みたいな感じになって、これTLE厳しくないかとか思って変なDP書いたりしてた。
　まず最初にある時刻にある地点から別の地点に移動できるかを２つの条件に分割するべきだった。

1. 潮が引いてしまったときにその移動は可能か？
2. 1.が可能なら潮が少なくともどこまで引けばいいのか？

1. は時間に依存しない静的な条件です。２つのセルの形状に応じて一意に決まります。そして1.が可能だったときに、2.の時間を計算します。ある時刻tにおいて(x1, y1)から(x2, y2)に移動可能なとき、時刻u >= tにおいても移動可能となるので、そもそも状態数の中に潮の高さとかいらなかった。。うーん多分問題をきちんと把握できていなかったのだろうか。Sample Caseの下にある説明をちゃんと読んで紙と鉛筆をつかってシミュレーションしてみるべきだった。時間には余裕があったのだから。

練習でACしたソースコード

view plainprint?

1. #define REP(i, n) for(int i=0; i<(int)(n); i++)  
2. #define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)  
3.   
4. typedef pair<double, pair<int, int> > Pr;  
5.   
6. const int dx[] = {-1, 0, 1, 0};  
7. const int dy[] = {0, 1, 0, -1};  
8. const double INF = 1e100;  
9. const double EPS = 1e-4;  
10.   
11. int H, N, M;  
12. int clg[128][128];  
13. int flr[128][128];  
14. double dist[128][128];  
15.   
16. double enterTime(int x1, int y1, int x2, int y2) {  
17.     if (flr[x1][y1] > clg[x2][y2]-50)  
18.         return INF;  
19.     if (flr[x2][y2] > clg[x2][y2]-50)  
20.         return INF;  
21.     if (flr[x2][y2] > clg[x1][y1]-50)  
22.         return INF;  
23.     if (H <= clg[x2][y2]-50)  
24.         return 0;  
25.   
26.     return (H - (clg[x2][y2]-50)) / 10.0;  
27. }  
28.   
29.   
30. double solve() {  
31.     REP(i, N) REP(j, M) dist[i][j] = INF;  
32.   
33.     priority_queue<Pr, vector<Pr>, greater<Pr> > Q;  
34.     Q.push(make_pair(0, make_pair(0, 0)));  
35.     dist[0][0] = 0;  
36.   
37.     while (!Q.empty()) {  
38.         double t = Q.top().first;  
39.         int x = Q.top().second.first;  
40.         int y = Q.top().second.second;  
41.   
42.         Q.pop();  
43.         if (t > dist[x][y])  
44.             continue;  
45.         if (x == N-1 && y == M-1)  
46.             break;  
47.   
48.         REP(k, 4) {  
49.             int xx = x + dx[k];  
50.             int yy = y + dy[k];  
51.   
52.             if (xx < 0 || xx > N-1 || yy < 0 || yy > M-1)  
53.                 continue;  
54.   
55.             double u = max(t, enterTime(x, y, xx, yy));  
56.   
57.             if (u == 0.0)  
58.                 ;  
59.             else if (H-10*u-flr[x][y] + EPS >= 20)  
60.                 u += 1.0;  
61.             else  
62.                 u += 10.0;  
63.   
64.             if (u < dist[xx][yy]) {  
65.                 dist[xx][yy] = u;  
66.                 Q.push(make_pair(u, make_pair(xx, yy)));  
67.             }  
68.         }  
69.     }  
70.   
71.     return dist[N-1][M-1];  
72. }  
73.   
74. #define SUBMIT  
75. int main() {  
76. #ifdef SUBMIT  
77.     freopen("./test.in", "r", stdin);  
78.     freopen("./test.out", "w", stdout);  
79. #endif  
80.   
81.     int T;  
82.     cin >> T;  
83.   
84.     REP(t, T) {  
85.         cerr << "solving #" << t+1 << "..." << endl;  
86.         cin >> H >> N >> M;  
87.         REP(i, N) REP(j, M) cin >> clg[i][j];  
88.         REP(i, N) REP(j, M) cin >> flr[i][j];  
89.         double ret = solve();  
90.         printf("Case #%d: %.16lf\n", t+1,ret);  
91.     }  
92.   
93.   
94. #ifdef SUBMIT  
95.     fflush(stdout);  
96.     cerr << "all done!" << endl;  
97. #endif  
98.     return 0;  
99. }  

#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)

typedef pair<double, pair<int, int> > Pr;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const double INF = 1e100;
const double EPS = 1e-4;

int H, N, M;
int clg[128][128];
int flr[128][128];
double dist[128][128];

double enterTime(int x1, int y1, int x2, int y2) {
    if (flr[x1][y1] > clg[x2][y2]-50)
        return INF;
    if (flr[x2][y2] > clg[x2][y2]-50)
        return INF;
    if (flr[x2][y2] > clg[x1][y1]-50)
        return INF;
    if (H <= clg[x2][y2]-50)
        return 0;

    return (H - (clg[x2][y2]-50)) / 10.0;
}


double solve() {
    REP(i, N) REP(j, M) dist[i][j] = INF;

    priority_queue<Pr, vector<Pr>, greater<Pr> > Q;
    Q.push(make_pair(0, make_pair(0, 0)));
    dist[0][0] = 0;

    while (!Q.empty()) {
        double t = Q.top().first;
        int x = Q.top().second.first;
        int y = Q.top().second.second;

        Q.pop();
        if (t > dist[x][y])
            continue;
        if (x == N-1 && y == M-1)
            break;

        REP(k, 4) {
            int xx = x + dx[k];
            int yy = y + dy[k];

            if (xx < 0 || xx > N-1 || yy < 0 || yy > M-1)
                continue;

            double u = max(t, enterTime(x, y, xx, yy));

            if (u == 0.0)
                ;
            else if (H-10*u-flr[x][y] + EPS >= 20)
                u += 1.0;
            else
                u += 10.0;

            if (u < dist[xx][yy]) {
                dist[xx][yy] = u;
                Q.push(make_pair(u, make_pair(xx, yy)));
            }
        }
    }

    return dist[N-1][M-1];
}

#define SUBMIT
int main() {
#ifdef SUBMIT
    freopen("./test.in", "r", stdin);
    freopen("./test.out", "w", stdout);
#endif

    int T;
    cin >> T;

    REP(t, T) {
        cerr << "solving #" << t+1 << "..." << endl;
        cin >> H >> N >> M;
        REP(i, N) REP(j, M) cin >> clg[i][j];
        REP(i, N) REP(j, M) cin >> flr[i][j];
        double ret = solve();
        printf("Case #%d: %.16lf\n", t+1,ret);
    }


#ifdef SUBMIT
    fflush(stdout);
    cerr << "all done!" << endl;
#endif
    return 0;
}