Mister雑記

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

Codeforces Round #512 (Div2) - E 「Vasya and Good Sequences」 [2100]

codeforces.com

概要

正整数列 \{a_i\}に以下の操作を何度か施すことで、全てのXORを取った値が 0になるようにできるとき、 \{a_i\}を「良い数列」と呼ぶことにする。

  • 要素 a_iを任意に選ぶ。
  •  a_iを2進数表記し、任意の2つのbitを交換する。

長さ Nの正整数列 \{a_i\}の連続部分列で、「良い数列」であるものの個数を求めよ。

制約

  •  1 \leq N \leq 3 \times 10^5
  •  1 \leq a_i \leq 10^{18}

考察

まず操作について考える。正整数 aを2進数表記したときの 1の数を nとする。この aに上の操作を何度か施すことによって、 1の数が nであるような任意の数に変換できることが分かる。 したがって、 a_iの代わりに「 a_iを2進数表記したときの 1の数」だけを保持すればよい。この数列を \{b_i\}とする。


次に、ある数列が「良い数列」となる条件を調べる。XORの性質を考えると、以下のことが分かる。

  •  \{b_i\}に対して、「異なる2要素から 1ずつ引く」という操作を考える。この操作を繰り返すことで \{b_i\}を全て 0にできるとき、 \{b_i\}は「良い数列」である。

さらにこれは、証明が難しいが以下の2つの条件と同値になる。

  •  \{b_i\}の総和が偶数。
  •  \{b_i\}の最大値は、それ以外の値の総和以下である。

前者は明らか。後者については

  •  \{b_i\}を最大値とそれ以外に分ける。
  • 一方は最大値を 0になるまで減らし続ける。
  • もう一方は「それ以外の集合」の最大値を常に減らすようにする。

という戦略によって常に全て 0にできるはず。


よって上の2条件を満たす連続部分列の数を数え上げればいい。

まず1つ目の条件。 \{b_i\}の累積和を \{sum_i\}としたとき、 sum_r sum_lの偶奇が一致していることが条件となる。よって \{sum_i\}パリティからなる累積和を取れば、前者を満たす区間の数は十分高速に求まる。Zero-Sum Rangesと同じ手法。

ここから2つ目の条件を満たさないものを排除していくが、これは全ての区間を調べる必要はない。制約の 1 \leq a_i \leq 10^{18}から 1 \leq b_i \leq 60なので、長さ 61以上の区間は全て2つ目の条件を満たすことになる。よって長さ 60以下の区間だけ調べれば良い。

最大値を線形探索で求めると、計算量は 60 \times 60 \times n \leq 10^9程度になる。危ない数値だが、ループ内の処理は単純なので何とか間に合う。

実装例

累積和はindexがズレがちなので実装が疲れる。

#include <iostream>
#include <algorithm>

using namespace std;
using ll = long long;

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

    int b[N];
    for (int i = 0; i < N; ++i) {
        ll a;
        cin >> a;
        b[i] = __builtin_popcountll(a);
        // 立っているbitの数を数える 環境によっては使えないかも
    }

    ll sum[N + 1], psum[N + 1];
    // sum[i]  = 前からi個の累積和
    // psum[i] = j<=iかつsum[j]が奇数であるものの数 (parity sum)

    sum[0] = psum[0] = 0;
    for (int i = 0; i < N; ++i) {
        sum[i + 1] = sum[i] + b[i];
        psum[i + 1] = psum[i] + (sum[i + 1] % 2);
    }

    ll ans = 0;
    for (int r = 1; r <= N; ++r) {
        // sum[l]とsum[r]の偶奇が一致しているものを数え上げ
        if (sum[r] % 2 == 1) {
            ans += psum[r - 1];
        } else {
            ans += r - psum[r - 1];
        }
    }

    // 長さ60以下の区間を全探索
    for (int l = 0; l < N; ++l) {
        for (int r = l + 1; r <= min(N, l + 60); ++l) {
            int s = sum[r] - sum[l];  // b[l]+b[l+1]+...+b[r-1]
            if (s % 2 != 0) continue;

            int ma = *max_element(b + l, b + r);  // max(b[l], b[l+1], ..., b[r-1])
            if (ma * 2 > s) --ans;
        }
    }

    cout << ans << endl;
    return 0;
}

