2020-04-24

AtCoder ABC 044 C - 高橋君とカード (ARC 060 C) (水色, 300 点)

AtCoder AtCoder300点 ABC-C 平均値に関する問題平均値制約を総和制約に変換する DP 部分和シーケンシャルDP 水色diff ARC-C

「平均値が A」という制約は上手に扱うテクニックがある。
今回はそれを思いつかなくても解けるけど、思いつくと計算量が落ちる。

問題へのリンク

問題概要

$N$ 個の整数 $x_{1}, \dots, x_{N}$ からいくつか選ぶ方法のうち、その平均値がちょうど $A$ となるものが何通りあるかを求めよ。

制約

$1 \le N, A \le 50$

解法 (1)：平均値をまともに取り扱う

「平均値が A」というのは

個数が k 個のとき、総和が Ak

という風にとらえることができる。よって

dp[ i ][ s ][ k ] := N 個の整数のうちの最初の i 個から、k 個選ぶ場合について、総和を s にするものが何個あるか

という DP で解くことができる。遷移は

x[ i ] を選ばない場合： dp[ i + 1 ][ s ][ k ] += dp[ i ][ s ][ k ]
x[ i ] を選ぶ場合： dp[ i + 1 ][ s + x[ i ] ][ k + 1 ] += dp[ i ][ s ][ k ]

で表すことができる。計算量は $O(N^{3}A)$ 。

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

long long dp[55][3000][55];
int main() {
    int N, A;
    cin >> N >> A;
    vector<int> x(N);
    for (int i = 0; i < N; ++i) cin >> x[i];

    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;
    for (int i = 0; i < N; ++i) {
        for (int s = 0; s <= N*A; ++s) {
            for (int k = 0; k <= N; ++k) {
                if (dp[i][s][k] == 0) continue;
                dp[i+1][s][k] += dp[i][s][k];
                dp[i+1][s+x[i]][k+1] += dp[i][s][k];
            }
        }
    }
    long long res = 0;
    for (int k = 1; k <= N; ++k) res += dp[N][A*k][k];
    cout << res << endl;
}

解法 (2)：平均値制約を上手に

一般に

$a, b, c, \dots$ の平均値が $A$
⇔ $a-A, b-A, c-A, \dots$ の平均値が $0$
⇔ $a-A, b-A, c-A, \dots$ の総和が $0$

という言い換えができる。平均値に関する制約が、総和に関する制約になって、とても扱いやすくなる！！！元の問題は

$N$ 個の整数 $x_{1} - A, \dots, x_{N} - A$ が与えられる。これらからいくつか選んで総和を 0 にする方法が何通りあるかを求めよ。

と言い換えることができる。こうしておくと dp も、

dp[ i ][ s ] := 最初の i 個からいくつか選んで総和が s になる方法の個数

という風に次元を減らすことができる。計算量は $O(N^{2}A)$ に減る。

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

long long dp[55][5000];
const int GETA = 2500;
int main() {
    int N, A;
    cin >> N >> A;
    vector<int> x(N);
    for (int i = 0; i < N; ++i) cin >> x[i], x[i] -= A;

    memset(dp, 0, sizeof(dp));
    dp[0][GETA] = 1;
    for (int i = 0; i < N; ++i) {
        for (int s = 0; s+x[i] < 5000; ++s) {
            if (dp[i][s] == 0) continue;
            dp[i+1][s] += dp[i][s];
            dp[i+1][s+x[i]] += dp[i][s];
        }
    }
    // 「何も選ばない」を除く
    cout << dp[N][GETA] - 1 << endl;
}

2020-04-24

AtCoder ARC 075 E - Meaningful Mean (青色, 600 点)

AtCoder AtCoder600点 ARC-E 平均値に関する問題解空間:O(N^2)通りの選択肢数列区間累積和転倒数 BIT 変数変換して扱いやすい同型な問題を見出す平均値制約を総和制約に変換する f(i,j)をiとjとに分離する青色diff 解空間:O(N^2)個の区間数え上げ問題制約条件:ある値<=K 連続部分列を扱う問題 Zero-Sum Ranges 中堅以上の典型要素を詰め合わせた教育的問題

