2020-10-29

AtCoder ARC 058 E - 和風いろはちゃん (橙色, 700 点)

5 + 7 + 5 = 17 なの、よくできてる！

問題へのリンク

問題概要

正の整数 $X, Y, Z$ が与えられる。

$1$ 以上 $10$ 以下の数値からなる長さ $N$ の数列 $a_{1}, \dots, a_{N}$ であって、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。

整数 $0 \le x \lt y \lt z \lt w \le N$ が存在して、
$a$ の区間 $\lbrack x, y)$ の総和が $X$
$a$ の区間 $\lbrack y, z)$ の総和が $Y$
$a$ の区間 $\lbrack z, w)$ の総和が $Z$

制約

$3 \le N \le 40$
$1 \le X \le 5$
$1 \le Y \le 7$
$1 \le Z \le 5$

考えたこと

第一感だと、

数列のうち、総和が $X, Y, Z$ となる区間の位置を決め打ちして
区間内の総和が $X, Y, Z$ となるような個数を数える

という風にしたくなる。しかしそのような方針では、ダブルカウントの脅威を取り除くことがとても厳しそう。同じ数列でも、総和が $X, Y, Z$ となるような区間の取り方が幾通りもあるケースがあるのだ。そのようなものをすべて考慮するとなると気が遠くなる。

DP で状態を全部もつ

代わりに、DP しよう。そしてざっくりとした方針としては、「数列の今の状態において最後尾付近は結局どのような区間を形成しうるか」という情報をすべて押し込めてしまうのが良さそう。そこで、 $S$ を $0$ 以上 $2^{X + Y + Z}$ 未満の整数として、

dp[ i ][ S ][ 0 or 1 ] := 数列のうち最初の i 項までを決めたとき、最後尾から連続する数値の総和として $1, 2, \dots, X+Y+Z$ のうちのどの値をとりうるかの情報を表すビット状態が $S$ であるようなもののうち、(0: まだ XYZ が形成されていない、1: すでに XYZ が形成済み) となるようなものの個数

という風にする。こうすると、ダブルカウントしそうな部位も全部まるごと DP 添字として管理できる。計算量は $O(AN2^{X+Y+Z})$ ( $A$ は数列の各項の値の種類数) となる。

コード

#include <bits/stdc++.h>
using namespace std;

// modint
template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() const { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr istream& operator >> (istream& is, Fp<MOD>& x) noexcept {
        is >> x.val;
        x.val %= MOD;
        if (x.val < 0) x.val += MOD;
        return is;
    }
    friend constexpr ostream& operator << (ostream& os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD>& r, long long n) noexcept {
        if (n == 0) return 1;
        if (n < 0) return modpow(modinv(r), -n);
        auto t = modpow(r, n / 2);
        t = t * t;
        if (n & 1) t = t * r;
        return t;
    }
    friend constexpr Fp<MOD> modinv(const Fp<MOD>& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        return Fp<MOD>(u);
    }
};

const int MOD = 1000000007;
using mint = Fp<MOD>;

int main() {
    int N, X, Y, Z;
    cin >> N >> X >> Y >> Z;
    int S = X+Y+Z;
    
    auto nex = [&](long long bit, int v) {
        long long nbit = (bit<<v) % (1<<S);
        if (v-1 < S) nbit |= 1<<(v-1);
        return nbit;
    };
    auto clear = [&](int bit) {
        if (!(bit & (1<<(Z-1)))) return false;
        if (!(bit & (1<<(Y+Z-1)))) return false;
        if (!(bit & (1<<(X+Y+Z-1)))) return false;
        return true;
    };

    vector<vector<mint>> dp(1<<S, vector<mint>(2, 0)), ndp = dp;
    dp[0][0] = 1;
    for (int i = 0; i < N; ++i) {
        ndp.assign(1<<S, vector<mint>(2, 0));
        for (int bit = 0; bit < (1<<S); ++bit) {
            for (int v = 1; v <= 10; ++v) {
                int nbit = nex(bit, v);
                if (clear(nbit)) ndp[nbit][1] += dp[bit][0];
                else ndp[nbit][0] += dp[bit][0];
                ndp[nbit][1] += dp[bit][1];
            }
        }
        swap(dp, ndp);
    }
    mint res = 0;
    for (int bit = 0; bit < (1<<S); ++bit) res += dp[bit][1];
    cout << res << endl;
}

