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

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

AtCoder ABC 176 B - Simple Math 4 (水色, 400 点)

AtCoder AtCoder400点 ARC-B 水色diff 数学(整数問題) コーナーケース マルチテストケース問題 入力が定数個 2^K 互いに素

M - K = 1 というコーナーケースにやられた！

問題概要

整数 N, M, K が与えられる。

2^{N} を 2^{M} - 2^{K} で割った余りの一の位の値を求めよ。

(マルチテストケース)

制約

  • 1 \le N \le 10^{18}
  • 1 \le K \lt M \le 10^{18}

　

考えたこと

まず最初に考えたのは「全体を 2^{K} で割った世界」で考えれば良いということ。

このことを正当化しよう。一般に、次のことが成り立つ。

整数 a, b, k と正の整数 m に対して

a \equiv b \pmod m

であることと、

ka \equiv kb \pmod{km}

であることは同値である。

つまり、 2^{N-K} を 2^{M-K} - 1 で割った余りを r とすると、

2^{N-K} \equiv r \pmod{2^{M-K} - 1}

と表せるが、これを全体に 2^{K} 倍して得られる

2^{N} \equiv 2^{K}r \pmod{2^{M} - 2^{K}}

は同値だということだ。

よって、この問題の答えは

2^{N-K} を 2^{M-K} - 1 で割った余りを求めて、 2^{K} をかけた値

となることがわかった。

例外処理

ただし、 N \lt K の場合は例外なので例外扱いする。

この場合は、 2^{N} \lt 2^{K} \le 2^{M} - 2^{K} であるから、答えは 2^{N} である。

　

本題

以降、 N \ge K とする。そして、「 2^{N-K} を 2^{M-K} - 1 で割った余り」を頑張って求める。

ここで、今度は次のことに注目しよう。

相異なる整数 a, b と、整数多項式 f(x) に対して、次のことが成り立つ。

f(a) \equiv f(b) \pmod{a - b}

つまり、 \pmod{a - b} についての合同式を考えるとき、 a の部分をそのまま b に置き換えてよいということだ！！！

そうすると、たとえば N - K = 14, M - K = 3 のとき、次のように式変形できる。

2^{14} = (2^{3})^{4} \times 2^{2} \equiv 1^{4} \times 2^{2} = 2^{2} \pmod{2^{3} - 1}

より一般に、 N - K を M - K で割った余りを r とすると、次のようになる。

2^{N - K} \equiv 2^{r} \pmod{2^{M-K} - 1}

よって、この問題の答えは 2^{r+K} である。あとは、この値を 10 で割った余りを求めれば OK。

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

　

コード

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