じょえちゃんえるから。
「平均値が $K$ 以上」という条件を見たときにパッと考えつく話がある。

問題へのリンク

問題概要

$N$ 個の正の整数列 $A_{1}, \dots, A_{N}$ と整数 $K$ が与えられる。

整数列の連続する部分列であって、その平均値が $K$ 以上であるものが何個あるかを求めよ。

制約

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

考えたこと

一般に、

$a, b, c, \dots$ の平均値が $K$ 以上
⇔ $a-K, b-K, c-K, \dots$ の平均値が $0$ 以上
⇔ $a-K, b-K, c-K, \dots$ の総和が $0$ 以上

という言い換えができる。「平均値」に関する条件が、なんと「総和」に関する条件へと早変わりして、滅茶苦茶扱いやすくなるのだ。というわけで、元の問題は次の問題へと言い換えることができる。

$N$ 個の整数 $A_{1} - K, \dots, A_{N} - K$ の連続する部分列であって、その総和が $0$ 以上であるものが何個あるかを求めよ。

累積和へ

次に「連続する部分列の総和」と言われたら、累積和が使える。 $A_{1} - K, \dots, A_{N} - K$ の累積和を $S_{0}, S_{1}, \dots, S_{N}$ とする。そうすると、元の問題はさらに次のように言い換えられる。

$N+1$ 個の整数 $S_{0}, S_{1}, \dots, S_{N}$ に対して、

$S_{j} - S_{i} \ge 0$ (⇔ $S_{i} \le S_{j}$ )

が成立するような $0 \le i \lt j \le N$ の組が何個あるかを求めよ。

これはもう、ほとんど転倒数と一緒だ。

転倒数へ

転倒数は

$S_{i} \ge S_{j}$

を満たすような $0 \le i \lt j \le N$ の組の個数である。今回は不等号は逆だけど、求め方はほとんど一緒。BIT を使うといい感じにできる！

転倒数の求め方は、

転倒数アルゴリズム

などに詳しく書いてある！！計算量は $O(N\log{N})$ 。

コード

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

template <class Abel> struct BIT {
    const Abel UNITY_SUM = 0;                       // to be set
    vector<Abel> dat;
    
    /* [1, n] */
    BIT(int n) : dat(n + 1, UNITY_SUM) { }
    void init(int n) { dat.assign(n + 1, UNITY_SUM); }
    
    /* a is 1-indexed */
    inline void add(int a, Abel x) {
        for (int i = a; i < (int)dat.size(); i += i & -i)
            dat[i] = dat[i] + x;
    }
    
    /* [1, a], a is 1-indexed */
    inline Abel sum(int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i)
            res = res + dat[i];
        return res;
    }
    
    /* [a, b), a and b are 1-indexed */
    inline Abel sum(int a, int b) {
        return sum(b - 1) - sum(a - 1);
    }
    
    /* debug */
    void print() {
        for (int i = 1; i < (int)dat.size(); ++i) cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

int main() {
    int N;
    long long K;
    cin >> N >> K;
    vector<long long> S(N+1, 0);
    for (int i = 0; i < N; ++i) {
        long long a;
        cin >> a;
        S[i+1] = S[i] + (a - K);
    }
    vector<long long> SS = S;
    sort(SS.begin(), SS.end());
    SS.erase(unique(SS.begin(), SS.end()), SS.end());
    long long res = 0;
    BIT<long long> bit(N+10);
    for (int i = 0; i <= N; ++i) {
        int id = lower_bound(SS.begin(), SS.end(), S[i]) - SS.begin();
        res += bit.sum(id+1);
        bit.add(id+1, 1);
    }
    cout << res << endl;
}

2020-04-23

JOI 二次予選 2020 D - テンキー (AOJ 0675, 難易度 7)

AtCoder JOI予選・二次予選 BFS DP 二次元グリッド Dijkstra法最小回数・最小個数を求めるパズル整数を「10倍してaを足す」で捉える AOJ JOI DP状態:あまり JOI難易度7 競プロ典型90問とその類題【問題集】DFS・BFSのステップアップ DP状態:どの桁まで見たか(広義の桁DP) 最適化問題

本選参加のボーダーとなった問題らしい！それにしても JOI は実装が重たい...！！！

問題へのリンク

類題とか

drken1215.hatenablog.com

問題概要

初期状態では下図のようなテンキーの「0」のところにカーソルがある。

上下左右への移動
ボタンを押す (315 に 4 を押すと 3154 になる)

を最小回数繰り返して、 $M$ で割って $R$ あまる状態にせよ。

制約

$1 \le R \lt M \le 10^{5}$

考えたこと

一般に、あることを実現するための最小回数を求めるためには、探索空間が十分に小さければ BFS でできる。今回もそんな感じ。探索空間としては

(i, j, r)：マス (i, j) にカーソルがあって、できている数を M で割ったあまりが r であるような状態

としてあげて、

dist[ i ][ j ][ r ] := 上記状態にするまでの最小回数

として BFS すれば良さそう。計算量は単純に $O(M)$ になる。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using pint = pair<int,int>;
using Node = pair<pint,int>;
const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};

