蟻本練習問題解説 Part1 (2-1)

• この記事は 解説 Advent Calendar 2017 の 23 日目の記事として書かれました。

みなさんは、蟻本の「練習問題」を解いたことはありますか？本の中で掲載されている例題は見たことがあっても、練習問題までは手を出していない、という人はそれなりにいるのではないでしょうか (要出典)

というわけで、今日から不定期で蟻本の練習問題を解説していきます。学習の一助になってくれれば幸いです。わからないところがあれば Twitter などで気軽にきいてください。

英語の問題は簡単に和訳しています。分量が多いので何回かに分けてやっていきますが、なんとか完走したいです・・・！

シリーズ目次はこちらからどうぞ。

tsutaj.hatenablog.com

すべての基本 "全探索"

深さ優先探索

POJ 1979: Red and Black

問題リンク

問題概要については、AOJ に全く同じ問題が日本語で掲載されているので、そちらを参照してください。

▶表示する

典型的な探索問題です。「4 近傍」は、座標の差分を配列で管理すると楽に書けます。

char board[30][30];
bool visited[30][30];

int H, W;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void dfs(int x, int y) {
    rep(k,0,4) {
        int nx = x + dx[k], ny = y + dy[k];
        if(nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
        if(board[nx][ny] == '#') continue;
        if(visited[nx][ny]) continue;
        visited[nx][ny] = true;
        dfs(nx, ny);
    }
}

int main() {
    while(cin >> W >> H, W || H) {
        memset(visited, false, sizeof(visited));

        int sx = 0, sy = 0;
        rep(i,0,H) rep(j,0,W) {
            cin >> board[i][j];
            if(board[i][j] == '@') {
                sx = i, sy = j;
            }
        }

        visited[sx][sy] = true;
        dfs(sx, sy);

        int ans = 0;
        rep(i,0,H) rep(j,0,W) {
            if(visited[i][j]) ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

POJ 3009: Curling 2.0

問題リンク

問題概要については、AOJ に全く同じ問題が日本語で掲載されているので、そちらを参照してください。

▶表示する

1 回のゲーム中に滑らせる回数の最大は 10 回です。石を動かす方向の候補は 4 つあるので、動かし方は 通りあります。この程度であれば全て試せます。

障害物が消えたりと、先ほどの問題より難しく感じるかもしれませんが、やることはあまり変わりません。

using Matrix = vector< vector<int> >;
const int INF = 1 << 30;
int W, H, ans = 0;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
 
void dfs(Matrix &mat, int turn, int pos_x, int pos_y) {
    if(turn > 10) return;
    for(int k=0; k<4; k++) {
        int nx = pos_x, ny = pos_y;
        int px = nx + dx[k], py = ny + dy[k];
        if(px < 0 || px >= H || py < 0 || py >= W) continue;
        if(mat[px][py] == 1) continue;
 
        while(1) {
            nx += dx[k], ny += dy[k];
            if(nx < 0 || nx >= H || ny < 0 || ny >= W) {
                // out of range
                break;
            }
            else if(mat[nx][ny] == 3) {
                // goal
                ans = min(ans, turn);
                break;
            }
            else if(mat[nx][ny] == 1) {
                // obstacle
                mat[nx][ny] = 0;
                dfs(mat, turn+1, nx-dx[k], ny-dy[k]);
                mat[nx][ny] = 1;
                break;
            }
        }
    }
}
 
int main() {
    while(cin >> W >> H, W) {
        ans = INF;
        Matrix mat(H, vector<int>(W));
 
        int x = 0, y = 0;
        for(int i=0; i<H; i++) {
            for(int j=0; j<W; j++) {
                cin >> mat[i][j];
                if(mat[i][j] == 2) {
                    x = i, y = j;
                }
            }
        }
 
        dfs(mat, 1, x, y);
        cout << (ans == INF ? -1 : ans) << endl;
    }
    return 0;
}

AOJ 0118: Property Distribution

問題リンク

概要は日本語なので省略します。

▶表示する

隣が同じ文字であれば探索を続けることができます。ですので、既にそのマスを見たかどうかを覚えながら dfs を書けば良いです。

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int H, W;
char board[110][110];
bool visited[110][110];

void dfs(int x, int y) {
    rep(k,0,4) {
        int nx = x + dx[k], ny = y + dy[k];
        if(nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
        if(board[nx][ny] != board[x][y]) continue;
        if(visited[nx][ny]) continue;

        visited[nx][ny] = true;
        dfs(nx, ny);
    }
}

int main() {
    while(cin >> H >> W, H || W) {
        memset(visited, false, sizeof(visited));
        rep(i,0,H) rep(j,0,W) cin >> board[i][j];

        int ans = 0;
        rep(i,0,H) rep(j,0,W) {
            if(visited[i][j]) continue;
            ans++;
            dfs(i, j);
        }
        cout << ans << endl;
    }
    return 0;
}

AOJ 0033: Ball

問題リンク

概要は日本語なので省略します。

▶表示する

それぞれの玉について、筒 B または C に入るため、入れ方は 通りあります。これは全て試せるため、それぞれの筒に最後に入れた玉の番号を覚えながら dfs をすれば良いです。

また別解として、今入れる玉の番号と、最後に筒に入れた番号の差分が小さい方の筒に貪欲に筒を入れていく貪欲法も存在します。この場合は線形時間で解けます。 参考

bool ans;
int a[10];
void dfs(int idx, int l, int r) {
    if(idx == 10) {
        ans = true;
        return;
    }

    int val = a[idx];
    if(l < val) dfs(idx+1, val, r);
    if(r < val) dfs(idx+1, l, val);
}

int main() {
    int N; cin >> N;
    while(N--) {
        ans = false;
        rep(i,0,10) cin >> a[i];
        dfs(0, -1, -1);
        cout << (ans ? "YES" : "NO") << endl;
    }
    return 0;
}

幅優先探索

AOJ 0558: Cheese

問題リンク

概要は日本語なので省略します。

▶表示する

体力を増やさないと次のチーズが食べられず、また硬さ 1 から N までのチーズは 1 個ずつあるため、(始点から硬さ 1 のチーズへ)、(硬さ 1 から硬さ 2 のチーズへ)・・・という動き方になります。これは経路が N 個あると考えればよく、それぞれの経路に対して始点から幅優先探索をすることで最短経路が求まります。今回は最大 9 回の幅優先探索をすれば良いです。

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1 << 25;

int H, W, N;
char board[1010][1010];
int dist[1010][1010];
int x[10], y[10];

int bfs(int sx, int sy, int tx, int ty) {
    rep(i,0,H) rep(j,0,W) dist[i][j] = INF;
    dist[sx][sy] = 0;

    queue<pii> que;
    que.push(make_pair(sx, sy));

    while(que.size()) {
        pii cur = que.front(); que.pop();
        int cx, cy;
        tie(cx, cy) = cur;

        rep(k,0,4) {
            int nx = cx + dx[k], ny = cy + dy[k];
            if(nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if(board[nx][ny] == 'X') continue;
            if(dist[nx][ny] > dist[cx][cy] + 1) {
                dist[nx][ny] = dist[cx][cy] + 1;
                que.push(make_pair(nx, ny));
            }
        }
    }

    return dist[tx][ty];
}

int main() {
    cin >> H >> W >> N;
    rep(i,0,H) rep(j,0,W) {
        cin >> board[i][j];
        if(board[i][j] == 'S') board[i][j] = '0';
        if(isdigit(board[i][j])) {
            int val = board[i][j] - '0';
            x[val] = i, y[val] = j;
        }
    }

    int ans = 0;
    rep(i,0,N) {
        ans += bfs(x[i], y[i], x[i+1], y[i+1]);
    }
    cout << ans << endl;
    return 0;
}

POJ 3669: Meteor Shower

問題リンク

隕石が 個落ちてくる。 番目の隕石は、座標 に時刻 に落ち、落ちた直後からその座標とそれに隣接する 4 つの座標には立ち入ることができなくなる。あなたは最初に座標 におり、そこから単位時間あたり 1 マス分進んで安全な場所 (隕石による影響がない場所) まで移動したい。このようなことが可能であれば最短の時間を、不可能であれば -1 を出力せよ。

▶表示する

まず、座標 に隕石が時刻 で落ちてくるのであれば、明らかに不可能です。

マスに進めるか否かに時刻の制約があるため、それぞれのマスについて「いつ以降立ち入り不可能になるか」を覚えておきます。その情報を使いながら bfs をすればよいです。

int dx[] = {0, 0, 1, -1, 0};
int dy[] = {1, -1, 0, 0, 0};

const int INF = 1 << 25;
const int S = 310;

int crash[S][S];
int dist[S][S];

int main() {
    rep(i,0,S) rep(j,0,S) crash[i][j] = dist[i][j] = INF;

    int N; cin >> N;
    rep(i,0,N) {
        int x, y, t; cin >> x >> y >> t;
        rep(k,0,5) {
            int nx = x + dx[k], ny = y + dy[k];
            crash[nx][ny] = min(crash[nx][ny], t);
        }
    }

    // 時刻 0 で始点に隕石が落ちると詰む
    if(crash[0][0] == 0) {
        cout << -1 << endl;
        return 0;
    }

    int ans = INF;
    dist[0][0] = 0;
    queue<pii> que;
    que.push(make_pair(0, 0));
    while(!que.empty()) {
        pii cur = que.front(); que.pop();
        int x = cur.first, y = cur.second;

        if(crash[x][y] == INF) {
            ans = min(ans, dist[x][y]);
        }

        rep(k,0,4) {
            int nx = x + dx[k], ny = y + dy[k];
            if(nx < 0 || nx >= S || ny < 0 || ny >= S) continue;
            int cand = dist[x][y] + 1;
            if(crash[nx][ny] > cand && dist[nx][ny] > cand) {
                dist[nx][ny] = cand;
                que.push(make_pair(nx, ny));
            }
        }
    }

    cout << (ans == INF ? -1 : ans) << endl;
    return 0;
}

AOJ 0121: Seven Puzzle

問題リンク

概要は日本語なので省略します。

▶表示する

まず、あり得る盤面の数がいくつあるかを考えましょう。これは長さ 8 の順列の数と同じですので、 通りあります。この程度のサイズであれば、全ての盤面について最小手数を覚えることができます。

ここで、「ある盤面 から最終状態にするまでの最小手数」と「最終状態からある盤面 にするまでの最小手数」は、全く変わりません。よって、最終状態から幅優先探索を行って各盤面について最小手数を覚える前処理をしておけば、あとは盤面に対応する値を読むだけになりますので、各クエリに対して で答えられます。

発展的な内容として、このルールと同様のもので盤面サイズが増えたものを考えます。あり得る盤面の数は階乗オーダーで増えていくため、サイズによっては全てを覚えることはできません。サイズの大きいある盤面について最小手数を計算するには、 探索という推定値付きのダイクストラ法を使えば、高速に求めることができます。これの練習問題として、 Indeedなう (予選 A) の D 問題 があります。うまく書けば、 24 手以内で解くことができる 36 パズルの最小手数を、 30ms 台で計算することができます。

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
map< vector<int>, int > mp;

void init(vector<int> vs) {
    queue< vector<int> > que;
    que.push(vs);
 
    while(!que.empty()) {
        vector<int> cur = que.front(); que.pop();
         
        int idx = -1;
        rep(i,0,8) {
            if(cur[i] == 0) {
                idx = i;
                break;
            }
        }
 
        rep(k,0,4) {
            int nx = (idx / 4) + dx[k];
            int ny = (idx % 4) + dy[k];
            if(nx < 0 || nx >= 2 || ny < 0 || ny >= 4) continue;
            int nc = nx * 4 + ny;
            vector<int> tmp = cur;
            swap(tmp[nc], tmp[idx]);
            if(mp.count(tmp)) continue;
            mp[tmp] = mp[cur] + 1;
            que.push(tmp);
        }
    }
}
 
int main() {
    vector<int> v(8);
    iota(v.begin(), v.end(), 0);
    mp[v] = 0;
    init(v);
 
    string s;
    while(getline(cin, s)) {
        stringstream ss(s);
        vector<int> vs;
        int val;
        while(ss >> val) vs.push_back(val);
 
        cout << mp[vs] << endl;
    }
    return 0;
}

全列挙

POJ 2718: Smallest Difference

問題リンク

相異なる 10 進数の 1 桁の数字の集合が与えられる。この集合を 2 つの部分集合に分ける (空集合は許されない)。同じ集合に属する数字どうしを全て組み合わせて、数字を 1 つ作る。例えば集合が である場合、 や などが作れる。ただし、leading zero は許されないため、 は作れない。このとき、それぞれの集合で作った 2 つの数字の差の絶対値の最小値を求めよ。

▶表示する

最小化をしたいので、9 個の数字があるときに 8 個と 1 個に分けるなどの分割は明らかに無駄です。この場合は、集合の要素数が半分になるように分ければ良いです。

あとは数字の列挙の方法ですが、next_permutation を使うと楽です。 0 の扱いに気をつけましょう。

const int INF = 1 << 30;

int main() {
    int T; cin >> T;
    cin.ignore();
    while(T--) {
        string s;
        getline(cin, s);
        stringstream ss(s);

        int val;
        vector<int> vs;
        while(ss >> val) vs.push_back(val);
        sort(vs.begin(), vs.end());

        int N = vs.size(), len = N / 2, ans = INF;
        do {
            int vl = 0, vr = 0;
            if(len != 1 && vs[0] == 0) continue;
            if(N - len != 1 && vs[len] == 0) continue;
            
            rep(i,0,len) {
                vl = vl * 10 + vs[i];
            }

            rep(i,0,N-len) {
                vr = vr * 10 + vs[len+i];
            }

            ans = min(ans, abs(vl - vr));
        }while(next_permutation(vs.begin(), vs.end()));
        cout << ans << endl;
    }
    return 0;
}

POJ 3187: Backward Digit Sums

問題リンク

長さ の順列が与えられる。1 行目にはその順列そのものを書き下す。2 行目以降は、前の行において隣接している要素同士を足しあわせたものを書き下すという操作を行う。この操作によって、最後の行は 1 つの数字からなる。順列の長さ と、最後の行に書かれた数字 が与えられるので、順列を復元せよ。なお、答えが複数ある場合は、辞書順最小のものを出力せよ。

▶表示する

これも基本的には next_permutation を使うのですが、本当に全ての場合に対してシミュレーションすると実行時間的に怪しいです (本当は間に合うかもしれませんが)。なので、「1 行目で左から 番目の要素は最後の要素に何回足されているか」の情報を前処理して求めます。すると、それぞれの順列に対して値を計算する部分が線形になるため、間に合います。

int board[15][15];

int main() {
    int N, K; cin >> N >> K;
    vector<int> weight(N);
    rep(i,0,N) {
        memset(board, 0, sizeof(board));
        board[0][i] = 1;
        rep(depth,0,N) rep(k,0,N-depth) {
            if(k-1 >= 0) board[depth+1][k-1] += board[depth][k];
            board[depth+1][k]   += board[depth][k];
        }
        weight[i] = board[N][0];
    }

    vector<int> perm(N);
    rep(i,0,N) perm[i] = i+1;
    do {
        int val = 0;
        rep(i,0,N) val += weight[i] * perm[i];
        if(val == K) {
            rep(i,0,N) cout << (i != 0 ? " " : "") << perm[i];
            cout << endl;
            return 0;
        }
    }while(next_permutation(perm.begin(), perm.end()));
    return 0;
}

POJ 3050: Hopscotch

問題リンク

1 マスにつき数字 1 桁が書かれている のが盤面がある。適当な位置からスタートし、上下左右に移動して 6 桁の数字を作るとき、何種類の数字が作れるか？

▶表示する

まず、開始位置の候補が 通りあります。また、 回移動する必要があり、それぞれに対して移動候補は 通りなので、全部で 通りしかありません。よって、全探索で解けます。

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

char board[6][6];
set<string> S;

void dfs(int turn, int x, int y, string s) {
    if(turn == 5) {
        S.insert(s);
    }
    else {
        rep(k,0,4) {
            int nx = x + dx[k], ny = y + dy[k];
            if(nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
            dfs(turn+1, nx, ny, s + board[nx][ny]);
        }
    }
}

int main() {
    rep(i,0,5) rep(j,0,5) cin >> board[i][j];

    rep(i,0,5) rep(j,0,5) {
        string tmp = "";
        tmp += board[i][j];
        dfs(0, i, j, tmp);
    }
    cout << S.size() << endl;
    return 0;
}

AOJ 0525: Osenbei

問題リンク

概要は日本語なので省略します。

▶表示する

行数が少ないことに着目します。 行までしかないのですから、行についてひっくり返すパターンの数は高々 通りしかありません。なので、行についてひっくり返すパターンを決め打ちして、列についてはひっくり返したほうが多く取れるならばひっくり返し、そうでなければひっくり返さなければ良いです。

const int INF = 1 << 25;
int R, C;
int board[20][10010];
int inv[20][10010];

int main() {
    while(cin >> R >> C, R || C) {
        rep(i,0,R) rep(j,0,C) {
            cin >> board[i][j];
            inv[i][j] = board[i][j] ^ 1;
        }

        int ans = 0;
        rep(bit,0,1<<R) {
            vector<int> cnt(C);
            rep(i,0,R) {
                rep(j,0,C) {
                    // ひっくり返すかどうか
                    if(bit >> i & 1) cnt[j] += inv[i][j];
                    else cnt[j] += board[i][j];
                }
            }

            int tmp = 0;
            rep(i,0,C) {
                tmp += max(cnt[i], R - cnt[i]);
            }
            ans = max(ans, tmp);
        }
        cout << ans << endl;
    }
    return 0;
}

全探索できるかどうかは、あり得るパターン数がどれくらいあるのかをざっくりと計算すれば良いです。大まかな計算量の見積りができるようにしましょう。

次回は、貪欲法のトピックを扱っていきます。