感想

  • 方針は合っていたが証明ができず、確信が持てなかった。
  • 実装は実装でindexズレやら勘違いで無限にバグらせた。
  • なんか反省点が多い問題だった。

Codeforces Round #514 - E 「Split the Tree」 [2400]

codeforces.com

概要

頂点 1が根であるような n頂点根付き木が与えられる。各頂点には重みが割り振られていて、頂点 iの重みは w_iである。

この木を、以下の条件を満たすいくつかのパスによって分割する。

  • 1つの頂点はちょうど1つのパスに含まれる。
  • 各パスについて、頂点の重みの総和は S以下である。
  • 各パスに含まれる頂点数は L以下である。
  • パス上の頂点を v_1, v_2, \cdots, v_kとしたとき、 v_i v_{i-1}の親である。

このような分割が可能か判定し、可能ならばパスの数の最小値を求めよ。

制約

  •  1 \leq n \leq 10^5
  •  1 \leq L \leq 10^5
  •  1 \leq S \leq 10^{18}
  •  1 \leq w_i \leq 10^9

考察

まず「分割が不可能である」ことは「 \exists i \hspace{1ex} w_i \gt S」と同値になる。 これは全てのパスが1頂点になるような分割を考えれば分かる。


次に割り振り方だが、これは葉から貪欲に決めていくのが良さそうだなと直感的に思う。

各子について、子を根とする部分木をパスに分割したとする。こうして得られた分割において、その子を含むパスを「子のパス」と呼ぶことにする。このとき、

  • その頂点をいずれか1つの「子のパス」に含める。
  • 全ての子とその頂点を切り離す。

のうち最善のものを選んでいけばよい。

まず全ての「子のパス」が親を含む余裕がなければ、子は全て切り離さざるを得ない。一方で、もし余裕のある「子のパス」が存在すれば、その頂点はいずれかの「子のパス」へ含めるのが最適となる。

で、問題となるのは「どの子を選ぶか」。重みと頂点数という2つの指標があるため、これらの情報だけでは簡単には評価ができない。

解法

指標が2つあるのが悪いので、これらを1つにまとめてしまえばいい。

そこで各「子のパス」について、「あといくつの頂点を含めるか?」という値を考える。これが最も大きいものを貪欲に選べばいい。

「子のパス」の始点は決まっているので、始点から親へとパスを辿っていくシミュレーションによって、「パスに含むことができる頂点数」が計算できる。 これは愚直にやると計算量 O(n^2)だが、ダブリングをすることで O(n \log n)で行うことができる。


参考: betrue12.hateblo.jp

実装例

ダブリングはあまり実装したことがないので慣れていない。特に根をどう扱うかでとても悩んだ。

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

const ll INF = 1LL << 60;

int N, L;
ll S;
vector<int> path[100010];

ll upcost[100010][20];  // iを末端とする、長さ2^kのパスの重み
int upto[100010][20];   // iからの距離が2^kの祖先

int ans = 0;

// vを含む集合が、あといくつの要素を含めるか
int dfs(int v) {
    int up = 0;  // 子の値の最大値
    for (int sv : path[v]) up = max(up, dfs(sv));

    if (up > 0) {
        // 頂点vはこの集合に加える
        ans += path[v].size() - 1;
        return up - 1;

    } else {
        // 頂点vは新たな集合にする
        ans += path[v].size();

        int ret = 0;  // vを末端とする集合の最大可能サイズ
        ll cost = 0;
        while (v >= 0) {
            int k;
            for (k = 19; k >= 0; --k) {
                if (upcost[v][k] + cost <= S) break;
            }
            if (k < 0) break;  // 1つでも増やすとコストオーバー

            ret += (1 << k);
            cost += upcost[v][k];
            v = upto[v][k];
        }

        // サイズはL以下であることに注意
        return min(L, ret) - 1;
    }
}

int main() {
    cin >> N >> L >> S;

    for (int i = 0; i < N; ++i) {
        cin >> upcost[i][0];

        // Sを超える重みの頂点が1つでもあればアウト
        if (upcost[i][0] > S) {
            cout << -1 << endl;
            return 0;
        }
    }

    upto[0][0] = -1;
    for (int i = 1; i < N; ++i) {
        cin >> upto[i][0];
        path[--upto[i][0]].push_back(i);
    }

    // ダブリング
    for (int k = 1; k < 20; ++k) {
        for (int i = 0; i < N; ++i) {
            if (upto[i][k - 1] >= 0) {
                upto[i][k] = upto[upto[i][k - 1]][k - 1];
                upcost[i][k] = upcost[i][k - 1] + upcost[upto[i][k - 1]][k - 1];
            } else {
                // 0を超えて過剰に遡れないようにする
                upto[i][k] = -1;
                upcost[i][k] = INF;
            }
        }
    }

    dfs(0);
    // 頂点1の集合を加える
    cout << ans + 1 << endl;
    return 0;
}

