AtCoder Grand Contest 002:B - Box and Ball

問題

https://atcoder.jp/contests/agc002/tasks/agc002_b

考え方

実験??実験のコツがわかるようになりたい...。

赤いボールが入っている箱から M 回の操作によって到達できる可能性がある箱については赤いボールが入りうる。ただし操作後に操作元の箱 x が空になる場合はその箱には赤いボールが入っていることはない。

これをシミュレーションすればよい。

Submission #4351818 - AtCoder Grand Contest 002

実験用コード

到達可能性について、editorialにように言われればまぁ理解できるが、なかなかぱっと正当性がわからない...。ちなみに以下が実験したコードというかぱっと思いついたdp解...

       public void solve(int testNumber, MyInput in, PrintWriter out) {

            int n = in.nextInt(), m = in.nextInt();

            // i 回目の操作で箱 j に赤いボールが r 個、白いボールが b 個入っている可能性があるかどうか
            boolean[][][][] dp = new boolean[m+1][n][n+1][n+1];
            for (int i = 0; i < n; i++) {
                dp[0][i][i == 0 ? 1 : 0][i != 0 ? 1 : 0] = true;
            }

            for (int i = 0; i < m; i++) {
                int x = in.nextInt()-1, y = in.nextInt()-1;

                // 赤いボールと白いボールがある場合
                boolean done = false;
                for (int r = 1; r <= n; r++) {
                    for (int w = 1; w <= n; w++) {
                        if (dp[i][x][r][w]) {

                            // 赤いボールを渡す場合
                            for (int r2 = 0; r2 <= n; r2++) {
                                for (int w2 = 0; w2 <= n; w2++) {
                                    if (dp[i][y][r2][w2]) {
                                        dp[i+1][y][r2+1][w2] = true;
                                        dp[i][x][r][w] = false;
                                        dp[i+1][x][r-1][w] = true;
                                    }
                                }
                            }

                            // 白いボールを渡す場合
                            for (int r2 = 0; r2 <= n; r2++) {
                                for (int w2 = 0; w2 <= n; w2++) {
                                    if (dp[i][y][r2][w2]) {
                                        dp[i+1][y][r2][w2+1] = true;
                                        dp[i][x][r][w] = false;
                                        dp[i+1][x][r][w-1] = true;
                                    }
                                }
                            }

                            done = true;
                        }
                    }
                }

                // 赤いボールしかない場合
                if (!done) {
                    for (int r = 1; r <= n; r++) {
                        if (dp[i][x][r][0]) {

                            // 赤いボールを渡す場合
                            for (int r2 = 0; r2 <= n; r2++) {
                                for (int w2 = 0; w2 <= n; w2++) {
                                    if (dp[i][y][r2][w2]) {
                                        dp[i+1][y][r2+1][w2] = true;
                                        dp[i][x][r][0] = false;
                                        dp[i+1][x][r-1][0] = true;
                                    }
                                }
                            }

                            done = true;
                        }
                    }
                }

                // 白いボールしかない場合
                if (!done) {
                    for (int w = 1; w <= n; w++) {
                        if (dp[i][x][0][w]) {

                            // 白いボールを渡す場合
                            for (int r2 = 0; r2 <= n; r2++) {
                                for (int w2 = 0; w2 <= n; w2++) {
                                    if (dp[i][y][r2][w2]) {
                                        dp[i+1][y][r2][w2+1] = true;
                                        dp[i][x][0][w] = false;
                                        dp[i+1][x][0][w-1] = true;
                                    }
                                }
                            }
                        }
                    }
                }

                if (!done) new RuntimeException();

                // 直前の状態のマージ(移動しなかった分)
                for (int j = 0; j < n; j++) {
                    if (j == y) continue;
                    for (int r = 0; r <= n; r++) {
                        for (int w = 0; w <= n; w++) {
                            dp[i+1][j][r][w] |= dp[i][j][r][w];
                        }
                    }
                }
            }

            // m回操作後の最終的な状態で赤いボールが入っている可能性がある箱の数を数える
            int ans = 0;
            for (int i = 0; i < n; i++) {
                boolean ok = false;
             top:
                for (int r = 1; r <= n; r++) {
                    for (int w = 0; w <= n; w++) {
                        if (dp[m][i][r][w]) {
                            ok = true;
                            break top;
                        }
                    }
                }
                if (ok) ans++;
            }
            out.println(ans);
        }