2020-10-28

AtCoder ABC 042 C - こだわり者いろはちゃん (ARC 058 C) (緑色, 300 点)

AtCoder AtCoder300点 ARC-C ABC-C 各桁ごとに見る見積り大事全探索禁止文字列緑色diff

記念すべき新体制 AtCoder になってからの初の rated ABC の C 問題！！！

問題のリンク

問題概要

$N$ 以上の整数のうち、 $K$ 種類の数値 $D_{1}, \dots, D_{K}$ のいずれも含まない最小のものを求めよ。

制約

$1 \le N \lt 10000$
$1 \le K \lt 10$
$0 \le D_{1} \lt \dots \lt D_{K} \le 9$

考えたこと

真っ先に思い浮かぶ方法は、単純に $N, N+1, \dots$ と順々に試していって「 $D$ をいずれも含まないもの」が初めて登場した時点でそれを出力する方法がと思う。

そして今回はそれでいいのだ！！！なぜそれでいいのかを念のためにきちんと確認しておこう。まず、 $N$ は最大でも 5 桁の整数であることに注目する。ということは、 $D$ に含まれない数値を $a$ としたとき、

$a$ を並べた 6 桁の整数 ( $= A$ とする)

は条件を満たしていることがわかる！！よって、どんなに時間がかかっても、 $A-N+1$ 通り程度試せばよいことがわかる。十分間に合う！！！

整数 n が条件を満たすかどうかの判定

残る問題は、整数 $n$ が $D_{1}, \dots, D_{K}$ のいずれも含まないかどうかを判定する部分だ。

これは、次のようにできる。

bool isValid(int n) {
    while (n) {
         if (n % 10 が D に含まれる) return false;
         n /= 10;
    }
    return true;
}

つまり、各桁の値を求めて、それらが $D$ に含まれるかどうかを判定していけば OK。

別解

なお他の方法として、整数 $n$ を文字列に変換して、各文字を調べる方法もある。

コード

#include <bits/stdc++.h>
using namespace std;

set<int> D;
bool isValid(int n) {
    while (n) {
        if (D.count(n % 10)) return false;
        n /= 10;
    }
    return true;
}

int main() {
    int N, K; 
    cin >> N >> K;
    for (int i = 0; i < K; ++i) {
        int d; cin >> d; D.insert(d);
    }
    for (int n = N;; ++n) if (isValid(n)) {
        cout << n << endl;
        return 0;
    }
}

2020-10-28

CPSCO2019 Session3 C - Make a Team (300 点設定)

AtCoder 探索順序を工夫して解くある量を固定して考えるしゃくとり法 nC2 数え上げ問題二分探索:lower_bound グルーピング(算数) グルーピングの数え上げ問題

これかなりいい問題だと思う！！！
テスターをしていて、最初は 3 人じゃなくて $K$ 人だったけど、3 人にしたことでいい感じに 300 点問題になった！

問題へのリンク

問題概要

$N$ 人がいて、それぞれレーティングは $a_{1}, \dots, a_{N}$ となっている。

$N$ 人の中から 3 人を選ぶ方法のうち、3 人のレーティングの最大値と最小値との差が $D$ 以下であるようなものが何通りあるか、求めよ。

制約

$3 \le N \le 10^{5}$

解法

この手の問題は最初に $N$ 人をレーティングの小さい順にソートしてしまうと考えやすくなる。

そして「3 人のうちレーティングが最小の人」を誰にするのかを固定して考えることにする。 $i$ 人目をレーティング最小の人としたとき、

$a_{j} \le a_{i} + D$ を満たす最大の $j$ をとる
このとき $i+1, i+2, \dots, j$ の中からどのように 2 人選んでもよい
その選び方は ${}_{j-i}{\rm C}_{2} = \frac{1}{2}(j-i)(j-i-1)$ 通りある

という風になる。あとは各 $i$ に対して、 $a_{j} \le a_{i} + D$ を満たす最大の $j$ が求められれば OK。これはしゃくとり法 (か lower_bound) を使えば OK。

全体として $O(N \log N)$ の計算量で解ける。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, D;
    cin >> N >> D;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    sort(a.begin(), a.end());

    long long res = 0;
    int j = 0;
    for (int i = 0; i < N; ++i) {
        while (j < N && a[j] <= a[i] + D) ++j;
        --j;
        res += (long long)(j-i) * (j-i-1) / 2;
    }
    cout << res << endl;
}