template<class T> T mod_pow(T a, T n, T m) {
    T res = 1;
    while (n > 0) {
        if (n % 2 == 1) res = res * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return res;
};

void solve() {
    long long N, M, K;
    cin >> N >> M >> K;
    
    if (N < K) {
        cout << mod_pow(2LL, N, 10LL) << endl;
    } else {
        if (M - K == 1)
            cout << 0 << endl;
        else
            cout << mod_pow(2LL, (N - K) % (M - K) + K, 10LL) << endl;
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) solve();
}

AtCoder ABC 350 C - Sort (灰色, 300 点)

順列テク:逆順列を考える 順列 ソートすることが目的の操作の問題 構築 AtCoder AtCoder300点 灰色diff ABC-C そのまま覚えたい易しい教育的典型問題 データ構造テク:どこにその要素があるのかを管理する 操作 操作をK回まで行える 操作:swap

O(N^{2}) の計算量で良いなら簡単。

「どこに値 i の要素があるのか」を管理するというテクニックをここで習得しよう！

問題概要

1, 2, \dots, N の並び替えである順列 A_{1}, A_{2}, \dots, A_{N} が与えられる。これをソートしたい。以下の操作を N-1 回まで実施できる。

  • i, j を選んで、 A_{i} と A_{j} を swap する

ソートするための操作列を 1 つ求めよ (必ず可能であることは示せる)。

制約

  • N \le 2 \times 10^{5}

考えたこと

この手の問題では、最初は計算量を気にせずに考えるとよい。最後に高速化を試みよう。

この問題に対しては、トランプなどでカードが配られて、それを見やすい順に並び替えるときのことを思い出すと、次のような解法が自然に思い浮かぶ。

  • まず、1 を探して、それを左から 1 番目に持ってくる
    • ただし、もともと左から 1 番目が 1 のときは何もしない
  • 次に、2 を探して、それを左から 2 番目に持ってくる
    • ただし、もともと左から 2 番目が 2 のときは何もしない
  • ...
  • 最後に、 N-1 を探して、それを左から N-1 番目に持ってくる
    • ただし、もともと左から N-1 番目が N-1 のときは何もしない

最後を N ではなく、 N-1 までにしているのは、「左から 1, 2, \dots, N-1 までが揃った時点で、 N の位置も自動的に揃っているため」だ。

さて、値 i (= 1, 2, \dots, N-1) について考えているとき、愚直にやると、以下の処理に O(N) の計算量を要する。

A_{i+1}, A_{i+2}, \dots, A_{N} の中から、値が i であるものを探す

そのため、全体の計算量は O(N^{2}) となってしまう。上記の処理を高速化しよう。

　

高速化

上記の処理を高速化するためには、次の情報を管理すればよい！！　この「どこにその要素があるのかを管理するテク」はより高難易度の問題では頻出する！！

  • where[v] ← A_{i} = v であるような i

この値を管理すれば、上記の「 A_{v+1}, A_{v+2}, \dots, A_{N} の中から、値が v であるものを探す」という処理を O(1) の計算量でこなすことができて、全体の計算量も O(N) となるのである。

where の更新

最後に、 A_{i} と A_{j} を swap するときに、この配列 where も更新する必要があることに注意しよう。慣れないと難しいかもしれない。次のようにできる (これは憶えてしまおう)。

swap(where[A[i]], where[A[j]]);
swap(A[i], A[j]);

ここで、1 行目と 2 行目の順序を間違えないように注意しよう。2 行目を先にやってしまうと、1 行目の処理において、更新されてしまった配列 A の情報を活用することとなるためだ。

　

コード

全体的に 0-indexed で実装した。

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;

int main() {
    int N;
    cin >> N;
    vector<int> A(N), where(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        --A[i];
        
        // 値 A[i] があるのは i 番目
        where[A[i]] = i;
    }
    
    // 左から i 番目に、値 i を持ってくる処理をする
    vector<pint> res;
    for (int i = 0; i <= N - 2; ++i) {
        // i 番目がすでに値 i なら何もしない
        if (A[i] == i) continue;
        
        // 値 i がある場所
        int j = where[i];
        
        // A[i] と A[j] を swap する
        swap(where[A[i]], where[A[j]]);
        swap(A[i], A[j]);
        res.emplace_back(i, j);
    }
    
    // 出力
    cout << res.size() << endl;
    for (auto [i, j] : res) {
        cout << i+1 << " " << j+1 << endl;
    }
}

AtCoder ABC 350 B - Dentist Aoki (灰色, 200 点)

バケット 集計処理 AtCoder AtCoder200点 ABC-B 灰色diff データ構造 フラグを活用する ビットを活用する 操作:flip 操作 そのまま覚えたい易しい教育的典型問題

「集計処理」の基本問題！

問題概要 (意訳)

N 個の LED が最初はすべて光っている。

Q 回の処理を行う。 i 回目の処理では T_{i} 番目の LED の状態を flip する (光っていたら消して、消えていたら光らせる)。

最終的に何個の LED が光っているかを求めよ。

解法

次の配列を用意しよう。

  • haeteru[v] ← v 番目の LED が光っているとき 1、そうでないとき 0

このとき、 T_{i} 番目の LED を flip する操作は次のように書ける。

haeteru[v] = 1 - haeteru[v];

この実装によって、0 は 1 になり、1 は 0 になる。 Q 回の処理を終えたあとは、 1 の個数を数えれば OK。

コード

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

int main() {
    int N, Q;
    cin >> N >> Q;
    
    vector<int> haeteru(N, 1);
    for (int i = 0; i < Q; ++i) {
        int T;
        cin >> T;
        --T;
        haeteru[T] = 1 - haeteru[T];
    }
    
    int res = 0;
    for (int i = 0; i < N; ++i) {
        res += haeteru[i];
    }
    cout << res << endl;
}

AtCoder ABC 176 C - Max Permutation (黄色, 700 点)

グラフ テク:グラフの問題として考える 探索順序を工夫して解く 各地点について自由度を掛け算していく 数え上げ問題 AtCoder AtCoder700点 ARC-C 黄色diff 後退解析 順列 グラフ・盤面・数列の個数の数え上げ

これは面白かった。

問題概要

1, 2, \dots, N の順列であって、以下の M 個の条件を満たすものの個数を 998244353 で割った余りを求めよ。

  • j = 1, 2, \dots, M について、 \max(P_{A_{j}}, P_{B_{j}}) = C_{j} である

制約

  • N, M \le 2 \times 10^{5}

考えたこと

グラフの問題として考えることにした。つまり、0-indexed で表現すると

頂点数 N、辺数 M であるグラフが与えられる。各辺には 0 以上 N-1 以下の重みがついている。

各頂点に 0, 1, \dots, N-1 の値を割り振る方法であって、どの辺についても両端の頂点の値の最大値が辺の重みに一致する方法の個数を求めよ。

重みが大きい方から順に考えることとした。次のように考えることができた。

また、常に「未使用の孤立頂点の個数」を表す値 s を管理しておくこととする。初期状態では

  • res = 1
  • s = (初期グラフの孤立点の個数)

としておく。

値 x = N-1, N-2, \dots, 0 について順に考えて

  • 重み x の辺が存在しないとき:
    • もし s = 0 ならば、答えは問答無用で 0 通りである
    • そうでないならば、res *= s, --s とする
  • 重み x の辺がちょうど 1 本存在するとき:
    • その時点でのグラフについて、もしその辺の両端の次数がともに 2 以上ならば、答えは問答無用で 0 通りである
    • そうでないとき、重み x の頂点を以下のように決定し、その頂点を削除する (このとき、孤立点が新たに誕生するならば ++s とする)
      • 片方の頂点の次数が 1、他方の頂点の次数が 2 以上のとき、次数 1 の頂点の値を x にする
      • 両端の頂点の次数が 1 のとき、いずれかの頂点の値を x とする (`res *= 2' とする)
  • 重み v の辺が 2 本以上存在するとき:
    • それらの辺がスターグラフを形成していないならば、問答無用で 0 通りである
    • そうでないとき、スターグラフの中心の頂点を v として、以下のようにする
      • 頂点 v に重み v 未満の辺が接続しているならば、問答無用で 0 通りである
      • そうでないとき、頂点 v の重みを x の頂点として、その頂点 v を削除する (このとき、孤立点が新たに誕生するならば ++s とする)

こうして重みが v = N-1, N-2, \dots, 0 の頂点を順に決定していく。計算量は O(N) となる。

コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;

// modint
template<int MOD> struct Fp {
    // inner value
    long long val;
    
    // constructor
    constexpr Fp() : val(0) { }
    constexpr Fp(long long v) : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr long long get() const { return val; }
    constexpr int get_mod() const { return MOD; }
    
    // arithmetic operators
    constexpr Fp operator + () const { return Fp(*this); }
    constexpr Fp operator - () const { return Fp(0) - Fp(*this); }
    constexpr Fp operator + (const Fp &r) const { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp &r) const { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp &r) const { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp &r) const { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp &r) {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp &r) {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp &r) {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp &r) {
        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 Fp pow(long long n) const {
        Fp res(1), mul(*this);
        while (n > 0) {
            if (n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }
    constexpr Fp inv() const {
        Fp res(1), div(*this);
        return res / div;
    }

    // other operators
    constexpr bool operator == (const Fp &r) const {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp &r) const {
        return this->val != r.val;
    }
    constexpr Fp& operator ++ () {
        ++val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -- () {
        if (val == 0) val += MOD;
        --val;
        return *this;
    }
    constexpr Fp operator ++ (int) const {
        Fp res = *this;
        ++*this;
        return res;
    }
    constexpr Fp operator -- (int) const {
        Fp res = *this;
        --*this;
        return res;
    }
    friend constexpr istream& operator >> (istream &is, Fp<MOD> &x) {
        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) {
        return os << x.val;
    }
    friend constexpr Fp<MOD> pow(const Fp<MOD> &r, long long n) {
        return r.pow(n);
    }
    friend constexpr Fp<MOD> inv(const Fp<MOD> &r) {
        return r.inv();
    }
};

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

int main() {
    int N, M;
    cin >> N >> M;
    
    // グラフを求める
    vector<vector<pint>> G(N);
    vector<int> deg(N, 0);
    vector<vector<pint>> edges(N);
    for (int i = 0; i < M; ++i) {
        int a, b, x;
        cin >> a >> b >> x;
        --a, --b, --x;
        G[a].emplace_back(b, x), G[b].emplace_back(a, x);
        ++deg[a], ++deg[b];
        edges[x].emplace_back(a, b);
    }
    
    // 孤立点の個数を求める
    int solitude = 0;
    for (int i = 0; i < N; ++i) {
        if (deg[i] == 0) ++solitude;
    }
    
    // 頂点 v を削除する関数
    auto pop = [&](int v) -> void {
        deg[v] = 0;
        for (auto e : G[v]) {
            --deg[e.first];
            if (deg[e.first] == 0) {
                ++solitude;
            }
        }
    };
    
    auto solve = [&]() -> mint {
        mint res = 1;
        
        for (int x = N-1; x >= 0; --x) {
            if (edges[x].empty()) {
                if (solitude == 0) return mint(0);
                res *= solitude;
                --solitude;
            } else {
                const auto &vec = edges[x];
                if (vec.size() == 1) {
                    int a = vec[0].first, b = vec[0].second;
                    if (deg[a] == 1 && deg[b] == 1) {
                        res *= 2;
                        pop(a);
                    } else if (deg[a] == 1) {
                        pop(a);
                    } else if (deg[b] == 1) {
                        pop(b);
                    } else {
                        return mint(0);
                    }
                } else {
                    map<int, int> ma;
                    for (auto [a, b] : vec) {
                        ++ma[a];
                        ++ma[b];
                    }
                    
                    int node = -1;
                    for (auto [val, num] : ma) {
                        if (num != 1) {
                            if (node != -1) return mint(0);
                            node = val;
                        }
                    }
                    
                    if (deg[node] != vec.size()) return mint(0);
                    pop(node);
                }
            }
        }
        return res;
    };
    cout << solve() << endl;
}

AtCoder ARC 176 A - 01 Matrix Again (水色, 400 点)

気付き系 格子点をmodごとに分類する 構築 構築:modに着目する 二次元グリッド 構築:グリッド 構築:線形結合 AtCoder AtCoder400点 ARC-A 制約条件:総和=K 制約条件:行和=K/列和=K sparseな問題 水色diff

大敗してしまったので自戒を込めて。

問題概要

整数 N, M が与えられる。 N \times N のグリッドであって、以下の条件を満たすものを構築せよ。

  • 各マスの値は 0 または 1 である
  • M 個のマス (A_{0}, B_{0}), \dots, (A_{M-1}, B_{M-1}) の値はいずれも 1 である
  • 行和はすべて M である
  • 列和はすべて M である

制約

  • N \le 10^{5}
  • M \le \min(N, 10)

考えたこと

たとえば N = 5, M = 3 のときを考える。

以下の 5 種類の盤面は、

  • いずれも「行和 = 1」「列和 = 1」である
  • 盤面間で、1 であるマスが disjoint である

という性質を満たすことに着目しよう (赤マスを 1、白マスを 0 とする)。

これら 5 個の盤面の中から、 3 種類選んで結合する (各マスについて和をとる) と、「行和 = 3」「列和 = 3」となるのだ。

ここで、 5 種類の選び方を柔軟に変えれば、どんな入力 (A_{0}, B_{0}), (A_{1}, B_{1}), (A_{2}, B_{2}) にも対応できる。

  • マス (A_{0}, B_{0}) が赤色になっている盤面
  • マス (A_{1}, B_{1}) が赤色になっている盤面
  • マス (A_{2}, B_{2}) が赤色になっている盤面

をそれぞれ選んでくればよいのだ。仮に被ったとしても、他のものを持ってくれば OK。

以上の方法は、一般の N, M に対しても適用できる。なお、この解法は実は公式解説と同じである。

コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;

int main() {
    int N, M;
    cin >> N >> M;
    
    // M 種類の盤面を選ぶ
    // 具体的にはマス (i, j) に対して、i + j mod N の値で類別する
    set<int> S;
    for (int i = 0; i < M; ++i) {
        int A, B;
        cin >> A >> B;
        --A, --B;
        S.insert((A + B) % N);
    }
    // 被った場合の処理
    for (int i = 0; i < N; ++i) {
        if (S.size() == M) break;
        if (!S.count(i)) S.insert(i);
    }
    
    // M 種類の盤面を結合する
    vector<pint> res;
    for (int i = 0; i < N; ++i) {
        for (auto r : S) {
            res.emplace_back(i, (r - i + N) % N);
        }
    }
    
    // 出力する
    cout << res.size() << endl;
    for (auto [x, y] : res) {
        cout << x+1 << " " << y+1 << endl;
    }
}