CODE FESTIVAL 2016 qual C : D - Friction
code-festival-2016-qualc.contest.atcoder.jp
当初の方針
- Cが解けなくてこちらに来る
- 部分点解法を狙おう
- うーん、O(H^4)にしかならない・・・
- cost[i][y1][y2]はcost[i][y1-1][y2-1]の一番下しか違いがないことに気づく
- 再利用すればO(H^3)になるぞ
- でも実装がとても重くてバグりそう・・・
- 撤退してCを通すか・・・通せたらこちらを実装しよう
そのままCを通せず、終了
解法を見て
頭いい。このように考察すれば簡単な問題に落とし込めるのはおもしろい。
トポロジカル順序はfor文できれいに書けそうにないので、メモ化再帰で解く。
実装 → 案の上バグらせる
括弧が足りなくて、おかしな挙動をしていた
int[][][] cost = new int[w - 1][h + 1][h + 1]; for (int i = 0; i < w - 1; ++i) { // left for (int j = 0; j < h; ++j) { for (int k = 0; k <= h - 1 - j; ++k) { cost[i][j][0] += field[k][i] == field[j + k][i + 1] ? 1 : 0; } for (int k = 1; k <= h - 1 - j; ++k) { cost[i][j + k][k] = cost[i][j + k - 1][k - 1] - (field[h - 1 - j - (k - 1)][i] == field[h - 1 - (k - 1)][i + 1] ? 1 : 0); } } // right: j = 0のケースはもう計算済みなので注意 for (int j = 1; j < h; ++j) { for (int k = 0; k <= h - 1 - j; ++k) { cost[i][0][j] += field[j + k][i] == field[k][i + 1] ? 1 : 0; } for (int k = 1; k <= h - 1 - j; ++k) { cost[i][k][j + k] = cost[i][k - 1][j + k - 1] - (field[h - 1 - (k - 1)][i] == field[h - 1 - j - (k - 1)][i + 1] ? 1 : 0); } } }
これを、
cost[i][j + k][k] = cost[i][j + k - 1][k - 1] - field[h - 1 - j - (k - 1)][i] == field[h - 1 - (k - 1)][i + 1] ? 1 : 0;
と書いてしまうと、
cost[i][j + k][k] = (cost[i][j + k - 1][k - 1] - field[h - 1 - j - (k - 1)][i]) == field[h - 1 - (k - 1)][i + 1] ? 1 : 0;
となってしまい、基本0が代入されていくことになる。
これに見つけるのに時間を費やしたので、気を付けたい。
直したらACできた。
サンプルで見つけられてよかった部類。
