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

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

AtCoder AGC 043 B - 123 Triangle (青色, 700 点)

AtCoder AtCoder700点 AGC-B パリティ 不変量 二項係数 個別の要素の動きに注目する 場合分け 絶対値やminを扱う問題 倍数判定や九去法 数列 経路数に帰着 係数を考える 数学的帰納法に基づく考察 0と1と2の問題 青色diff ピラミッド 操作後の結果を求める問題 操作:隣接要素の和や差をとる

答えが 0, 1, 2 の三通りしかないとなれば、mod で絞るのをやりたくなる！ 受験数学では定番のテクニックだ！！！

問題へのリンク

問題概要

長さ N の、1, 2, 3 のみからなる数列が与えられる。この数列に対して、

  • 隣接する要素の差を書き出す

という操作を、数列の長さが 1 になるまで繰り返す。最後に残る値を答えよ。

制約

  • 2 \le N \le 10^{6}

考えたこと

ひとまず、1 回は操作してしまう。そうすると数列が 0, 1, 2 のみになる。そこから後はずっと 0, 1, 2 しか登場しない世界となる。まともにシミュレーションしたら O(N^{2}) かかってしまう。何かしたら省略できるからくりがあるはず。こういうので今まで経験したのは

  • パリティで絞れる
  • 何かしら単調性があって二分探索できる

といったあたり。ザッと手元で実験した感じだと、なんか構造がある気がしない。というわけで、mod で絞るのを決行することに！

そして今回、絶対値制約が mod. 2 で考えろとささやいているようにも見える。なぜなら

  • |a - b| \equiv a + b \pmod 2

が成立するからだ。mod. 2 であれば「足し算」も「引き算」も一緒だというのが効いている。

  • a - b \equiv a + b \pmod 2
  • b - a \equiv a + b \pmod 2

がともに成立するので、絶対値があろうとなかろうと関係ないのだ。この特質は mod. 2 でしか成り立たない。さて、ここから言えることは一つ。「mod. 2 で考えれば、少なくとも答えの偶奇は必ず特定できるはず」ということだ。これで 0 or 2 か、1 かのどちらかには絞ることができる。まずはそれを考えることにした。

さて、mod. 2 で考えたとき、最終結果は a_{0}, a_{1}, \dots, a_{N-1} の線形結合で表せるはずだ。つまり

  • x_{0} a_{0} + x_{1} a_{1} + \dots + x_{N-1} a_{N-1}

という形になるはずなのだ。なのであとは係数 x_{i} を求めればいいはずだ。こういう風に「係数を考えればいい」という考察はめちゃくちゃ良く見る。

そしてその係数は良く考えると簡単だ。今回のシミュレーションの構造は、パスカルの三角形そのものなので、二項係数になる。つまり

  • C(N-1, 0) a_{0} + \dots + C(N-1, N-1) a_{N-1}

となる。よって二項係数の偶奇がわかれば OK。

二項係数の偶奇

二項係数の偶奇が、シェルピンスキーのガスケットとよばれる構造を持っていることはよく知られている。

mathtrain.jp

このことの考察を深めるとリュカの定理というのに行き着く。

mathtrain.jp

しかしそんなことしなくても、 C(n, r) の偶奇を調べたかったら単純に

  • n! が 2 で何回割れるかを求めて、そこから
  • r! が 2 で何回割れるのかを引いて、
  • (n-r)! が 2 で何回割れるのかを引いて、

残った値が 1 以上かどうかで判定することができる。

0 or 2 になったときは...

さて、以上から最終結果が偶数か奇数かはわかった。奇数なら答えは 1 で確定する。偶数の場合は 0 か 2 かを絞らなければならない。

ここで、「2 になるためにはどういう条件が必要か」を考察することにしよう。最終結果が 2 になるように、数列を遡っていくイメージで手を動かしていくと、

  • 最後の結果を 2 とすると、0 と 2 しか作れない

ということがわかってくる。そしてもう一つ。

  • 初期数列に 1 が存在しないならば、途中で 1 が生えてくることが絶対にない

