【4完】ABC453 振り返り #C++

はじめに

ABC453に参加したため振り返っていきます。結果は4完でした。

A - Trime

文字列 $S$ の先頭に連続するoをすべて取り除いた文字列を出力する問題です。文字列の先頭ポインタをoの間インクリメントし、残りを出力しました。

abc453_a.c

#include <stdio.h>

int main(void) {
    int N; scanf("%d", &N);
    char S[N + 1]; scanf("%s", S);
    char *p = S;

    while (*p == 'o') {
        p++;
    }

    printf("%s\n", p);
    return 0;
}

ポインタ操作の注意点として、C言語の文字列を格納する配列は末尾に終端文字\0が入るため、$N$文字の文字列を格納するためにはN + 1のサイズが必要です。また、ポインタのインクリメントで文字列の先頭位置を進めた場合、printf("%s", p)でポインタの現在位置以降の文字列をそのまま出力できます。

B - Sensor Data Logging

センサーの値を条件によって場合分けする問題でした。時刻 $0$ の時はそのまま出力、それ以降は直前に保存された値との差（絶対値）が $X$ 以上なら記録するというフローでした。毎ステップ更新しないように注意です。

abc453_b.c

#include <stdio.h>

int main(void) {
    int T, X; 
    scanf("%d %d", &T, &X);
    int A; 
    
    scanf("%d", &A);
    int last = A;  // 直前に保存された値
    printf("0 %d\n", last);  // 時刻0は必ず保存

    for (int i = 1; i <= T; i++) {
        scanf("%d", &A);

        int diff;
        if (last - A < 0) {
            diff = A - last;
        } else {
            diff = last - A;
        }

        if (diff >= X) {
            printf("%d %d\n", i, A);
            last = A;  // 保存されたときだけ更新
        }
    }
    return 0;
}

C - Sneaking Glances

数直線上において原点 $O$ を最大何回通過するかをカウントする問題でした。解法として、$N≦20$ なので $2^N$ 通りの方向の組み合わせを全探索します（ビット全探索）。

maskのiビット目でi回目の方向を表現します。各組み合わせで座標の符号の変化（=0を通過）をカウントします。初期入りは $0.5$（正の側）で、移動前後の座標の積が負になった時（符号が変わった時）に座標 $0$ を通過したと判定できます。$L_i\geq 1$ の整数なので、座標がちょうど $0$ になることはなく、この判定が成り立ちます。

abc453_c.c

#include <stdio.h>

int main(void) {
    int N;
    scanf("%d", &N);
    int L[N];
    for (int i = 0; i < N; i++) {
        scanf("%d", &L[i]);
    }

    int ans = 0;
    for (int mask = 0; mask < (1 << N); mask++) {
        double pos = 0.5;
        int count = 0;
        for (int i = 0; i < N; i++) {
            int dir = (mask >> i) & 1;
            double prev = pos;
            if (dir == 0) {
                pos += L[i];
            } else {
                pos -= L[i];
            }
            // ここで0を通り過ぎたか判定
            if (prev * pos < 0) {
                count++;
            }
        }
        // countの最大値を更新
        if (count > ans) {
            ans = count;
        }
    }

    printf("%d\n", ans);
    return 0;
}

>>は右シフト演算子です。

mask >> iはmaskのビット列を右にiビットずらす操作です。例としてmask = 0b1101（=13）で確認します。

式	結果	ビット列
mask >> 0	13	1101
mask >> 1	6	0110
mask >> 2	3	0011
mask >> 3	1	0001

右にずらす度に見たいビットが最下端桁に来ることが分かります。そこに& 1することで最下位ビットだけ取り出せます。

今回のコードではind dir = (mask >> i) & 1がi回目の移動方向（0 or 1）を取り出しています。

D - Go Straight

通常の迷路と違い、マスの種類によって次の方向が制約される問題でした。

解法として幅優先探索（BFS）を用い、状態を(行, 列, 直前の方向)の3つの組で管理しました。状態空間は $1000 * 1000 * 5 = 500万$ なのでタイムアウトしません。親ポンタで経路を復元し、逆順を反転して出力します。

通常の迷路では状態は(行, 列)の2つの組ですが、この問題はoマス・xマスの制約が「直前の移動方向」に依存するため、方向も状態に含める必要があります。判定は以下の通りです。

• oマスにいるとき：試している方向dが直前の方向dirを異なれば進めない（d != dirでスキップ）
• xマスにいるとき：試している方向dが直前の方向dirと同じなら進めない（d == dirでスキップ）

経路復元は、BFSで各状態に「どの状態から遷移してきたか（親ポインタ）」を記録しておき、ゴールからスタートまで逆順にたどって経路を構築します。最後に配列を反転して正しい順序にします。

マス	制約
o	同じ方向のみ
x	同じ方向は禁止
./S/G	制約なし