2020-10-28

CPSCO2019 Session4 D - Boring Sequence (400 点設定)

AtCoder 最大値の最小化二分探索操作操作をK回まで行える全部混ぜて解く priority_queue Greedy 数列テク:区間ごとに分割するランレングス圧縮区間の長さの最大値または最小値を求める最大スコア最適化問題

一目二分探索ゲーだし、実際二分探索で解けるのだけど、実はもっとすごく楽に解ける！！

問題へのリンク

問題概要

長さ $N$ の整数列 $a_{1}, \dots, a_{N}$ が与えられる。数列の退屈さとは「同じ値が連続している区間の長さの最大値」として定義する。

与えられた数列において、最大で $K$ 箇所まで値を書き換えることができる。書き換えた数列の退屈さとして考えられる最小値を求めよ。

制約

$1 \le K \lt N \le 2 \times 10^{5}$

考えたこと

「最大値の最小化」なので、ごく自然に二分探索で解けるのだけど、とても鮮やかな別解があるのでそれで解いてみる。ちょうど Session3 の G 問題と同じように解く！！

drken1215.hatenablog.com

まず、数列をランレングス圧縮したときの、各区間の長さの列を $l_{1}, \dots, l_{p}$ とする。このとき

$i$ 番目の要素に対して $k$ 回の操作を行うと、スコアは $L / (k + 1)$ になる

という風に考えることができる。各要素に対する操作の合計値が $K$ となるように操作を行ったときの、「各要素のスコアの最大値」を最小にする問題だと言える。これは次のような Greedy で求められる。

その時点でスコアが最大となっている要素に対して操作を行っていく

これはもっと簡単に、各要素に対する

元の長さ, 1 回の操作を行ったときの長さ, 2 回の操作を行ったときの長さ, ...

を全部混ぜたベクトル v を考えて、それをまとめてソートしてしまえばよい。その $K$ 番目の値が答えとなる。なお、元の長さが $L$ であるような系列においては、 $L$ 回以上の操作を行う必要がないことから、v に挿入する値は、最大でも $L$ 個となる。 $L$ の合計値は $N$ なので、v のサイズは $O(N)$ となる。

よって $O(N \log N)$ で解くことができた。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    vector<int> v;
    for (int i = 0; i < N;) {
        int j = i;
        while (j < N && a[j] == a[i]) ++j;
        int len = j - i;
        for (int k = 0; k <= len; ++k) v.push_back(len / (k+1));
        i = j;
    }
    sort(v.begin(), v.end(), greater<int>());
    cout << max(v[min(K, (int)v.size()-1)], 1) << endl;
}

2020-10-28

CPSCO2019 Session4 E - ox Concatenation (600 点設定)

AtCoder グルーピング(算数) 文字列のconcatを考える問題文字列 0と1の問題コーナーケース Yes/No判定問題テク:区間ごとに分割するランレングス圧縮連結性に着目する必要条件を列挙したら十分条件になる算数と数学 Greedy:条件を満たすまで大きい順に取っていく Greedy

これすごく好き！！！普通に難しい。

問題へのリンク

問題概要

'o' と 'x' のみからなる長さ $N$ の文字列 $S$ を作りたい。部品として使えるのは以下のものたち ( $2A + 2B + C + D = N$ となっている)。

"ox" が $A$ 個
"xo" が $B$ 個
"o" が $C$ 個
"x" が $D$ 個

これらを適切な順序で concat することで、文字列 $S$ にすることが可能かどうかを判定せよ。

制約

$1 \le N \le 2 \times 10^{5}$

考えたこと

とりあえず、 $S$ に含まれる 'o' が $A+B+C$ 個、'x' が $A+ B+D$ 個になる必要がある。

それを満たしているとき、部品 "o" と "x" の配置はあとからいくらでも調整が効くので、なるべく "ox" と "xo" を積極的に消費していきたい。逆に $A$ 個の "ox" と $B$ 個の "xo" をすべて、 $S$ 上で、互いに重なり合わないように配置できたならば、残りは "o" と "x" で埋めることができる。

さて、 $S$ において、「"o" が連続している箇所」や「"x" が連続している箇所」に仕切りを入れて分割して考えることにしよう。(仕切りを入れる場所には "ox" や "xo" は配置できない)。そうすると各区間は