どこに着目して考察するべきだったか

実験をすると分かる

何がバグっていたか

得た知見(典型ポイント)

  • 実験して法則を見出す
  • シミュレーション

類題

yukicoder:No.793 うし数列 2

問題

https://yukicoder.me/problems/no/793

考え方

うし数列を 10 進数で桁ごとに考える。例えば E_3 = 1333 の場合、

\displaystyle 1333 = 10^3 + 3 * 10^2 + 3 * 10^1 + 3 * 10^0 = 10^3 + 3 * (10^0 + 10^1 + 10^2) = 10^3 + 3 * \frac{10^3-1}{9}

となる。項をまとめるのに等比数列の和の公式を用いた。そうすると後は各項ごとに modつきの累乗を取り、9 で割る操作は逆元を取れば良い。

#318620 No.793 うし数列 2 - yukicoder

どこに着目して考察するべきだったか

数を 10 進数で見て、桁ごとに考えると解ける。

何がバグっていたか

得た知見(典型ポイント)

類題

全国統一プログラミング王決定戦 エキシビジョン:F - コラッツ問題

問題

https://atcoder.jp/contests/nikkei2019-ex/tasks/nikkei2019ex_e

考え方

サンプル2から f(1789997546303)=1000 であることが分かっているので、これを利用する。

f(N)=P を満たす Nmemo_P とすると f(memo_{1000}) = 1000 である。この結果の両辺に -1 すると

f(memo_{1000}) - 1 = 1000 - 1 = 999

となる。左辺は X の偶奇によって仮定の式を適応することができて memo_{1000} は奇数であるから

f(memo_{1000}) - 1 = f(3 * memo_{1000} + 1) + 1 - 1 = f(3 * memo_{1000} + 1)

となる。まとめると

f(3 * memo_{1000} + 1) = 999

となるから、これによって memo_{999} = 3 * memo_{1000} + 1

となることが分かる。偶数の場合も同様だが、memo_{998} の結果を求めてみよう。

f(memo_{999}) = f(5369992638910) = 999 であり X = memo_{999} は偶数である。この両辺に -1 すると

\displaystyle f(memo_{999}) - 1 = f(\frac{memo_{999}}{2}) + 1 - 1 = f(\frac{memo_{999}}{2}) = 998

であることから \displaystyle memo_{998} = \frac{memo_{999}}{2} であることが分かる。

このようにして memo_P から memo_{P-1} の結果を得ることができるので memo_{1000} から順番に memo_{1} まで求めることができる。

Submission #4347375 - 全国統一プログラミング王決定戦 エキシビジョン

どこに着目して考察するべきだったか

何が求められているか整理するとサンプル2の両辺から-1をすることで求めたい値を得ることができることが分かる。

何がバグっていたか

得た知見(典型ポイント)

類題

雑記

ちょっと冗長になってしまった...

全国統一プログラミング王決定戦本戦:C - Come Together

問題

https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_c

考え方

難しいが過去にも300点で似たような問題があるので、点数は相応な気はする...

どこに着目して考察するべきだったか

まずは H 軸、W 軸ごとに独立して考えることにしよう。W 軸についてコマを揃えることを考える。

サンプル 1 の例で考えると以下の図のようにそれぞれの列ごとに 1 0 2 マスのコマがあることになる。

f:id:d_tutuz:20190222153255p:plain

これをある列 x にすべて揃えたい。i 列目にあるコマの数を cnt_i 個としよう。その時のコストを f(x) とすると

f(x) = \displaystyle \sum_{i=1}^W |x - i| * cnt_i