感想

  • 2つの評価値を1つにまとめるという発想がなかった。
  • ダブリングの実装にも慣れていきたい。
  • ちなみにTutorialのDP解法はまるで理解できなかった。

AGC003-D 「Anticube」 (1100)

一応自力AC。一応。

atcoder.jp

概要

 N個の整数 \{s_i\}が与えられる。ここから以下の条件を満たすようにいくつかの数を選ぶ。

  • 任意の異なる2要素について、その積は立方数でない。

選べる個数の最大値を求めよ。

制約

  •  1 \leq N \leq 10^5
  •  1 \leq s_i \leq 10^{10}

考察

言い換えをすると、「掛け合わせると立方数になる整数間に辺が張られたグラフについて、最大独立集合のサイズを求めよ」となる。 しかし辺は密になる可能性があるのと、最大独立集合は計算量が指数オーダーなので普通にやると間に合わない。

グラフを書きながら色々考えるうちに、以下の事実に気づく。

  •  A B A' B A B'の積が立方数のとき、
    •  A' B'の積も立方数となる。
    • 素因数分解における指数を3で割った余りに変えたとき、 A A' B B'は一致する。

素因数分解における指数を3で割った余りに変える」というのは、例えば 2160 = 2^4 \cdot 3^3 \cdot 5^1 2^1 \cdot 3^0 \cdot 5^1 = 10に変換するということである。以降、この変換が施された後の値を「標準形」と呼ぶことにする。

また、ある標準形の値について、掛け合わせると立方数となる標準形の値を「補数」と呼ぶことにする。補数は素因数分解の指数の 1 2を交換することで得られる。

 \{s_i\}を全て標準形に変換したときに同じ値のものを1つの頂点とする。するとこの頂点から張られる辺は、補数からなる頂点のみとなる。補数からなる頂点も同様なので、2つのうちどちらか1つは選ぶことができる。

よって標準形が同じものを一まとまりにし、補数の集合と要素数が多い方を貪欲に選べばそれが最適解となる。

ただし標準形が 1の集合だけは例外で、ここからは1つだけ選ぶことができる。

高速化

しかし、これを愚直に実装すると間に合わない。というのも、標準形に変換するには素因数分解をする必要があり、素因数分解の計算量が O(\sqrt{s_i})であることから、全体の計算量は O(N \sqrt{s_i})になってしまうからだ。そこで何らかの高速化をする必要がある。

まず標準化だが、これは以下のような高速化をした。

  • 素数の立方であり、 10^{10}以下であるものを前計算で列挙する。
  • この全要素について割れるだけ割る。

立方数は 325個なので、これで間に合う。

あとは補数を高速に求める必要があるのだが、この方法が思いつかなかった。とりあえず 10^5以下の素数を前計算で列挙したものをダメ元で出してみたら、なんと通ってしまった。

実装例

以下のコードは2582msで動く(制約は5000ms)。想定解ではないけど、本番もこれくらいの実行時間の人がそこそこいたのでセーフってことで。

#include <iostream>
#include <map>
#include <vector>

using namespace std;
using ll = long long;

template <typename T, typename U>
T mypow(T b, U n) {
    if (n == 0) return 1;
    if (n == 1) return b;
    if (n % 2 == 0) {
        return mypow(b * b, n / 2);
    } else {
        return mypow(b, n - 1) * b;
    }
}

vector<ll> primes, cubes;

// 10^5以下の素数と、10^10以下の立方数を列挙する
void precalc() {
    bool isp[100010];
    fill(isp, isp + 100010, true);

    for (ll i = 2; i * i < 1e10; ++i) {
        if (!isp[i]) continue;
        primes.push_back(i);
        for (ll j = 2; i * j <= 100000; ++j) isp[i * j] = false;
    }

    for (ll p : primes) {
        if (p * p * p > 1e10) break;
        cubes.push_back(p * p * p);
    }
}