vector<vector<int>> val = {vector<int>({7, 8, 9}),
    vector<int>({4, 5, 6}), vector<int>({1, 2, 3}), vector<int>({0})};

int dp[5][5][210000];
int main() {
    int M, R;
    cin >> M >> R;
    memset(dp, -1, sizeof(dp));
    dp[3][0][0] = 0;
    queue<Node> que;
    que.push(Node(pint(3, 0), 0));
    while (!que.empty()) {
        auto cur = que.front(); que.pop();
        int x = cur.first.first, y = cur.first.second;
        int r = cur.second;
        {
            int nr = (r * 10 + val[x][y]) % M;
            if (dp[x][y][nr] == -1) {
                dp[x][y][nr] = dp[x][y][r] + 1;
                que.push(Node(pint(x, y), nr));
            }
        }
        for (int dir = 0; dir < 4; ++dir) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if (nx < 0 || nx >= 4 || ny < 0 || ny >= val[nx].size()) continue;
            if (dp[nx][ny][r] == -1) {
                dp[nx][ny][r] = dp[x][y][r] + 1;
                que.push(Node(pint(nx, ny), r));
            }
        }
    }
    int res = 1<<29;
    for (int x = 0; x < 4; ++x) {
        for (int y = 0; y < val[x].size(); ++y) {
            chmin(res, dp[x][y][R]);
        }
    }
    cout << res << endl;
}

2020-04-23

AtCoder ABC 135 D - Digits Parade (水色, 400 点)

AtCoder AtCoder400点 ABC-D 整数を「10倍してaを足す」で捉える DP 数え上げ問題ワイルドカード問題 DP状態:あまり水色diff DP状態:どの桁まで見たか(広義の桁DP)

よくある桁DPとはまた違うけれど、あまりを状態にもつ DP を試せる問題ですね！

問題へのリンク

問題概要

"013?42???2??"
のような、'?' と数値で構成された、長さ $N$ の文字列が与えられる。

この '?' を埋めて数値を作る方法のうち、13 で割ったあまりが 5 になるようなものが何通りあるか、1000000007 で割ったあまりを求めよ。

ただし、先頭に 0 があっても、それを整数とみなすこととする。

制約

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

考えたこと

この問題、「先頭に 0 があったらダメ」とかだったら、ちょっと面倒になるけど、それがないので助かる ^^;

さて、整数を扱う一つの方法として「10 倍して〜を足すのを繰り返したものとみなす」というのがある！！！！

この考え方は、

桁DPな問題全般
AtCoder ABC 077 D - Small Multiple

あたりで見られる。たとえば、3141 とかだと、

0 からスタートする
10 倍する (0 になる)
3 を足す (3 になる)
10 倍する (30 になる)
1 を足す (31 になる)
10 倍する (310 になる)
4 を足す (314 になる)
10 倍する (3140 になる)
1 を足す (3141 になる)