である。この関数 f(x) の最小値を求めたいが、各 x\ (1 \le x \le W) について考えると O(W^2) となり間に合わない。しかし f(x) は凸関数であることに気づくと三分探索を用いることができて計算量 O(WlogW) で最小値を求めることができる。

よって W 軸についてある位置 x にするときの最小値を求めることができた。H 軸についても同様に最小値を求めて、それぞれの最小値の和が解となる。

Submission #4345231 - 全国統一プログラミング王決定戦本戦

何がバグっていたか

得た知見(典型ポイント)

  • xy軸を独立に考える
  • 差の絶対値の和は三分探索
  • 中央値で最小値を取る

類題

SoundHound Inc. Programming Contest 2018 -Masters Tournament-:E - + Graph

問題

https://atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_e

考え方

考えていたこと

グラフは連結であるから、ある頂点のコストを決め打ちすると頂点と辺の関係から他の頂点のコストが一意に決まることが分かる。なのでまずは頂点 0 のコストを 0 として考えることとする。

そのとき頂点のコストを 0 から 1 に変化させると、偶数長の頂点は + の変化をして、奇数長の頂点は - の変化をすることが分かる。

がサンプル1のようにある頂点が偶数長にも奇数長にもなりうる場合にどうしていいかわからず...

解説見た

グラフが二部グラフであるかそうでないかが重要。二部グラフの場合、各頂点の偶奇は一意に決まるので、頂点 0 のコストを 0 できめうちして各頂点のコストを計算した後に、それぞれの頂点が 0 以下にならないように初期値の幅を調整すれば良い。このときの初期値の候補が求める場合の数である。

二部グラフではない場合は、実は場合の数は高々 1 通りになる。ある頂点について、奇数長でのコストを a - t とし、偶数長でのコストを b + t とすると、これらが一致するときの t\displaystyle \frac{|a-b|}{2} で定まるためである。サンプル1の場合、以下の図のイメージ。グラフが2面あることをイメージすると理解しやすかった。

f:id:d_tutuz:20190221211350j:plain:w300

よって \displaystyle t=\frac{|a-b|}{2} として頂点 0 から再度 dfs で各頂点のコストを求めたときにそれぞれの頂点のコストが 0 以下にならなければ解は 1 そうでなければ 0 となる。

Submission #4339483 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-

実装テク

偶奇分の二回グラフを計算すると実装が楽。kmjpさんの実装を参考にした。

    // [初期コスト][偶奇][頂点] = コスト
    cost = new long[2][2][n];

    void dfs(int id, int st, int cur, long v) {
        if (cost[id][st][cur] == LINF) {
            cost[id][st][cur] = v;
            for (P p : g[cur]) {
                dfs(id, st^1, p.t, p.c - v);
            }
        }
    }

どこに着目して考察するべきだったか

頂点 0 からの長さの偶奇が重要である。また与えられたグラフが二部グラフであるかどうかがポイントであった。

何がバグっていたか

得た知見(典型ポイント)

  • 偶奇性から二部グラフを考える

類題

参考

CODE FESTIVAL 2018 Final (Parallel):D - Three Letters

問題

https://atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_d

考え方

考えていたこと

文字  A_i の長さについて 3 つの箇所を全探索というナイーブな考察以外に思いつかなかった...。3 文字なので、真ん中を固定して全探索して考えるとうまくいくことも多いが、解法は思いつかなかった。

あとは、最頻出の文字列について文字数が DP で求められたとすると文字列を復元できないか?最頻出の文字数が x 文字だとすると x は単調性があって二分探索でうまいことできないか?...などという明後日の方向の考察しか出てこなかった...。

解説見た

文字列の略称の候補を全探索する。その際に各文字について真ん中の文字 1 つを全探索して、左右の文字の候補については文字種類数で全探索する。略称の候補を数えるためには部分文字列のみが必要であって、文字の位置は問わないため。