// 標準形に変換
ll delcube(ll n) {
    for (ll c : cubes) {
        while (n % c == 0) n /= c;
    }
    return n;
}

// 標準形の補数を求める
ll anticube(ll n) {
    ll ret = 1;

    for (ll p : primes) {
        if (p * p > n) break;
        if (n % p > 0) continue;

        int c = 0;
        while (n % p == 0) {
            n /= p;
            ++c;
        }
        ret *= mypow(p, 3 - c);
    }

    // 最後に残ったnは素数か1
    // 素数なら指数は1
    ret *= mypow(n, 2);
    return ret;
}

int main() {
    precalc();

    int N;
    cin >> N;

    // 標準形をキーに、その個数を保持する
    map<ll, int> cnt;
    for (int i = 0; i < N; ++i) {
        ll s;
        cin >> s;
        s = delcube(s);
        if (cnt.count(s) == 0) cnt[s] = 0;
        ++cnt[s];
    }

    int ans = 0;
    for (auto p : cnt) {
        if (p.second == 0) continue;
        if (p.first == 1) {  // 立方数の集合は例外
            ++ans;
            continue;
        }

        ll opp = anticube(p.first);

        // 補数集合と、大きい方を選ぶ
        if (cnt.count(opp)) {
            ans += max(cnt[p.first], cnt[opp]);
            cnt[p.first] = cnt[opp] = 0;
        } else {
            ans += cnt[p.first];
        }
    }

    cout << ans << endl;
    return 0;
}

感想

  • ガチで高速化したら1100点なんだろうなぁ。
    • 上の解法は900点くらいな気がする。
  • 考察パートだけで部分点がほしいね。
  • もっと考察が早くなりたい。
    • 累計4時間くらいの考察でようやく解法に至った。

ARC090-F 「Number of Digits」 (900)

死ぬほどバグらせた。

atcoder.jp

概要

正整数 xに対し、 f(x) = xを10進数表記したときの桁数」と定義する。

整数 Sが与えられる。正整数の組 (l, r)で、 f(l) + f(l + 1) + \cdots + f(r) = Sを満たすものの数を 10^9 + 7で割った値を求めよ。

制約

  •  1 \leq S \leq 10^8

考察

※今回は考察が随分と遠回りだったので、解法だけ読みたい方は飛ばしてください。


最初に述べておくが、 10^n n + 1である。これを念頭に以下を読んでいただきたい。

以降、 d桁の数の個数を num(d)とする。これは num(d) = 9 \times 10^{d - 1}で求まる。

まず f(l) f(r)の桁数の差で場合分けすることにする。

 f(r) - f(l) = 0の場合

 f(l) = f(r) = dとする。このとき、 d桁の数は S / d個必要となる(ここから、 d Sの約数でなくてはならない)。この (l, r)の取り方は num(d) - d + 1個となる。

 f(r) - f(l) = 1の場合

 f(l) = dとすると、 d桁、 d + 1桁の数はそれぞれ dx + (d + 1)y = Sを満たす x, y個必要になる。よって拡張ユークリッドの互除法を使って気合で (x, y)の個数を求めればいける(いける)。

 f(r) - f(l) \geq 2の場合

そもそもこれを満たすのは l \lt 10^7のケースのみである。というのも num(8) \times 8 = 7.2 \times 10^8 Sの制約を上回るからだ。 よって f(r) \leq 9にて桁数のパターンを全部試し、上と同じように拡張ユークリッドの互除法で解の個数を...。

というところで力尽きた。理論上は可能なのだろうが、AtCoderはこういう重実装を出さない(と信じたい)。


ここで諦めてEditorialを見たが、それも f(r) - f(l) = 1のケースがよく分からなかった。そこでkmjpさんの記事を見つけた。こちらは「区間で全探索する」という方針で f(r) - f(l) \leq 1を統一的に扱っていて、とても分かりやすかった。

kmjp.hatenablog.jp

解法

上と同様に d桁の数の個数を num(d)とする( num(d) = 9 \times 10^{d - 1})。

 l \lt 10^8の場合

 (l, r)を全探索する。 (l, r)はともに単調増加なので、尺取り法の要領で十分高速にシミュレートできる。

 l \lt 10^7でも f(r) - f(l) \geq 2のケースは網羅できるのだが、そうしない理由は後で分かる。

 l \geq 10^8の場合