abc453_d.c

#include <stdio.h>
#include <string.h>

#define MAXN 1000
#define MAXSTATES (MAXN * MAXN * 5)

int H, W;
char grid[MAXN][MAXN + 1];

// 方向: 0=U, 1=D, 2=L, 3=R, 4=なし（スタート）
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
char dname[] = "UDLR";

int visited[MAXN][MAXN][5];

// 親ポインタ: どの状態から来たか
int par_r[MAXN][MAXN][5];
int par_c[MAXN][MAXN][5];
int par_dir[MAXN][MAXN][5];

typedef struct { int r, c, dir; } State;
State queue[MAXSTATES];
char path[MAXSTATES];

int main(void) {
    scanf("%d %d", &H, &W);
    int sr, sc, gr, gc;
    for (int i = 0; i < H; i++) {
        scanf("%s", grid[i]);
        for (int j = 0; j < W; j++) {
            if (grid[i][j] == 'S') {
                sr = i;
                sc = j;
            }
            if (grid[i][j] == 'G') {
                gr = i;
                gc = j;
            }
        }
    }

    // BFS初期化
    int head = 0, tail = 0;
    queue[tail++] = (State){sr, sc, 4};
    visited[sr][sc][4] = 1;

    int found = 0, fdir = -1;

    while (head < tail && !found) {
        State cur = queue[head++];
        int r = cur.r, c = cur.c, dir = cur.dir;

        for (int d = 0; d < 4; d++) {
            // o, x の条件チェック
            if (grid[r][c] == 'o' && dir != 4 && d != dir) continue;
            if (grid[r][c] == 'x' && d == dir) continue;

            int nr = r + dr[d];
            int nc = c + dc[d];

            // 範囲外・壁チェック
            if (nr < 0 || nr >= H || nc < 0 || nc >= W || grid[nr][nc] == '#') continue;

            if (visited[nr][nc][d]) continue;
            visited[nr][nc][d] = 1;

            // 親ポインタを記録
            par_r[nr][nc][d] = cur.r;
            par_c[nr][nc][d] = cur.c;
            par_dir[nr][nc][d] = cur.dir;

            queue[tail++] = (State){nr, nc, d};

            if (nr == gr && nc == gc) {
                found = 1;
                fdir = d;
                break;
            }
        }
    }

    if (!found) {
        printf("No\n");
        return 0;
    }

    // パス復元: ゴールからスタートへ逆順に辿る
    int plen = 0;
    int r = gr, c = gc, dir = fdir;
    while (!(r == sr && c == sc)) {
        path[plen++] = dname[dir];
        int pr = par_r[r][c][dir];
        int pc = par_c[r][c][dir];
        int pd = par_dir[r][c][dir];
        r = pr; c = pc; dir = pd;
    }

    // 逆順をなおす
    for (int i = 0; i < plen / 2; i++) {
        char tmp = path[i];
        path[i] = path[plen - 1 - i];
        path[plen - 1 - i] = tmp;
    }
    path[plen] = '\0';

    printf("Yes\n%s\n", path);
    return 0;
}

ちなみに深さ優先探索（DFS）でも一応ACしました。

DFSでも正しい答えが得られる理由は、visited[行][列][方向]を立てたまま戻ることで、「この状態からゴールに到達できない」という情報を使い回しているためです。
同じ状態を2度探索しないので、無限ループにもなりません。

ただし、再帰の深さが最悪で状態空間の全数（今回は $1000 \times 1000 \times 5 = 500$万）に達する可能性があります。C言語のデフォルトのスタックサイズは通常数MB程度なので、深い再帰でスタックオーバーフローが起きる恐れがあります。

BFSはキューをグローバル配列として静的領域に確保しているため、この問題が起きません。

今回グローバル配列を使用したため、C言語のメモリ構造についてまとめていきます。

領域	何が置かれるか	上限
スタック	ローカル変数、関数の呼び出し情報	数MB（小さい）
ヒープ	mallocで動的確保したメモリ	数GB（大きい）
静的領域	グローバル変数、static変数	数GB（大きい）

今回のコードにおいてqueueやvisitedはグローバル変数なので、正確には静的領域に置かれます。DFSが危ない理由は「再帰呼び出しがスタックを消費する」からで、BFSが安全な理由は「キューをグローバル配列（静的領域）」に置いているのでスタックを消費しないからです。

おわりに

今回のコンテストの解法をまとめると以下の通りです。

• A問題：ポインタ操作
• B問題：シミュレーション（各ステップの更新だけ注意）
• C問題：ビット全探索
• D問題：幅優先探索（BFS）

D問題については最初はDFSで実装してしまったので、そこらへんの違いをちゃんと理解しておきたいです（運よくACしたから良かったものの...）。またビット演算は大学編入でも頻出のテーマなので復習しておきたいです。