そうすると計算量は \displaystyle O(\sum_{i=0}^{n-1} |S_i| * 52^2) = O(90000 * 52^2) \approx O(2.4 * 10^8) となり、C++で実装すると間に合う。Java だと TLE するのでかなり定数倍が重い。

実装テク

  • 左右の文字列の計算

ある文字についてその文字位置の左右に登場する文字数を計算するのは、予め文字位置の右に登場する文字を前計算し、文字を進めるごとにその文字を -1 し、左に登場することにするとよい。以下のような実装になる。

    int m = str.length;
    int[] L = new int[52], R = new int[52];
    fill(used, false);

    for (char c : str) R[c2i(c)]++;

    for (int i = 0; i < m; i++) {
        int n = c2i(str[i]);
        R[n]--;
        for (int left = 0; left < 52; left++) {
            for (int right = 0; right < 52; right++) {
                if (L[left] >= 1 && R[right] >= 1 && !used[left][n][right]) {
                    max = Math.max(max, ++cnt[left][n][right]);
                    used[left][n][right] = true;
                }
            }
        }
        L[n]++;
    }

Submission #4332300 - CODE FESTIVAL 2018 Final (Parallel)

どこに着目して考察するべきだったか

3 文字の真ん中を全探索。文字種類が 52 であるから、\displaystyle O(\sum_{i=0}^{n-1} |S_i| * 52^2) はギリギリ間に合うかも...という気持ちになると解ける。

何がバグっていたか

得た知見(典型ポイント)

  • 3点の真ん中を全探索

類題

AtCoder Regular Contest 058:E - 和風いろはちゃん / Iroha and Haiku

問題

https://atcoder.jp/contests/arc058/tasks/arc058_c

考え方

考えていたこと

条件を満たす数列はどのような数列であるか考えた。

x, y, z, w を全探索する。そのとき [x, y-1], [y, z-1], [z, w-1]区間の長さを求めておいて、各区間の長さの要素の和が X, Y, Z なる要素の組み合わせを考えると、これは重複組合せで求めることができる。範囲に含まれない要素は [1, 10] の任意の数を選択できる...

みたいな考察を進めていた。がサンプル3で合わず。よく考えると、範囲外の要素で XYZ の数列が含まれるので数列を重複して数えていることになる。

解説見た

余事象の数え上げを考える。余事象のほうが数え上げやすいため。数列の要素ごとに左から全探索していくことを考える。例えば X=1, Y=2, Z=1 という XYZ の組み合わせを考えると、X Y が決まっていたとすると、どういうときに次の数 Z を選べないか。

それまでの数字の和が 1 2 となる場合は次に Z として 1 をとることはできない。 XYZ121 になってしまうため。

数列の状態を bit で考えることにしよう。X+Y+Z \le 17 であるから 2^{X+Y+Z} \le 2^{17} \approx 1.3 * 10^5 として状態を持つことができる。

今までの数列の和の状態が左から 1 2 となる場合に bit として 110 となっているとしよう。このように bit で状態をもつことを考えることがこの問題を bitDP で解くために重要な考察な気がする。このとき Z として 1 をとることを考えると bit の状態は 1101 となる。これは bit の下位(0-indexed)から考えて Z=1, Y=2, X=1 となっているので状態として遷移することができない。そうでない場合、例えば Z=3 などを選ぶ場合は 110100 となるので遷移することができる。

よって次のようなメモ化全探索を考えよう

f(i, state) := i 桁目まで考えて数列の状態が state であるような場合の数

DP遷移は i 桁目に数 j をとるとすると next = state << j | 1 << j - 1 となる(実装のまんま)。これが XYZ にならないとき、つまり next >> z - 1 && next >> y + z - 1 && next >> x + y + z - 1 にならないときのみ遷移可能

Submission #4328265 - AtCoder Regular Contest 058

何がバグっていたか

  • ダブって数え上げしてしまう

得た知見(典型ポイント)

  • 余事象を考える
  • 状態を bit でもって全探索

類題