以降 f(r) - f(l) \leq 1となる。

 t = r - l + 1として、 tを全探索することにする。このとき f(l) = \lfloor S / t \rfloorとなる1が、 l \geq 10^8 \Rightarrow f(l) \geq 9 (ここ注意) より f(l) \lt 9になったら終了する。

ここで以下の2つのケースに分けられる。

 S \bmod t = 0のとき

このとき \lfloor S / t \rfloor桁の数が t個必要となる。これは上で述べた f(r) - f(l) = 0のケースなので、上の式を適用すればいい。

 S \bmod t \gt 0のとき

このとき \lfloor S / t \rfloor \lfloor S / t \rfloor + 1の間に区間が跨るようになるので、高々1通りになる。

問題は「 \lfloor S / t \rfloor桁の数と \lfloor S / t \rfloor + 1桁の数は十分あるのか?」だが、 l \geq 10^8 num(9) = 8.1 \times 10^8 \gt Sから常に足りることが分かる。これが先程 l \lt 10^7にしなかった理由である。

実装例

前半の全探索部分はいくらC++といえども結構ギリギリなので、無駄を極力削る必要がある。

以下のコードは214msで通る。

#include <iostream>

using namespace std;
using ll = long long;

const ll MOD = 1000000007;

template <typename T, typename U>
T mypow(T b, U n) {
    if (n == 0) return 1;
    if (n == 1) return b % MOD;
    if (n % 2 == 0) {
        return mypow(b * b % MOD, n / 2);
    } else {
        return mypow(b, n - 1) * b % MOD;
    }
}

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

    ll ans = 0;
    int r = 0, sum = 0;
    int ldig = 0, rdig = 0, lten = 1, rten = 1;

    // l<10^8 尺取り法で全探索
    for (int l = 1; l < 100000000; ++l) {
        if (l == lten) ++ldig, lten *= 10;

        while (sum < S) {
            ++r;
            if (r == rten) ++rdig, rten *= 10;
            sum += rdig;
        }

        if (sum == S) ++ans;
        sum -= ldig;
    }

    // l>=10^8 区間長で総当たり
    for (int t = 1; t * 9 <= S; ++t) {
        int d = S / t;
        if (S % t == 0) {  // f(l)=f(r)=dの場合
            ans += mypow(10LL, d - 1) * 9 - t + 1 + MOD;
        } else {  // f(l)=f(r)-1=dの場合
            ++ans;
        }
    }

    cout << ans % MOD << endl;
    return 0;
}

ちなみにFastest Code辺りは考察で述べた拡張ユークリッド互除法の解法を実装しているらしい。正気か?

反省

  • 脳を使うことはC++に任せよう。
  • 区間長で全探索するのは中々出ない。
    •  f(l)の桁数に囚われすぎてしまった。
  • 学びが大きい問題ではあった。

  1.  \lfloor S / t \rfloor \times t \leq S \lt ( \lfloor S / t \rfloor + 1) \times tより従う。

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全体のレベルが高すぎる。

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をすばやく実装できたのはとても偉いと思う。

3日目 CFR537 (Div2)

codeforces.com

本番ならB落としてた。CまでとD以降の差が酷くない?

f:id:misteer:20190205002207p:plain


B. Average Superhero Gang Power

Problem - B - Codeforces

概要

長さ Nの数列 \{a_i\}が与えられる。あなたはこの数列に、以下のいずれかの操作を高々 M回行うことができる。

  • 長さが2以上であれば、好きな要素を1つ消す。
  • 好きな要素を1増やす。ただし、1つの要素は高々 K回しか増やせない。

こうして得られた数列の平均値として、考えうる最大値を求めよ。

制約

  •  1 \leq N \leq 10^5
  •  1 \leq K \leq 10^5
  •  1 \leq M \leq 10^7
  •  1 \leq a_i \leq 10^6

解説

「1つになるまで消せるだけ消して、できるだけインクリメント」という貪欲でいけそうに見えるが、これは a_iが全て同じケースに撃墜される1

答えを求めるには、「いくつ減らすか」を全探索する必要がある。減らすのはもちろん小さい方からで、 i個消したときインクリメントは min(M - i, K(N - i))回行える。よって累積和とこの値から総和、及び平均値を求めればいい。


ここまで分かっていたのだが、結局注意力不足で3WAを吐いてしまった。その内容が以下の2つ。

  • 要素を M個以上減らした。
  •  K(N - i)がintに収まらないのに気づかなかった。

