Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

7日目 みんなのプロコン2019 予選

atcoder.jp

ABCDF5完で久々の橙パフォ。人々、問題を解きすぎ。

f:id:misteer:20190210014747p:plain


D. Ears (600)

D - Ears

概要

数直線があり、 1から Lの各点には空の箱が置かれている。

すぬけ君はこの数直線上を、以下のルールに従って移動をする。

  •  [0, L]の区間のみを移動する。
  • 始点と終点の座標は整数である。
  • 座標が整数の点でのみ折り返す。

ある整数 iによって i - 0.5と表せる座標を通過する度に、すぬけ君は座標 iにある箱に石を1個入れる。

その後りんごさんが数直線上に来て、箱 iに入っている石の数が A_i個になるように以下の操作を行う。

  • 1つの箱から石を1つ取り除く。
  • 1つの箱に石を1つ入れる。

このとき、りんごさんの操作回数の最小値を求めよ。

制約

  •  1 \leq L \leq 2 \times 10^5
  •  1 \leq A_i \leq 10^9

考察

この問題でまず重要なのが、問題を分かりやすく換言することだったりする。というのも上の問題文は既に言い換えをしたもので、原文は問題設定が奇抜すぎてとても読みにくい。


まず石の置き方について色々模索した結果、以下の区間が左から順に並んでいる場合は自由に実現できることが分かった。

  • 何も置かない区間
  • 偶数個の石が置かれた区間
  • 奇数個の石が置かれた区間
  • 偶数個の石が置かれた区間
  • 何も置かない区間

言い換えの過程で勘違いや混乱が生まれて、ここまで地味に15分くらいかかっている。

「では各区間の端点を探索しよう」となったのだが、これは愚直にやると O(L^4)の計算量が必要で、どれだけ工夫してもあまりにも厳しい。ここでしばらく詰まってしまい、「方針ミスったかもな〜」などと思い始める。

しかしふと「困ったときのDP頼み」という教訓(?)を思い出し、DPを適用できないか考えたらこれが大正解だった。


上の5つの区間に0から4の値を割り振る。そして dp_{i, k} = [1, i]のみを見たとき、箱 i区間 kに属するような石の置き方における最適解」というDPを考える。

更新は貰うDPで、 dp_{i + 1, k} = \min_{0 \leq l \leq k} (dp_{i, l}) + f(k, A_{i + 1})となる。ここで f(k, a)は「 a区間 kに属するときにかかる最小操作数」とする。これは場合分けで簡単に書ける。

答えは \max_{0 \leq k \leq 4} dp_{L, k}となるが、これは A_{L + 1} = 0として L + 1個目の箱を置くことで dp_{L + 1, 4}と一致し、実装が少し楽になる。

実装例

このくらいのDPの実装は、最近の精進で慣れたものである。

#include <iostream>
#include <algorithm>

using namespace std;
using ll = long long;

const ll INF = 1LL << 50;

ll f(int k, ll a) {
    if (k == 2) {  // 奇数の区間
        return (a + 1) % 2;
    } else if (1 <= k && k <= 3) {  // 偶数の区間
        return (a == 0 ? 2 : a % 2);
    } else {  // 無の区間
        return a;
    }
}

int main() {
    int N;
    cin >> N;
    ll a[N + 2];
    for (int i = 1; i <= N; ++i) cin >> a[i];
    a[N + 1] = 0;

    ll dp[N + 2][5];
    fill(dp[0], dp[1], 0);
    fill(dp[1], dp[N + 2], INF);

    for (int i = 1; i <= N + 1; ++i) {
        for (int k = 0; k < 5; ++k) {
            ll m = *min_element(dp[i - 1], dp[i - 1] + k + 1);
            dp[i][k] = m + f(k, a[i]);
        }
    }

    cout << dp[N + 1][4] << endl;
    return 0;
}

反省

DPに気づくまで随分と時間がかかった、まだ頭にDPが染み付いていないという感じがある。染み付いてほしくはないけど。

でも実装がとても早かったと思う。こどふぉ精進の成果か。


