AtCoder Grand Contest 002：B - Box and Ball
問題
https://atcoder.jp/contests/agc002/tasks/agc002_b
考え方
実験？？実験のコツがわかるようになりたい...。
赤いボールが入っている箱から 回の操作によって到達できる可能性がある箱については赤いボールが入りうる。ただし操作後に操作元の箱 x が空になる場合はその箱には赤いボールが入っていることはない。
これをシミュレーションすればよい。
Submission #4351818 - AtCoder Grand Contest 002
到達可能性について、editorialにように言われればまぁ理解できるが、なかなかぱっと正当性がわからない...。ちなみに以下が実験したコードというかぱっと思いついたdp解...実験用コード
public void solve(int testNumber, MyInput in, PrintWriter out) {
int n = in.nextInt(), m = in.nextInt();
// i 回目の操作で箱 j に赤いボールが r 個、白いボールが b 個入っている可能性があるかどうか
boolean[][][][] dp = new boolean[m+1][n][n+1][n+1];
for (int i = 0; i < n; i++) {
dp[0][i][i == 0 ? 1 : 0][i != 0 ? 1 : 0] = true;
}
for (int i = 0; i < m; i++) {
int x = in.nextInt()-1, y = in.nextInt()-1;
// 赤いボールと白いボールがある場合
boolean done = false;
for (int r = 1; r <= n; r++) {
for (int w = 1; w <= n; w++) {
if (dp[i][x][r][w]) {
// 赤いボールを渡す場合
for (int r2 = 0; r2 <= n; r2++) {
for (int w2 = 0; w2 <= n; w2++) {
if (dp[i][y][r2][w2]) {
dp[i+1][y][r2+1][w2] = true;
dp[i][x][r][w] = false;
dp[i+1][x][r-1][w] = true;
}
}
}
// 白いボールを渡す場合
for (int r2 = 0; r2 <= n; r2++) {
for (int w2 = 0; w2 <= n; w2++) {
if (dp[i][y][r2][w2]) {
dp[i+1][y][r2][w2+1] = true;
dp[i][x][r][w] = false;
dp[i+1][x][r][w-1] = true;
}
}
}
done = true;
}
}
}
// 赤いボールしかない場合
if (!done) {
for (int r = 1; r <= n; r++) {
if (dp[i][x][r][0]) {
// 赤いボールを渡す場合
for (int r2 = 0; r2 <= n; r2++) {
for (int w2 = 0; w2 <= n; w2++) {
if (dp[i][y][r2][w2]) {
dp[i+1][y][r2+1][w2] = true;
dp[i][x][r][0] = false;
dp[i+1][x][r-1][0] = true;
}
}
}
done = true;
}
}
}
// 白いボールしかない場合
if (!done) {
for (int w = 1; w <= n; w++) {
if (dp[i][x][0][w]) {
// 白いボールを渡す場合
for (int r2 = 0; r2 <= n; r2++) {
for (int w2 = 0; w2 <= n; w2++) {
if (dp[i][y][r2][w2]) {
dp[i+1][y][r2][w2+1] = true;
dp[i][x][0][w] = false;
dp[i+1][x][0][w-1] = true;
}
}
}
}
}
}
if (!done) new RuntimeException();
// 直前の状態のマージ(移動しなかった分)
for (int j = 0; j < n; j++) {
if (j == y) continue;
for (int r = 0; r <= n; r++) {
for (int w = 0; w <= n; w++) {
dp[i+1][j][r][w] |= dp[i][j][r][w];
}
}
}
}
// m回操作後の最終的な状態で赤いボールが入っている可能性がある箱の数を数える
int ans = 0;
for (int i = 0; i < n; i++) {
boolean ok = false;
top:
for (int r = 1; r <= n; r++) {
for (int w = 0; w <= n; w++) {
if (dp[m][i][r][w]) {
ok = true;
break top;
}
}
}
if (ok) ans++;
}
out.println(ans);
}
どこに着目して考察するべきだったか
実験をすると分かる
何がバグっていたか
得た知見(典型ポイント)
- 実験して法則を見出す
- シミュレーション