故意かは知らないが、罠が多すぎる...。

実装例

本番でバグを一切埋め込まずに実装できた人は本当に凄いと思う。

#include <iomanip>
#include <iostream>
#include <algorithm>

using namespace std;
using ll = long long;

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

    double a[n];
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a, a + n, greater<double>());
    for (int i = 1; i < n; ++i) a[i] += a[i - 1];  // 累積和に変換

    double ans = 0;
    for (int i = 0; i <= min(n - 1, m); ++i) {
        // i人を減らす
        double sum = a[n - i - 1];
        sum += min(m - i, k * (n - i));
        ans = max(ans, sum / (n - i));
    }

    cout << fixed << setprecision(10) << ans << endl;
    return 0;
}


C. Creative Snap

Problem - C - Codeforces

概要

※本文をそのまま和訳すると長くなるので、全く別の設定にしています。

同一直線上に並んだ 2^N個の穴があり、いくつかの穴にはゴミが入っている。 i個目のゴミは左から a_i番目の穴に入っている。

あなたは以下のように全ての穴を埋めていくことにした。

  • 最初は全体区間から始める。
  • 今見ている区間に対して、以下のいずれかを適用する。
    1. 長さが等しい2つの区間に分割し、再帰的に埋める。
    2. その区間を埋める。
      • 区間内にゴミが1つもない場合、コスト Aがかかる。
      • ゴミが n個( n \gt 0)あったとき、コスト B \times n \times lがかかる。ここで l区間長。

このとき、全ての穴を埋めるのにかかる最小コストを求めよ。

制約

  •  1 \leq N \leq 30
  •  1 \leq K \leq 10^5
  •  1 \leq A, B \leq 10^4

解説

以降、区間 (l, r]のように半開区間で考えることにする。これは ( l, \frac{l + r}{2}]と (\frac{l + r}{2}, r]のように区間を分割しやすいことと、後述するようにコストを求めやすいことによる。


まず解法だが、問題文にあるまま再帰的に求めれば良い。つまり「分割する場合」と「埋める場合」の両方を試し、安い方を採用するということだ。計算量解析がしにくいのでTLEが不安になるが、ちゃんと空区間をスキップすれば、再帰関数の呼び出し回数は O(NK)に抑えられるはずだ。

問題となるのは、「埋める場合」のコストの算出だろう。「区間 (l, r]に含まれる a_iの数」、言い換えれば「 \{a_i\} r以下の要素数」から「 \{a_i\} l以下の要素数」を引いたものを高速に求める必要がある。

 \{a_i\} r以下の要素数」は二分探索で高速に求められるが、自分で実装しなくてもstd::upper_boundを使うことで

upper_bound(a.begin(), a.end(), r) - a.begin()

のように求められる2。便利。


今回区間を半開区間として扱ったが、基本的に閉区間や開区間より半開区間の方が扱いやすい。というのも、半開区間

  • 区間の分割・マージが楽。
  • 区間和」を求めるのが楽(「 rまでの累積和」から「 lまでの累積和」を引くだけ)。

といった性質を持つからだ。「バグの原因となりやすい \pm 1の調整が出ない」ことも大きい。

実装例

区間の扱いに \pm 1の微調整が一切入っていないのが分かる。これは半開区間だからこそ為せる技である。

#include <iostream>
#include <algorithm>

using namespace std;
using ll = long long;

int n, k, a, b;
int p[100010];

ll rec(ll l, ll r) {
    // 区間内のa_iの数
    ll num = upper_bound(p, p + k, r) - upper_bound(p, p + k, l);

    if (num == 0) return a;          // 空区間をスキップ
    if (r - l == 1) return b * num;  // 長さが1のときは、終了しないと無限ループになる

    // 2つの区間に分割
    int m = (l + r) / 2;
    return min(b * num * (r - l), rec(l, m) + rec(m, r));
}

int main() {
    cin >> n >> k >> a >> b;
    for (int i = 0; i < k; ++i) cin >> p[i];
    sort(p, p + k);

    cout << rec(0, 1 << n) << endl;
    return 0;
}


感想

  • std::upper_boundの使い方をまた1つ学んだ。
  • Bをバグなしで通せるようになりたい。
  • D, Eは何。

  1. 本番ではこれがpretestを通ってしまい、こどふぉ春のHack祭りだったらしい(立春だけに)。

  2. ただしaはソート済みとする。