NoiminのNoise

競技プログラミング (多め) とWeb (たまに) ,自然言語処理 (ブログではまだ)。数式の書き方を一気に KaTeX に変えようとして記事を全削除してインポートし直すなどしたので,過去にブックマークされた記事は URL が変わってしまっている可能性があります…….

Google Code Jam 2020 Qualification Round - ESAb ATAd

問題: ESAb ATAd - Code Jam

問題概要

'0' と'1' のみからなる長さ$B$ の文字列が与えられる (制約は本節最後を参照)。この文字列に対して,次のクエリを 150 回まで投げることができる。

  • 文字列の $i$ 文字目は '0' と'1' のどちら?

1回目,11回目,21回目……のクエリが投げられたとき,サーバがクエリの回答を渡す前に,文字列に以下の操作のうちいずれか1つが行われる。

  • 何もしない
  • complement : '0' を '1' に,'1' を'0' にする
  • reverse : 文字列を逆順にする
  • compliment と reverse の両方を適用する

適用された動作が何かは一切わからない。

このとき,長さ $B$ の文字列は現在どうなっているかを答えよ。文字列の初期状態を答える必要はなく,現時点での状態を $B$ 文字分揃って答えられれば良い。

制約

テストケース数 : $T \leq 100$

Test Set 1 : $B = 10$

Test Set 2 : $B = 20$

Test Set 3 : $B = 100$

解法概要

中心からの距離が同じ文字列 (例えば $B = 100$ なら 1 番目と 100 番目,2 番目と 99 番目,……) をペアで見ていく。$i$ 番目の文字と $j$ 番目の文字のペアを今後 $(i, j)$ のように表すとする。

10回目のクエリまでは文字列に変更はないので,文字列の外側から見ていって $(i+1, B-i) (0 \leq i \lt 5)$ の5ペアを確定させていく。

11回目以降は10回ごとに文字列に変更が入る可能性があるので,それを検知する必要がある。文字列の変更は,今まで見たペアの中で同じ数字だったペアと違う数字だったペアをあらかじめ覚えておいて,その数字が今どうなっているかを聞き直すことで検知する。この検知には 2 回分のクエリを消費するので,11回目以降は「文字列の状態の検知のためのクエリ2回→今まで不明だった部分を聞くクエリ8回」という 10 クエリ 1 セットの繰り返して,文字列に反映された操作を常に把握して文字列全体を作っていく。

例えば,外側から見ていったときに最初に見つけた同じ数字のペアの値が,前回見たときは両方 0 だったのに今は 1 に変更されているとしよう。これは文字列が complement されたことを意味する。文字列の中心からの距離が同じペアであれば,reverse されていようといまいと complement されれば必ず元の数字とは別の数字に変更されるからである。なお,reverse されたかどうかはこの段階では分からない。

reverse されているかどうかは,外側から見ていったときに最初に見つけた違う数字のペアを使う。違う数字のペアは,complement または reverse されると前回の値からは変更になる。ただし,complement と reverse の両方が適用されると前回の値と同じになる。したがって,違う数字のペアの値が変更になっているとき,complement されているなら reverse はされておらず,complement されていないなら reverse されている。変更になっていない場合は,complement されているなら reverse されていて,complement されていないなら reverse もされていない。要するに,「変更になったか?」と「complement されているか?」の排他的論理和として書ける。

同じ数字のペア / 違う数字のペア,片方しか見つかっていない場合には,それぞれ complement / reverse だけを考慮すればよい。reverse / complement されても,その時点で判明している部分の文字列はまったく変わらないためである。ただしこの場合,10 クエリ 1 セットのクエリ回数を壊さないために,適当にダミーのクエリを投げておく必要がある。11回目以降,不明部分を外側から埋めていく途中で同じ数字のペア / 違う数字のペアを新しく見つけたらそれを記録しておくのを忘れないこと。

ソースコード

#include <iostream>
#include <algorithm>
#include <utility>

using namespace std;

int B, same_pair_i = -1, diff_pair_i = -1, same_pair_num, diff_pair_num;
int a[100];

// i+1 番目と B-i 番目を読み込む
void read_pair(int i) {
    int r1, r2;
    cout << i+1 << endl;
    cin >> r1;
    a[i] = r1;
    cout << B-i << endl;
    cin >> r2;
    a[B-1-i] = r2;
    if(r1 == r2) {
        if(same_pair_i == -1) {
            same_pair_i = i;
            same_pair_num = r1;
        }
    } else {
        if(diff_pair_i == -1) {
            diff_pair_i = i;
            diff_pair_num = r1;
        }
    }
}

