Mister雑記

競プロやります。

6日目 Codeforces Global Round 1

codeforces.com

ABCDEの5完、薄橙に復帰。

f:id:misteer:20190208031352p:plain

D. Jongmah [2200]

Problem - D - Codeforces

概要

 m以下の正整数が書かれた n個の牌がある。 i個目の牌には a_iと書かれている。

このとき、以下の2種類の3枚組を合わせて最大何組作れるか求めよ。ただし1つの牌は1つの組にしか含めてはならない。

  • 同じ数が書かれた牌3枚からなる組。
  • ある正整数 kについて、 (k, k + 1, k + 2)が書かれた牌それぞれ1枚からなる組。

制約

  •  1 \leq n, m \leq 10^6
  •  1 \leq a_i \leq m

考察

以降、 iが書かれた牌の数を cnt_iとする。

「何かAtCoderで似た問題あったな」ということで「Simplified mahjong」をちょっと見る。この解法が「数が小さい方から組を作り続ける貪欲」だったので、今回も貪欲だろうと目星をつける。

しかし前の2つの牌から戦略を決めようとすると、

  • 2 3 3 3 4 4 4
  • 2 3 3 3 4 4 4 5 5

のように「順子を作らないのが最善」のときと「順子を作るのが最善」のケースがあり、貪欲でやるには場合分けが地獄だなと悟る。

そこでふと気がつく。「DPなら勝手に場合分けしてくれるのでは?」

DPは値をより良い方に更新することで最適解を求めるものだが、その更新が場合分けの働きをしてくれる、ということである。

というわけで以下のようなDPを書いた。

  •  dp_{i, p, q} = i - 1までの牌を処理し終わった時点で、 iの牌が p個、 i + 1の牌が q個既に順子で使われているようなケースの、組数の最大値。
    • ただし、 iの牌が p個、 i + 1の牌が q個あることは保障されていない。

このとき答えは dp_{m + 1, 0, 0}となる。

更新は、 iの牌を起点とする順子を s個作るとしたときに、 dp_{i + 1, q + s, s} dp_{i, p, q} + s + \frac{cnt_i - s - p}{3}で緩和すればよい。ただし s \leq cnt_i - pで、 cnt_i \lt pなら遷移はなしとする。

順子3組は刻子に置き換えられるので、 0 \leq s \leq 2だけ試せばいい。ここから 0 \leq p \leq 4, 0 \leq q \leq 2が保障される。

実装例

遷移が少し複雑で実装も難しめ。しかし本番ではなぜかバグもなくスラスラ実装できた。

#include <iostream>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    int cnt[m];
    fill(cnt, cnt + m, 0);
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        ++cnt[--a];  // 0-indexedに変換
    }

    int dp[m + 1][5][3];
    fill(dp[0][0], dp[m + 1][0], 0);

    for (int i = 0; i < m; ++i) {
        for (int p = 0; p < 5; ++p) {
            for (int q = 0; q < 3; ++q) {
                for (int s = 0; s < 3; ++s) {
                    if (p + s > cnt[i]) continue;  // 牌が足りない
                    int c = (cnt[i] - p - s) / 3;  // 作れる刻子の数
                    dp[i + 1][q + s][s] = max(dp[i + 1][q + s][s], dp[i][p][q] + s + c);
                }
            }
        }
    }

    cout << dp[m][0][0] << endl;
    return 0;
}

反省

DPは計算結果を記録して処理を高速化するものだが、今回のように「場合分けや考察の負荷を減らす」という役割を持つことが往々にしてある。汎用性が高いのになぜか頭から消えがちなので、常に意識しておく癖をつけたい。


E. Magic Stones [2200]

Problem - E - Codeforces

概要

長さ nの数列 \{c_i\} \{t_i\}が与えられる。

ここで、 \{c_i\}について以下のような操作を考える。

  •  2 \leq i \leq n - 1なる iを選ぶ。
  •  c_i c_{i - 1} - c_i + c_{i + 1}に置き換える。

この操作を何度か行うことで、 \{c_i\} \{t_i\}に一致させることが可能か判定せよ。

制約

  •  2 \leq n \leq 10^5
  •  0 \leq c_i, t_i \leq 2 \times 10^9

考察

問題を見て、とりあえず手を動かす。

まず重要な気づきとして、

  • 両端の要素は変えられないため、 c_1 = t_1, c_n = t_nは必要条件。
  • 同じ要素に対して2回連続で操作を行うと元に戻る。

と分かる。

そして具体的に、 n = 4の一般化したケースで元に戻るまで遷移を紙に書いていた。

その後、なぜかふと「差分取ったら何かいいことないかな」と思い、さっきの遷移を差分について書き直してみた。これがビンゴで、差分だけ見ると操作は「隣り合う2要素をswapする」ことと同値であることに気づく。数式で書くと、

  •  (c_{i-1}-c_i+c_{i+1})-c_{i-1}=c_{i+1}-c_i
  •  c_{i+1}-(c_{i-1}-c_i+c_{i+1})=c_i-c_{i-1}

となり、見事に入れ替わっていることが分かる。

swapは何度も繰り返すことで任意の並び替えを実現できる。よって \{c_i\}, \{t_i\}それぞれについて差分の数列をとり、ソートして比較すればよい。

実装例

分かってしまえば実装自体は秒殺である。

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    int c[2][n];
    for (int t = 0; t < 2; ++t) {
        for (int i = 0; i < n; ++i) cin >> c[t][i];
    }

    // 必要条件:両端の一致
    if (c[0][0] != c[1][0] || c[0][n - 1] != c[1][n - 1]) {
        cout << "No" << endl;
        return 0;
    }

    int d[2][n - 1];  // 差分の数列
    for (int t = 0; t < 2; ++t) {
        for (int i = 0; i < n - 1; ++i) d[t][i] = c[t][i + 1] - c[t][i];
        sort(d[t], d[t] + n - 1);
    }

    // 差分の数列を比較
    bool judge = true;
    for (int i = 0; i < n - 1; ++i) {
        if (d[0][i] != d[1][i]) judge = false;
    }

    cout << (judge ? "Yes" : "No") << endl;
    return 0;
}

反省

「差分を取る」ところで発想の飛躍があるが、この発想に至ったのは完全なまぐれではなく、過去に何度か「差分を取ると格段に見通しが良くなる」という考え方に出会ってきたことによる。実際AGCにもこれとほぼ同じ発想を要求する問題があり、その問題による影響が大きいと思われる。

ところで「2つの数列が一致しているか」を判定する関数はSTLライブラリにないのだろうか。


感想

  • Cの実装で詰まってしまったのが痛手だったが、DEで挽回できた。
  • Dをすばやく実装できたのはとても偉いと思う。