という風にして構成できる！！！ざっくり

0 -> 3 -> 31 -> 314 -> 3141

という流れだ。今回みたいに「整数の各桁をどうするか」みたいな問題では、上記の見方が役に立つことが結構ある！

DP へ

以上のことを意識して、こんな感じの DP を組んでみよう。

dp[ i ][ j ] := S の上から i 桁目までを考えたときの、それを 13 で割ったあまりが j になるように、'?' を埋める方法の数

このとき、i から i+1 への遷移は次のように考えることができる！dp[ i ][ j ] に属する整数を 10 倍して x を足すと、それを 13 で割ったあまりは

(10 × j + x) % 13

になることに注意すると、遷移は次のように書ける！！

S[ i ] が 'x' または '?' のとき、

dp[ i + 1 ][ (10 × j + x) % 13 ] += dp[ i ][ j ]

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

const int MOD = 1000000007;
void add(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}
int main() {
    string S;
    cin >> S;
    vector<vector<long long>> dp(S.size()+1, vector<long long>(13, 0));
    dp[0][0] = 1;
    for (int i = 0; i < S.size(); ++i) {
        for (int j = 0; j < 13; ++j) {
            if (S[i] == '?') {
                for (int k = 0; k < 10; ++k) {
                    add(dp[i+1][(j*10+k)%13], dp[i][j]);
                }
            }
            else {
                int k = S[i] - '0';
                add(dp[i+1][(j*10+k)%13], dp[i][j]);
            }
        }
    }
    cout << dp[S.size()][5] << endl;
}

2020-04-23

AtCoder ABC 155 D - Pairs (青色, 400 点)

AtCoder AtCoder400点 ABC-D K番目を求めるパリティ数列ある量を固定して考えるある量を決めるとGreedy しゃくとり法二分探索青色diff 負値が本質的に効く問題

最初は、問題を見た瞬間に「にぶたんだ...」となったので、青 diff に驚いたのだった。でもいざ実装を始めると、頭壊れる問題ですね。。。^^;

問題へのリンク

問題概要

$N$ 個の整数 $A_{1}, \dots, A_{N}$ が与えられる。これらから 2 つを選んで積をとって得られる $\frac{N(N-1)}{2}$ 個の整数のうち、小さい順に $K$ 番目の値を求めよ。

制約

$2 \le N \le 2 \times 10^{5}$
$-10^{9} \le A_{i} \le 10^{9}$

考えたこと

「小さい順に $K$ 番目の値を求めよ」と言われたときに、頻出の一つの考え方がある。それは、問題を次のように言い換えることだ。

$x$ 以下のものが $K$ 個以上あるような、最小の $x$ を求めよ

この言い換えを行うと、二分探索で求められるということがわかる！！！つまり、次の判定問題を、 $\log$ 回解けば良いのだ。

$x$ 以下のものが $K$ 個以上あるかどうかを判定せよ。

判定パート

$A_{1}, \dots, A_{N}$ から 2 つ選んで積をとった値のうち、 $x$ 以下のものが何個あるかを求める問題となった。依然として $O(N^{2})$ から落とすことが課題となるけど、かなり考えやすくなった。

こういうシチュエーションを扱う定石として、「1 つを固定したときに、条件を満たす相方が何個あるのかを求める」というのがある。注意点として、

$A_{i}$ の相方として $A_{j}$ を選ぶ
$A_{j}$ の相方として $A_{i}$ を選ぶ

というのは重複してしまうので、最後に 2 で割ることにする。あと、

$A_{i}$ の相方として $A_{i}$ 自身を選ぶ

というのもまとめて数えてしまっていい。最後にそれも除く。まとめると、以下の手順で求めることができる。

各 $A_{i}$ について、 $A_{1}, \dots, A_{N}$ のうち、掛けて $x$ 以上になるやつが何個あるかを求める (その合計値を $S$ とする)
$A_{i} \times A_{i} \le x$ となるようなものが何個あるかを求める $T$ とする
このとき、求める個数は $\frac{S - T}{2}$ となる

