JAG 夏合宿 2014 Day4 E - AI 解説＋裏話
はじめに
この記事は Competitive Programming （その2） Advent Calendar 2015 5日目の記事です．
1年半にわたって，自分が担当していた問題の解説を放置していたのでこの機会に書きます．
あと，単純に解法書くだけだとさみしい気がするので，作問体験記ということで，作問時の裏話も書きます．
問題
- コンテスト: JAG 夏合宿 2014 Day4
- 問題文: AI | Aizu Online Judge
- 作問，解説: @mitaki28
- テスター: @ustimaw
解法
- この問題のプログラムにおいて，条件判定の結果はロボットの位置と向きにのみ依存します．
- つまり，ロボットの位置と向きが全く同じ状態でプログラム中のある文が2回実行された場合，ロボットは以後，同じ動作を無限に繰り返すことがわかります．
- サンプル3でロボットがどう動くのか試してみるとわかると思います．
- したがって，(ロボットのx座標)×(ロボットのy座標)×(ロボットの向き)×(プログラム中で実行中の文)について，1度発生した状態をすべて記憶していき，同じ状態に2回到達した時点でゴールに到達不可能なものとすることで解くことができます．
- 計算量は $O(hw|s|)$ となり，状態数は高々 $50 \times 50 \times 4 \times 1000=10000000$ で解けます．
- 状態数の上限がわかっているので，10000000ステップ回してゴールに到達しなかったら諦めるとかでも解けます．
- ただし，単純に動作文の数だけ数えていると後述する空のプログラムのパターンでTLEするため注意が必要です．
実装上の注意
- if 文や while 文については条件によってプログラムを対応する括弧まで読み飛ばす必要があります．毎回，対応する括弧を見つけても良いですが，前処理で対応する括弧を計算しておくと，多少実装が楽になるかもしれません．
- 同じ状態に到達したかどうかの判定は，条件文の中で行う必要があります．動作文で判定した場合，while 文中のプログラムが空の場合に無限ループが発生してしまいます．以下のケースでTLEしている人が多かったです．
5 3 ### #g# #.# #s# ### {T} - 実装量的には1500〜3000byte程度になると思います．
ジャッジ解
- @ustimaw, 1412 byte
- @mitaki28, 2029 byte
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_W = 55;
const int MAX_H = 55;
const int MAX_L = 1100;
const int D = 4;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {-1, 0, 1, 0};
const string ACT = "^v<>";
const string DIR = "NESW";
int H, W, K;
char a[MAX_H][MAX_W];
string s;
int y, x, d, p, gy, gx, ct;
bool used[MAX_H][MAX_W][D][MAX_L];
int jump[MAX_L];
void prog();
void stmt();
void if_stmt();
void while_stmt();
void action();
bool cond();
bool cond() {
if (used[y][x][d][p]) throw false;
used[y][x][d][p] = true;
bool r = false;
bool neg = false;
if (s[p] == '~') {
neg = true;
p++;
}
if (s[p] == 'T') {
r = true;
} else if (s[p] == 'C') {
r = (a[y + dy[d]][x + dx[d]] == '#');
} else {
r = (DIR.find(s[p]) == d);
}
p++;
if (neg) r = !r;
return r;
}
void action() {
ct++;
int nx, ny, nd;
if (s[p] == '^') {
ny = y + dy[d], nx = x + dx[d], nd = d;
} else if (s[p] == 'v') {
ny = y - dy[d], nx = x - dx[d], nd = d;
} else if (s[p] == '<') {
ny = y, nx = x, nd = (d + 3) % D;
} else if (s[p] == '>') {
ny = y, nx = x, nd = (d + 1) % D;
}
if (a[ny][nx] != '#') {
y = ny;
x = nx;
d = nd;
if (y == gy && x == gx) throw true;
}
p++;
}
void while_stmt() {
int q = p;
while (cond()) {
prog();
p = q;
}
p = jump[q];
}
void if_stmt() {
int q = p;
if (cond()) {
prog();
} else {
p = jump[q];
}
}
void prog() {
for (;;) {
if (ACT.find(s[p]) != string::npos) {
action();
} else if (s[p] == '[') {
assert(s[p++] == '[');
if_stmt();
assert(s[p++] == ']');
} else if (s[p] == '{') {
assert(s[p++] == '{');
while_stmt();
assert(s[p++] == '}');
} else {
break;
}
}
}
void preprocess(char end) {
int q = p;
while (s[p] != end) {
if (s[p] == '[') {
assert(s[p++] == '[');
preprocess(']');
assert(s[p++] == ']');
} else if (s[p] == '{') {
assert(s[p++] == '{');
preprocess('}');
assert(s[p++] == '}');
} else {
p++;
}
}
jump[q] = p;
}
int main() {
cin >> H >> W;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
cin >> a[i][j];
if (a[i][j] == 's') {
y = i;
x = j;
a[i][j] = '.';
}
if (a[i][j] == 'g') {
gy = i;
gx = j;
a[i][j] = '.';
}
}
}
cin >> s;
s.push_back('$');
p = 0;
preprocess('$');
p = 0;
ct = 0;
bool ok = false;
try {
prog();
} catch(bool e) {
ok = e;
}
cout << (ok ? ct : -1) << endl;
return 0;
}
裏話
せっかくなので，作問時の裏話をつらつら書きます．
問題が作られた経緯
- ICPCということで，強実装系の構文解析問題を入れようという話になった
- 過去の構文解析系の問題は式の解析が多かったので，if文やwhile文を使ってみた
- プログラムで実際にロボットを盤面上で動かしてみると面白いんじゃないかと思いつく
- 発想自体は Misterious Gems | Aizu Online Judge とかと同じ感じがする．
- 単純な構文解析と見せかけてメモ化が必要というのがひねりがあって面白そうという話になり採用
テストケースについて
- この問題は，むしろテストケースを作るのが大変だった
- ランダムケースを作るのが難しい
- 適当に作ると，ほぼ100%ゴールまで辿りつけない
- ランダムケースを作るのが難しい
- 最終的にランダムケースは以下の手順で作成
- ランダムな迷路を生成
- ランダムなプログラムを生成
- 1, 2を使って2つのケースを生成
- ランダムな位置にゴールをおいたもの(到達失敗ケース)
- ランダムなプログラムで移動する範囲の中でスタート地点から最も離れた位置にゴールを置いたもの(到達成功ケース)
- とはいっても，今回の場合，ランダムケースはあまり当てにならないので，手動ケースも作成した
- 無限ループに関するもの: 4つ
- 空プログラムを含むもの: 1つ
- 50x50のほとんど空の盤面上を動き回るもの: 6つ
- if文やwhile文を限界までネストしたもの: 2つ
- これでも，テストケースとしてはちょっと弱いなぁと思ってたら @ustimaw 君がマラソンマッチパワーを発揮してとんでもなく強力なケースを作ってくれていた
50 50 ################################################## #s..#..#.#.....#..............#...#.#.###...#....# #...........#...#.............#...#.#.#...#..#..## #....##.#......##..#.##...#.........#..##..#...### #.#..#....#.....##....#.#..##....#...###..#.....## #..###....#.##......#.#...#..###.###.............# #...#..#.#.....#..#..#..#.#...#..#.#.......#.....# #............#....#.##..#.....##...#...###....##.# #..#.#....##.#.###..#...#.##..##......#..#.###.#.# #.#..#.##............#............#.#.#...#....#.# #..#........###...#......#.......#........##....## #.....#..##.....#..#..#.#..####...#........#...#.# #..#...#.##..#..#...#...#.......##...#.#....##..## #..##.........#..#.........#...####......##.....## #..#####...#..#..#.##..##.##........#...#........# #..#........##.##..#.#.#..#..#.#.###.#.#..#..#.### #..#.#..#..#.#...#.....#..#..##.....#.....#..#..## #..#...##.#..#..#..##........#.#..######.....###.# #....#.#.##.....#....#...##..#.##...#....###.#...# ##.......#.#...#..#....#.....#.#...#........#...## #..#.##..#.........#..#.#...#......#....##..#....# #.........#..#..#.#....#..####..##...#...#.####### #.#.#..#..#..#..#....##....##.##..#...#.##.##..#.# #...##.#..#.#......##...##...#....#..#..#.#...#..# #...#..#..#..#####....##..##..#....#.#.....#.##..# #.#....#..#........#..#.##...#...##..####...#.#..# #.........#.#........#.........#..####..####.###.# #..#..#..#....###..#....#..#...#.#..#...#...#....# #.#...#..#..#.#.#..######.###.#...#.....#..##....# ##....#.#..#..#...##.#......#...#..####..#....#..# #.###.......#......#.#.#....#...#...#...##.##.#### #......#.#.....#.#.....###.#..##...#..##..#...#### #....#.....#..#.#....##..##....#...#.#..##..##...# #..#.#.##...#.....#......#....#....#..#..#...#...# #..........##..#..#........##.#......#...###..#.## #.###.#.......#.#.#...###...#...###...##.....#..## #......#.###....##..#....###....#..#..##..#...#.## #..#..#..#......#.#.#.....##....#...#..##........# #...#.......###.........#.##.###...#..#.##....#..# #.......#.#..#..##.#.##.....#............#.#.....# #.#..#..#..........##........#..##.##....#.#...#.# ##..#..#.....#..#...##..#.....#..........##...#..# #....#.#..#..#.#.#....#...##......#.####.......#.# #....#.#..##....#.##....#.#..#.#.....#.....#.#...# #...#.#..#.#.........##.#.#....##........#.....#.# #.#..##......#...##..............#...###...##.##.# #.......#.###....#.#.....#...##..##......#.#..#### #..#.#....#....#..#..##..#..#...#...##...#.....### #...#..#...#....................................g# ################################################## {T<><<><^><><<<<<<><<<<<<><<<<<<<<<><<<<<<><<<<<><<<<<>>><<<>^<<<<<<<<<<<<<><<<{Cv<<><<<<>><<<^v<<<><<><<<><<<^><><<<<<<><<<<><<<>>>>><<><<<<^<>>><<^<><<><<>><<<><<<<<>><<^><><><<<<<<<><<<<><<<<<<<<<<<>^>><>><<<><><<<><<<><<<<<vv>><<<<<<<<<<>>><<<<><<<<<>><<><<>>^<<<<<><<<><<<>><v><^<<<<^>>^<<<<<<<>^<<<><<<><<><<<v<<><<<<<<<><v<<<<><<<<><<<<<<><><<<<<<><<><<<>><<<<<<<<<>><<<<<<<><<<<<v<<><<<<<<<v<<<<><<<<<^<<<<><<<<<><<<<<<<<<<<<<<<<<>><<v<<>>><<<<<<<<^<<<<<<<<<<<<<><<<<<<^<<<<v<<<><<<<<<<<<<<<v<>><<<<<^<<<<<<<<<<><<<<><<<<v<><<><<><<<<><><<<<<<<<<<<<<><<<<>>>><<>><><<>><<<<>^<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<><<<<<><<<^<<<<<<<><<<<<<<<<<<<<<<<<<<<<><<<<<><<<<<<><<<<<<<<<<v<<<<<<v<<<^<<<<<<<^<<<<><<<<<<<<><<><<<<<<>><<<<<<<<<<<<><<><<<<><<<<><<<<<<<v<<<<<><<><<<<><<<<<<<><<^<<<<<<<><<<<<<<<<<><<<<<<><<<<<<<<<<<<<<<<<<<<>><<<<<<<<<><<<}<<<<<<<<<><<<>><<<<<<<<<<><>><<<<<<<<<<<>>><<<<<<<<<<<<<<>><><><<<<<<<<<<<<<<<<<<<<<<><<<<<<<<<<<<<<^>><<<><<><<<<<<>><<<<<^<<<><>><<><<>><<<<<<<<<><<><<>}- このケース，ゴールまでに1210310(動作文)かかる
- 理論上の最大値の1/10
- これよりも長い動作文が必要なケースを作れたという方はご一報ください．
- このケース，ゴールまでに1210310(動作文)かかる
コンテスト中のジャッジルームにて
- 先ほど書いたように，「動作文のない無限ループが存在しうる」という罠があるにも関わらず，コンテスト開始時に問題文が『「プログラム」は複数の「文」からなり，...』となっており，あわてて修正した．
- AtCoder の仕様で問題文を修正すると，"<" や ">" のエスケープが解除されてしまうというトラップがあり，Sample Input 中で使われていた"<" や ">" がぶっ壊れてしまい，更なる対応に追われた．
- 基本的にAtCoderで問題文を訂正するときは，AtCoder上から書き換えるのではなく，問題文を再生成してコピペするほうが安全
- 構文解析＋探索でそれほど内容的には難しくないと考えていたので，想像以上にWAやTLEが多くミスジャッジしてしまっているのではないかとヒヤヒヤしていた．
- 上記のトラブルや，WAやTLEの多さからジャッジルームでずっとヤバいヤバい言ってて周囲を苛つかせていたかもしれない．反省している．