ということも見えて来る。それはそうで、初期数列に 1 がないということは、最初からすべて偶数なのだから、差をとっても偶数しか生まれないのだ。したがって、

  • 最終結果が偶数で、初期数列に 1 がある： 答えは 0
  • 最終結果が偶数で、初期数列に 1 がない： もう少し考える

という状態になった。

初期数列に 0 と 2 しかないとき...

良く考えるとこれはもう、全体を 2 で割ってしまってよい。そうすると、

  • 初期数列は 0 と 1 しかない
  • その差分も 0 と 1 しかない

という状態に落ち着く。この最終結果が 0 ならば、元の問題の答えも 0 で、1 ならば、元の問題の答えは 2 だ。

そして、2 で割ったバージョンで最終結果が 0 か 1 かを求める問題は、結局先ほどと同じように偶奇を求めればよい。

まとめ

  • パリティが奇数なら、答えは 1
  • パリティが偶数で、1 が含まれるなら、答えは 0
  • パリティが偶数で、1 が含まれないとき、全体を 2 で割って
    • その状態でパリティが偶数なら、答えは 0
    • その状態でパリティが奇数なら、答えは 2

計算量は O(N)。

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

const int MAX = 1100000;
vector<long long> cnt; // cnt[n] := n! が 2 で何回割れるか
void pre() {
    cnt.assign(MAX, 0);
    for (int i = 1; i < MAX; ++i) {
        int j = i;
        int add = 0;
        while (j % 2 == 0) ++add, j /= 2;
        cnt[i] = cnt[i-1] + add;
    }
}

int solve(const string &S) {
    pre();
    vector<int> a;
    for (int i = 0; i + 1 < S.size(); ++i) {
        int x = S[i] - '0';
        int y = S[i+1] - '0';
        a.push_back(abs(x - y));
    }
    long long parity = 0;
    for (int i = 0; i < a.size(); ++i) {
        long long ex = cnt[a.size()-1] - cnt[i] - cnt[a.size()-i-1];
        if (ex > 0) continue;
        parity += a[i];
    }

    if (parity & 1) return 1;
    else {
        bool exist_one = false;
        for (int i = 0; i < a.size(); ++i) if (a[i] == 1) exist_one = true;
        if (exist_one) return 0;
        else {
            parity = 0;
            for (int i = 0; i < a.size(); ++i) {
                long long ex = cnt[a.size()-1] - cnt[i] - cnt[a.size()-i-1];
                if (ex > 0) continue;
                parity += a[i] / 2;
            }
            if (parity & 1) return 2;
            else return 0;
        }
    }
}

int main() {
    int N;
    string S;
    cin >> N >> S;
    cout << solve(S) << endl;
}

AtCoder AGC 043 A - Range Flip Find Route (緑色, 400 点)

AtCoder AtCoder400点 AGC-A 盤面を予め変更する 最適化テク:固定する変数を入れ替えて考える ある量を固定して考える 最小コスト 最小回数・最小個数を求める 迷路 二次元グリッド DP XOR 操作 操作:flip 条件の言い換え 操作:区間 区間 最短路問題 緑色diff 魔法を唱える問題 【問題集】最短路問題 壁マス 最適化問題

「予め盤面をいじることができる」という設定の問題にはある程度の定石があるように思う！

問題へのリンク

問題概要

H \times W の盤面が与えられ、左上から右下まで行きたい。'#' マスは壁を表し、'.' マスは通路を表す。

予め盤面に以下の操作を行うことができる。最小回数の操作を行うことで、左上から右下まで、最短経路で (右か下への移動のみで) 到達できるようにせよ。

  • 長方形区域を選んで、その中の通路と壁を反転する

制約

  • 2 \le H, W \le 100

考えたこと

こういう「スタートする前に予め盤面をいじっておくことができる」というタイプの問題には一定の定石があるのだ。そういうタイプの類題としては、以下のような問題たちがある！

drken1215.hatenablog.com

drken1215.hatenablog.com

こういうタイプの問題では、

  • まずは経路を一つ固定してみる
  • その経路が条件を満たすようにするための最小操作回数を求めてみる
  • それがわかれば、元の問題の解き方も自然とわかってくる