F. Pass (900)

F - Pass

概要

 N人のすぬけ君が一列に並んでいる。最初 i人目のすぬけ君は赤か青のボールを2つ持っている(具体的に何を持っているかは、文字列として入力で与えられる)。

ここで、以下の操作を 2N回繰り返すことでボール列を作る。

  •  i \geq 2について、 i人目のすぬけ君は、持っているボールのうち1つを i - 1人目のすぬけ君に渡す。
    • ボールを持っていなければ何もしない。
  •  1人目のすぬけ君は、持っているボールのうち1つをボール列の末尾に置く。

なお、これらの受け渡しは同時に行われる。

こうして作られたボール列として考えうるものの数を、 998244353で割った余りを求めよ。

制約

  •  1 \leq N \leq 2,000

考察

Dが終わった時点でなぜかEよりFの方が正解者数が多かったのでこっちを選んだ。


問題風景をイメージすると、2回操作した時点で一番後ろの人がボールを持たなくなることが分かる。そこでまず最初2回の操作に注目し、「最初2回の操作を行った時点でのボール列」を全部列挙した。

すると、1回目は1人目が持っているボールしか選べないが、2回目は2人目が持ってるボールも自由に選べると気づく。

ここから帰納的に、「 i回目での操作では i人目までのボールを自由に選べる」ことが分かった。これに気づいてしまえば、後はウィニングランである。


 dp_{r, b} =「赤いボールを r個、青いボールを b個並べる方法」とする。赤いボール、青いボールの総数をそれぞれ R, Bとしたとき、答えは dp_{R, B}となる。

赤いボールが r個、青いボールが b個並んだ状態を考える。次の操作は r + b + 1回目なので、 r + b + 1人目までの赤いボールの個数が rを上回っていれば赤いボールを置くことができる。よってこのとき dp_{r + 1, b} += dp_{r, b}という遷移ができる。青いボールも同様。

 r + b \geq Nのときは場合分けが必要になるが、これは「 i人目( i \gt N)までのボールの数は、 N人目までのボールの数と同じ」と見なせば場合分けが不要になる。

実装例

 4,000 \times 4,000の配列ってMLEしそうだなと思ったが、意外と大丈夫だった。

#include <iostream>
#include <string>

using namespace std;
using ll = long long;

const ll MOD = 998244353;

ll dp[4010][4010];

int main() {
    string S;
    cin >> S;
    int N = S.length();

    int rsum[N * 2 + 1], bsum[N * 2 + 1];
    rsum[0] = bsum[0] = 0;
    // 各ボール数の累積和 (1-indexed)

    for (int i = 1; i <= N; ++i) {
        rsum[i] = rsum[i - 1] + ('2' - S[i - 1]);
        bsum[i] = bsum[i - 1] + (S[i - 1] - '0');
    }
    for (int i = N + 1; i <= N * 2; ++i) {
        rsum[i] = rsum[i - 1];
        bsum[i] = bsum[i - 1];
    }

    dp[0][0] = 1;
    for (int r = 0; r <= rsum[N]; ++r) {
        for (int b = 0; b <= bsum[N]; ++b) {
            if (r == rsum[N] && b == bsum[N]) continue;

            // 赤ボールを置けるか?
            if (rsum[r + b + 1] > r) {
                dp[r + 1][b] += dp[r][b];
                dp[r + 1][b] %= MOD;
            }

            // 青ボールを置けるか?
            if (bsum[r + b + 1] > b) {
                dp[r][b + 1] += dp[r][b];
                dp[r][b + 1] %= MOD;
            }
        }
    }

    cout << dp[rsum[N]][bsum[N]] << endl;
    return 0;
}

反省

ぶっちゃけDより簡単だったが、解く順番を変えても成績は変わらないのでまぁ。

考察と実装の速度については十分速かったと思う。今の私に「これ以上速く」というのは厳しい気がする。


感想

  • 全体的に申し分ない結果だった。
  • 強いて言えばDのDPにもっと早く気づきたかったか。
  • それにしてもAtCoder全体のレベルが高すぎる。