"oxox...ox"
"xoxo...xo"
"oxox...o"
"xoxo...x"

のいずれかのパターンとなる。それぞれについて、長さを $2n$ (パターン 1, 2) または $2n-1$ (パターン 3, 4) とする。このとき、"ox" と "xo" の消費可能数を $(a, b)$ で表すことにすると、

$(n, 0)$ と $(a, b)$ ( $a + b = n-1$ ) が可能
$(0, n)$ と $(a, b)$ ( $a + b = n-1$ ) が可能
$(a, b)$ ( $a + b = n-1$ ) が可能
$(a, b)$ ( $a + b = n-1$ ) が可能

というふうになる。基本的には、どのパターンからも合計 $n-1$ 個ずつ作れることがわかる (そして合計が $n-1$ になるような 2 数のパターンは任意)。よって、各区間ごとの「(長さ - 1) / 2」の合計値を $L$ としたとき、 $A+B \le L$ であれば可能と言える。

$A+B \gt L$ となる場合が問題となる。このときは、パターン 1 で $(n, 0)$ を選んだり、パターン 2 で $(0, n)$ を選んだりすることによって、"ox" と "xo" の消費量の合計値を上手に上げていく必要がある。ただし、

パターン 1 で $(n, 0)$ を選ぶならば、それを選んだ $n$ の合計値が $A$ を超えてはならない
パターン 2 で $(0, n)$ を選ぶならば、それを選んだ $n$ の合計値が $B$ を超えてはならない

ということに留意する必要がある。以上から、次のように判定できることがわかる。

まず、すべてのパターンの「(長さ - 1) / 2」の合計値を $L$ とする。

パターン 1 な区間をすべて抽出して、それらの長さを $2l_{1}, 2l_{2}, \dots$ とする。それらから合計値 / 2 が $A$ 以下となるように選べる個数の最大値を $p$ とする

パターン 2 な区間をすべて抽出して、それらの長さを $2r_{1}, 2r_{2}, \dots$ とする。それらから合計値 / 2 が $B$ 以下となるように選べる個数の最大値を $q$ とする

このとき、 $L + p + q \ge A + B$ ならば可能で、そうでなければ不可能である。

計算量は $O(N \log N)$ となる。

コード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

long long N, A, B, C, D;
string S;

bool solve() {
    int maru = 0;
    for (int i = 0; i < N; ++i) if (S[i] == 'o') ++maru;
    if (maru != A + B + C) return false;
    if (N - maru != A + B + D) return false;

    vector<long long> ox, xo, other;
    for (int i = 0; i < N;) {
        int j = i+1;
        while (j < N && S[j-1] != S[j]) ++j;
        if ((j-i) % 2 == 0) {
            if (S[i] == 'o') ox.push_back((j-i)/2);
            else xo.push_back((j-i)/2);
        }
        else other.push_back((j-i)/2);
        i = j;
    }
    sort(ox.begin(), ox.end());
    sort(xo.begin(), xo.end());
    int num = 0;
    long long oxsum = 0, xosum = 0, otsum = 0;
    for (int i = 0; i < ox.size(); ++i) {
        if (oxsum + ox[i] <= A) ++num;
        oxsum += ox[i];
    }
    for (int i = 0; i < xo.size(); ++i) {
        if (xosum + xo[i] <= B) ++num;
        xosum += xo[i];
    }
    for (int i = 0; i < other.size(); ++i) otsum += other[i];
    if ((oxsum - (int)ox.size()) + (xosum - (int)xo.size()) + otsum + num >= A + B)
        return true;
    return false;
}

int main() {
    while (cin >> N >> S >> A >> B >> C >> D) {
        if (solve()) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ARC 058 E - 和風いろはちゃん (橙色, 700 点)

問題概要

制約

考えたこと

DP で状態を全部もつ

コード

AtCoder ABC 042 C - こだわり者いろはちゃん (ARC 058 C) (緑色, 300 点)

問題概要

制約

考えたこと

整数 n が条件を満たすかどうかの判定

別解

コード

CPSCO2019 Session3 C - Make a Team (300 点設定)

問題概要

制約

解法

CPSCO2019 Session4 D - Boring Sequence (400 点設定)

問題概要

制約

考えたこと

コード

CPSCO2019 Session4 E - ox Concatenation (600 点設定)

問題概要

制約

考えたこと

コード