という流れが典型的だと思う。今回は、経路を固定してみると、下図のように、

  • 経路中の連続する壁はまとめて破壊できる
  • 経路中の飛び飛びの壁はまとめて破壊することはできない

ということがわかる。

したがって元の問題は次のように言い換えることができるのだ。

以下のように左上から右下へ進みたい。その際に魔法を唱える回数をできるだけ減らしたい。魔法を唱える回数の最小値を求めよ。

  • 魔法を唱えると壁の中に進むことができる
  • 魔法が効いている間は壁の中をそのまま突き進むことができる
  • 壁を抜けて通路に出ると、魔法の効果が切れる

(右か下にしか進めない)

ここまでわかれば、次のような DP を組むことができる。

  • dp[ x ][ y ] := マス (x, y) に到達するまでに魔法を唱える回数の最小値

初期値は

  • スタート地点が壁のとき： dp[ 0 ][ 0 ] = 1
  • スタート地点が通路のとき： dp[ 0 ][ 0 ] = 0

ということになる。そして、(x, y) から (nx, ny) への移動に関する DP 遷移は、

  • (nx, ny) が通路のとき： chmin(dp[ nx ][ ny ], dp[ x ][ y ])
  • (nx, ny) か壁で、(x, y) が通路のとき： chmin(dp[ nx ][ ny ], dp[ x ][ y ] + 1)
  • (nx, ny) が壁で、(x, y) も壁のとき： chmin(dp[ nx ][ ny ], dp[ x ][ y ])　(魔力が継続中)

として実現できる ( (nx, ny) = (x + 1, y) or (x, y + 1) )。

#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; }

const vector<int> dx = {1, 0};
const vector<int> dy = {0, 1};
const long long INF = 1LL<<60;
int H, W;
vector<string> fi;

long long solve() {
    vector<vector<long long>> dp(H, vector<long long>(W, INF));
    if (fi[0][0] == '#') dp[0][0] = 1;
    else dp[0][0] = 0;

    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            for (int dir = 0; dir < 2; ++dir) {
                int ni = i + dx[dir], nj = j + dy[dir];
                if (ni >= H || nj >= W) continue;
                int add = 0;
                if (fi[ni][nj] == '#' && fi[i][j] == '.') add = 1;
                chmin(dp[ni][nj], dp[i][j] + add);
            }
        }
    }
    return dp[H-1][W-1];
}

int main() {
    cin >> H >> W;
    fi.resize(H);
    for (int i = 0; i < H; ++i) cin >> fi[i];
    cout << solve() << endl;
}

Codeforces Round #201 (Div. 1) A. Alice and Bob (R1600)

Codeforces 数学(整数問題) 操作がEuclidの互除法に対応 最大公約数 パリティ ゲーム CodeforcesDIV1-A CodeforcesR1600

シンプルで楽しい感じ

問題へのリンク

問題概要

N 要素からなる数列 A_{1}, \dots, A_{N} がある (互いに相異なる)。交互に以下の操作を行う

  • 数列から 2 つの整数を選んで、その差を数列の末尾に追加する
  • ただし、「その差の値」がすでに数列中に含まれる場合は、この操作を行うことはできない

先に操作を行えなくなった方が負けである。双方最善を尽くしたとき、どちらが勝つか？

制約

  • 2 \le N \le 100
  • 1 \le A_{i} \le 10^{9}

考えたこと

N 個の整数の最大公約数を g として、 g の倍数のうち A の最大値以下のものはすべて作れる。逆にそれ以外は作れない。よって、

(その個数) - N

のパリティのみで勝敗が決まってしまう。戦略性は関係ない。

#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; }

long long GCD(long long x, long long y) {
    if (y == 0) return x;
    else return GCD(y, x % y);
}

int main() {
    int N; cin >> N;
    long long ma = 0, g = 0;
    for (int i = 0; i < N; ++i) {
        long long a;
        cin >> a;
        g = GCD(g, a);
        chmax(ma, a);
    }
    if ((ma/g - N) % 2 == 1) cout << "Alice" << endl;
    else cout << "Bob" << endl;
}