2 は $O(N)$ でできる。1 について考える。　　

Ai > 0 のとき

このとき、 $A_{i} \times y$ という値は「 $y$ について単調増加」であることに注意しよう。

よって、 $A_{1}, A_{2}, \dots, A_{N}$ をソートしておけば、

$A_{i} \times A_{j} \le x$ を満たすような $j$ の最大値

を、再び二分探索で求めることができる。なお、この部分を std::lower_bound() を使う手もありそう...だけど、 $\frac{x}{A_{i}}$ を計算する必要があって、C++ だと、この値は $x$ の正負によって挙動が変わるので場合わけが面倒だと思う。。。

Ai < 0 のとき

今度は反対に、 $A_{i} \times y$ という値は「 $y$ について単調減少」であることに注意しよう。

よって、 $A_{1}, A_{2}, \dots, A_{N}$ をソートしておけば、

$A_{i} \times A_{j} \le x$ を満たすような $j$ の最小値

を、再び二分探索で求めることができる。

まとめ

まとめると、

大元の問題を二分探索に落とす
判定パートを、A[ i ] を固定しながら処理する

計算量は、判定問題を解くのに $O(N\log{N})$ の計算量を要するので、全体で $O(N\log{N}\log{B})$ となる ( $B$ は登場する値の最大値)。

なお別解として、2. の部分の処理にしゃくとり法を用いる方法もありそう。

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

const long long INF = 1LL<<61;
long long N, K;
vector<long long> A;

long long solve() {
    sort(A.begin(), A.end());
    long long left = -INF, right = INF;
    while (right - left > 1) {
        long long x = (left + right) / 2;
        long long S = 0, T = 0;
        for (int i = 0; i < N; ++i) {
            if (A[i] > 0) {
                int l2 = -1, r2 = N;
                while (r2 - l2 > 1) {
                    int m = (l2 + r2) / 2;
                    if (A[i] * A[m] <= x) l2 = m;
                    else r2 = m;
                }
                S += r2;
            }
            else if (A[i] < 0) {
                int l2 = -1, r2 = N;
                while (r2 - l2 > 1) {
                    int m = (l2 + r2) / 2;
                    if (A[i] * A[m] <= x) r2 = m;
                    else l2 = m;
                }
                S += N - r2;
            }
            else if (x >= 0) S += N;
            if (A[i] * A[i] <= x) ++T;
        }
        long long num = (S - T) / 2;
        if (num >= K) right = x;
        else left = x;
    }
    return right;
}

int main() {
    cin >> N >> K;
    A.resize(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    cout << solve() << endl;
}

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

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

AtCoder ABC 044 C - 高橋君とカード (ARC 060 C) (水色, 300 点)

問題概要

制約

解法 (1)：平均値をまともに取り扱う

解法 (2)：平均値制約を上手に

AtCoder ARC 075 E - Meaningful Mean (青色, 600 点)

問題概要

制約

考えたこと

累積和へ

転倒数へ

コード

JOI 二次予選 2020 D - テンキー (AOJ 0675, 難易度 7)

問題概要

制約

考えたこと

AtCoder ABC 135 D - Digits Parade (水色, 400 点)

問題概要

制約

考えたこと

DP へ

AtCoder ABC 155 D - Pairs (青色, 400 点)

問題概要

制約

考えたこと

判定パート

Ai > 0 のとき

Ai < 0 のとき

まとめ

問題概要

制約

解法 (1)： 平均値をまともに取り扱う

解法 (2)： 平均値制約を上手に

問題概要

制約

考えたこと

累積和へ

転倒数へ

コード

問題概要

制約

考えたこと

問題概要

制約

考えたこと

DP へ

問題概要

制約

考えたこと

判定パート

Ai > 0 のとき

Ai < 0 のとき

まとめ

解法 (1)：平均値をまともに取り扱う

解法 (2)：平均値制約を上手に