bool solve() {
    same_pair_i = -1;
    diff_pair_i = -1;
    for(int i=0;i<5;++i) {
        read_pair(i);
    }

    for(int i=5;i<B/2;i+=4) {
        int r;
        bool is_complemented = false;
        if(same_pair_i != -1) {
            cout << same_pair_i+1 << endl;
            cin >> r;
            is_complemented = (r != same_pair_num);
            same_pair_num = r;
        } else {
            cout << 1 << endl;
            cin >> r;
        }
        bool is_reversed = false;
        if(diff_pair_i != -1) {
            cout << diff_pair_i+1 << endl;
            cin >> r;
            is_reversed = (r != diff_pair_num) ^ is_complemented;
            diff_pair_num = r;
        } else {
            cout << 1 << endl;
            cin >> r;
        }
        for(int ii=0;ii<i;++ii) {
            if(is_complemented) {
                a[ii] = 1 - a[ii];
                a[B-1-ii] = 1 - a[B-1-ii];
            }
            if(is_reversed) {
                swap(a[ii], a[B-1-ii]);
            }
        }

        for(int j=0;j<4&&i+j<B/2;++j) {
            read_pair(i+j);
        }
    }

    for(int i=0;i<B;++i) {
        cout << a[i];
    }
    cout << endl;
    char c;
    cin >> c;
    return c == 'Y';
}

int main() {
    int T;
    cin >> T >> B;
    while(T-- && solve());
}

所感

太字部分は私が誤読していた部分です。

Typical DP Contest J - ボール

問題: J - ボール

問題概要

$N (\leq 16)$ 個の障害物が $x$ 軸上に置かれていて,$i$ 番目の障害物の座標は $x_i (0 \leq x_i \leq 15)$ である。

すぬけ君がボールを座標 $x$ めがけて投げると,$x-1$,$x$,$x+1$ にそれぞれ $\frac{1}{3}$ の確率で飛んでいき,当該座標にあった障害物が倒れる。

すぬけ君の目的はボールを投げてこの障害物をすべて倒すまでにボールを投げる回数の期待値を求めよ。

ただしボールを投げる場所は,前に投げたボールの飛んだ場所を見てから決めることができる。

解法概要

制約が bitDP と言っているので,

$dp_{i} = i$ で表される障害物の集合がまだ倒されていないときの,すべての障害物を倒すまでにボールを投げる回数の期待値

とする。

初期値は $dp_0 = 0$ である (ただし $0$ は空集合 $\emptyset$ に対応している)。

次に遷移を考える。Sample Input1 (下記) を使って考える。

2
0 2

${0}$ という集合 ($i=2$ に対応しているとする) から $\emptyset$ への遷移については,ボールを $x$ めがけて投げるときの $x$ を適切に決めたとすると

$$dp_2 = \frac{1}{3} (dp_0+1) + \frac{2}{3} (dp_2+1)$$

という関係式ができる。右辺は,次にとりうる状態に対応する期待値に次の状態に遷移するための操作回数1回を足したものと,その確率をかけて足し合わせたものになっている。求めたい $dp_2$ が左辺にだけ現れるように式変形をすると

$$(1-\frac{2}{3}) dp_2 = \frac{1}{3} dp_0 + (\frac{1}{3} + \frac{2}{3})$$

$$dp_2 = dp_0 + 3$$

$dp_0 = 0$ より

$$dp_2 = 3 \texttt{.}$$

${2}$ という集合 ($i=1$ に対応しているとする) から $\emptyset$ への遷移や,${0, 2}$ という集合 ($i=3$ に対応しているとする) から $\emptyset$ への遷移も同様にして考えることができる。これらを一般化して考えると

$$(1 - \frac{\mathit{cnt}_\mathit{next}}{3}) dp_i = \sum_{j \in \mathit{next}(i, x)} \frac{1}{3} (dp_j + 1)$$

$$dp_i = \frac{3}{3 - \mathit{cnt}_\mathit{next}}\sum_{j \in \mathit{next}(i, x)} \frac{1}{3} (dp_j + 1) = \frac{3}{3 - \mathit{cnt}_\mathit{next}} (1 + \sum_{j \in \mathit{next}(i, x)} \frac{1}{3} dp_j ) \texttt{.}$$

ただし,$\mathit{cnt}_\mathit{next}$ は次の状態としてありうるもの (自分自身は除く) の数であり,$\mathit{next}(i, x)$ は $x$ めがけてボールを投げるときに $i$ の次の状態としてありうる状態の集合である。

ここまで,$x$ を適切に決めたという仮定を置いていたが,$0 \leq x \leq 15$ なので,各状態ペアの遷移について $x$ をすべて試しても間に合う。

ソースコード