AtCoder Petrozavodsk Contest 001 C - Vacant Seat (緑色, 500 点)

AtCoder AtCoder500点 インタラクティブ 二分探索 二分探索:境界のうちの1つを見つける 数珠 テク:循環するものを二週させる 方程式 パリティ 緑色diff 中間値の定理

インタラクティブ...でも問題自体は「単調性が成り立たなくても二分探索できるよ！」という教育的なものだった！

問題へのリンク

問題概要

円形状に並んだ N 個の椅子がある ( N は奇数)。各椅子は

  • 男性がいる
  • 女性がいる
  • 空席

のいずれかである。どの隣り合う 2 つの席も、同性の人が座っていることはない。また、空席が一つ以上存在することがわかっているのでそれを特定したい。20 回以内の質問で当てよ。

制約

  • 3 \le N \le 99999

考えたこと

単調でなかったとしても、両端の間に解があることがわかっているときにその間を挟むようにするタイプの二分探索ですね！！！

  • 間隔が偶数で、両端の性別が異なる
  • 間隔が奇数で、両端の性別が等しい

という場合には、かならずその間に空席が存在することが示せるので、空席を挟むようにして二分探索できる。

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

bool betemp(string sleft, string sright, int left, int right) {
    if (sleft == sright) return (right - left) % 2 == 1;
    else return (right - left) % 2 == 0;
}

void solve(int N) {
    string vac = "Vacant";
    string sleft, sright, str;
    int left = 0, right = N/2;
    cout << left << endl;
    cin >> sleft;
    if (sleft == vac) return;
    cout << right << endl;
    cin >> sright;
    if (sright == vac) return;

    if (!betemp(sleft, sright, left, right)) {
        swap(sleft, sright), left = right, right = N;
    }
    while (right - left > 1) {
        int mid = (left + right) / 2;
        cout << mid << endl;
        cin >> str;
        if (str == vac) return;
        if (betemp(sleft, str, left, mid)) sright = str, right = mid;
        else sleft = str, left = mid;
    }
}

int main() {
    int N;
    while (cin >> N) solve(N);
}

AtCoder Petrozavodsk Contest 001 B - Two Arrays (緑色, 300 点)

AtCoder AtCoder300点 数列 操作 Yes/No判定問題 操作を好きな回数だけ行える SをTにすることが目的の操作の問題 必要条件を列挙したら十分条件になる 決めてから整合性を確認する Greedy:端から順に決まっていく Greedy 緑色diff

面白かった。間違いやすいけど、このくらいなら！！！

問題へのリンク

問題概要

長さ N の正の整数からなる二つの数列 a_{1}, \dots, a_{N}、 b_{1}, \dots, b_{N} が与えられる。以下の操作を好きな順序で好きな回数だけ行える。 a と b が一致するようにすることは可能か？

  • a の要素を一つ選んで +2 する
  • b の要素を一つ選んで +1 する

制約

  • N \le 10^{4}

考えたこと

とりあえず、 a の方が全体的に小さい必要がありそう。極端な話、すべての index について、a[ i ] <= b[ i ] であれば、全然可能である。

よって話は、a[ i ] > b[ i ] となっているような場所をいかにして補償するかである。

  • a[ i ] > b[ i ] のところについて、b[ i ] に 1 を足す代わりに
  • a[ j ] < b[ j ] のところについて、a[ j ] に 2 を足す

という風にしていく。その結果、すべての index について a[ i ] <= b[ i ] とにう状態になれば "Yes"、そうでなければ "No" だ。

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

int main() {
    int N; cin >> N;
    vector<long long> a(N), b(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    for (int i = 0; i < N; ++i) cin >> b[i];
    long long biggerA = 0, biggerB = 0;
    for (int i = 0; i < N; ++i) {
        if (a[i] > b[i]) biggerA += a[i] - b[i];
        if (b[i] > a[i]) biggerB += (b[i] - a[i])/2;
    }
    if (biggerB >= biggerA) cout << "Yes" << endl;
    else cout << "No" << endl;
}