今まで学んだことを生かして4問解いてみた. 答えと全然違う実装をしたくないので, 問題を読んで実装の流れを考えたら答えをみるという流れでやってみた.

Minimum Scalar Product (2008 Round1A A)

2つのベクトル成分を自由に入れ替えて内積を最小にする問題. 最初は数の正負を考えて, 正の数で絶対値が大きいものには負の数で絶対値が大きいものと積を取るようにみたいなことを考えていたが, シンプルに2つの成分を順と逆順でソートすればよかった.

const int MAX_N = 800;

typedef long long ll;

int n;
int v1[MAX_N], v2[MAX_N];

void solve() {
    sort(v1, v1 + n);
    sort(v2, v2 + n);
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += (ll)v1[i] * (ll)v2[n - i - 1];
    }
    printf("%lld\n", ans);
}

Crazy Rows (2009 Round2 A)

行をバブルソートする問題. 行列が与えられて下三角行列がどうとか難しい話をしているが案外簡単で, 上から順に行を埋めていくことを考える. 動かす行は上の行にすることで, 動かす操作数を最小化する.

実装のポイントとしてはa[i]: i行目の最後に現れる1の位置-1 ~ N-1を定義することで行列より扱いやすくしている. また, 配列の要素を入れ替えるswapをうまく使って再帰的な処理を実現している.

void solve() {
    int res = 0;

    // 配列にする
    for (int i = 0; i < N; i++) {
        a[i] = -1;
        for (int j = 0; j < N; j++) {
            if (M[i][j] == 1) {
                a[i] = j;
            }
        }
    }

    for (int i = 0; i < N; i++) {
        int pos = -1;  // i + 1行目に移動する行番号
        for (int j = i; j < N; j++) {
            if (a[j] <= i) {
                pos = j;
                break;
            }
        }

        // 実際にスワップ
        for (int j = pos; j > i; j--) {
            swap(a[j], a[j - 1]);
            res++;
        }
    }
    printf("%d\n", res);
}

Bribe the Prisoners (2009 Round 1C C)

囚人の問題. 普通に問題として面白かった. アルゴリズムのポイントとしては, 空き部屋の概念と端の概念を一緒にしていかに再帰を実現するか.

実装のポイントとしては, 動的計画法を用いるためにdp[MAX_Q + 1][MAX_Q + 2]: (i, j)を解放するのに必要な金貨を定義して使うところ. dpがどういう動きをするのかが最初わかりにくいので具体的な例でdpテーブルを埋める作業をしてみる. 幅が小さい順に調べるモチベーションがわかる.

const int MAX_Q = 100;

int P, Q, A[MAX_Q + 2];

// (i, j)を解放するのに必要な金貨
int dp[MAX_Q + 1][MAX_Q + 2];

void solve() {
    // 簡単のため端をAに追加する
    A[0] = 0;
    A[Q + 1] = P + 1;

    // 初期化
    for (int q = 0; q <= Q; q++) {
        dp[q][q + 1] = 0;
    }

    // 幅が小さい順にdpを埋めていく
    for (int w = 2; w <= Q + 1; w++) {
        for (int i = 0; i + w <= Q + 1; i++) {
            int j = i + w;
            int t = INT_MAX;

            // 最初に解放する囚人を全て試し最小コストのものを探す
            for (int k = i + 1; k < j; k++) {
                t = min(t, dp[i][k] + dp[k][j]);
            }

            // 最初の解放では解放する囚人にかかわらずA[j] - A[i] - 2の金貨が必要
            dp[i][j] = t + A[j] - A[i] - 2;
        }
    }
    printf("%d\n", dp[0][Q + 1]);
}

Millionaire (2008 APAC local onsites C)

お金の掛け方が整数に限られていないので, 全探索ができない. ここで, ラウンドが1回しかなかった場合, 金額によって0%, P%, 100%の3つの確率に分けられることに気づく. さらに2ラウンドの場合は, 5つの確率に分けられる. この考えかたを動的計画法で実装する.

実装のポイントとしては, iラウンド目の確率はi-1ラウンド目の確率をもとに計算するので, 2つの配列prvとnxtを用意してうまく使うところにある. i-1ラウンド目の状態から正解・不正解する場合を確率の独立性を生かして考える.

typedef long long ll;
const int MAX_M = 15;

int M, X;
double P;

double dp[2][(1 << MAX_M) + 1];

void solve() {
    // n = 2^M
    int n = 1 << M;

    double \*prv = dp[0], \*nxt = dp[1];
    memset(prv, 0, sizeof(double) * (n + 1));
    // 既に100万円持っていれば確率1
    prv[n] = 1.0;

    for (int r = 0; r < M; r++) {
        for (int i = 0; i <= n; i++) {
            int jub = min(i, n - i);
            double t = 0.0;
            for (int j = 0; j <= jub; j++) {
                t = max(t, P * prv[i + j] + (1 - P) * prv[i - j]);
            }
            nxt[i] = t;
        }
        swap(prv, nxt);
    }

    // 全勝した場合の金額 / 100万円
    int i = (ll)X * n / 1000000;
    printf("%.6f\n", prv[i]);
}

感想

アルゴリズムに落とし込むところは発想力, そのあとの実装は再帰などをどう実現するかの数学力が必要なのではないかと思った.