#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;++i) {
        cin >> a[i];
    }

    vector<double> dp(1<<n, 0.0);
    for(int bi=1;bi<(1<<n);++bi) {   // どの障害物が残っているかの状態
        dp[bi] = 10000.0;
        for(int x=0;x<=15;++x) {
            double tmp_dp = 0.0;
            int tmp_cnt = 3;
            for(int i=0;i<n;++i) {
                if((bi & (1<<i)) == 0 or abs(a[i]-x) > 1) continue; // 既にない / 射程距離にいない障害物は墜とせない
                tmp_dp += 1.0/3.0 * dp[bi^(1<<i)];
                --tmp_cnt;
            }
            if(tmp_cnt == 3) continue;
            tmp_dp += 1;
            tmp_dp *= 3.0 / (3-tmp_cnt);
            if(dp[bi] > tmp_dp) dp[bi]= tmp_dp;
        }
    }

    cout << setprecision(10) << fixed << dp[(1 << n) - 1] << endl;
}

所感

Educational DP Contest も J は期待値だったね

J - Sushi

Typical DP Contest I - イウィ

問題: I - イウィ

問題概要

i と w からなる文字列 $s (|s| \leq 300)$ から iwi を削除し残った文字列を連結する操作を繰り返す。

最大何回操作できるか答えよ。

解法概要

$\mathit{dp}_{i, j} := i$ 文字目 (ソースコードでは 0-indexed) から始まる j 文字の部分文字列に対して最大何回操作できるか

を求める。

$j \% 3 \neq 0$ について $\mathit{dp}_{i, j}$ を求めようとするとややこしいので,$j \% 3 = 0$ についてのみ考え,全体での操作回数は$j \% 3 = 0$ についての場合からうまいこと計算する。

消せるパターンを考えてみると,

  • iwi そのもの
  • (消える文字列)(消える文字列)
  • i(消える文字列)wi
  • iw(消える文字列)i
  • i(消える文字列)w(消える文字列)i

がある。iwiは,それぞれの文字の間に0文字の文字列があると考えると一番最後のパターンになるので,全部で 4 パターンということになる。これを短い部分文字列から順に計算していく。ここでは,長さが3の倍数の文字列だけ考えれば良い。また,1回の操作で3文字消えることを考えると,(消える文字列) は $\mathit{dp}_{i, j} = \frac{j}{3}$ であるような文字列である。遷移の詳細はソースコードを見た方が早い。

上記の計算では,完全に消せる部分文字列については正しい操作回数が求められるが全体の最大操作回数が求まっているとは限らない。そのため,最後に別の DP で全体の最大操作回数を求める必要がある。

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.length();

    vector<vector<int>> dp(n, vector<int>(n+1, 0));
    for(int j=3;j<=n;j+=3) {
        for(int i=0;i+j<=n;++i) {
            // (消せる)(消せる) の形
            for(int k=i+1;k<i+j;++k) {
                if(dp[i][k-i] * 3 == k-i && dp[k][i+j-k] * 3 == i+j-k) {
                    dp[i][j] = max(dp[i][j], dp[i][k-i] + dp[k][i+j-k]);
                }
            }
            // i(消せる)wi の形
            if((s[i] == 'i') && (dp[i+1][j-3] * 3 == j-3) && (s[i+j-2] == 'w') && (s[i+j-1] == 'i')) {
                dp[i][j] = max(dp[i][j], dp[i+1][j-3]+1);
            }
            // iw(消せる)i の形
            if((s[i] == 'i') && (s[i+1] == 'w') && (dp[i+2][j-3] * 3 == j-3) && (s[i+j-1] == 'i')) {
                dp[i][j] = max(dp[i][j], dp[i+2][j-3]+1);
            }
            // i(消せる)w(消せる)i の形
            for(int j1=0;j1<=j-3;j1+=3) {
                int j2 = j-3-j1;
                if((s[i] == 'i') && (dp[i+1][j1] * 3 == j1) && (s[i+j1+1] == 'w') && (dp[i+j1+2][j2] * 3 == j2) && (s[i+j-1] == 'i')) {
                    dp[i][j] = max(dp[i][j], dp[i+1][j1] + dp[i+j1+2][j2]);
                }
            }
        }
    }

    vector<int> cnt(n+1, 0);
    for(int i=0;i<n;++i) {
        for(int j=0;i+j<=n;++j) {
            cnt[i+j] = max(cnt[i+j], cnt[i] + dp[i][j]);
        }
        cnt[i+1] = max(cnt[i+1], cnt[i]);
    }

    cout << cnt[n] << endl;
}

所感

解いてるときは四苦八苦したのに終わってみると簡単に見えてしまう