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

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

AtCoder ABC 161 F - Division or Substraction (600 点)

めちゃくちゃ面白かった!!!

問題へのリンク

問題概要

整数  N が与えられる。以下の条件を満たす  2 以上  N 以下の整数  K の個数を求めよ。

  • 整数  K を用いて、 N に対して操作を行っていく
  •  N K で割り切れるならば  N N/K で置き換えて、そうでない場合には  N N-K に置き換える。
  • 上記の操作を  N K 未満になるまで繰り返したとき、 N 1 となる

制約

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

考えたこと

問題文を読んでも状況がパッとつかめない。こういうときは幾つかのケースを手で試すと良さそうである。 N = 22 のときは、こんな感じになる。

K 変化 結果
2 22 → 11 → 9 → 7 → 5 → 3 → 1 o
3 22 → 19 → 16 → 13 → 10 → 7 → 4 → 1 o
4 22 → 18 → 14 → 10 → 6 → 2 x
5 22 → 17 → 12 → 2 x
6 22 → 16 → 10 → 4 x
7 22 → 15 → 8 → 1 o
8 22 → 14 → 6 x
9 22 → 13 → 4 x
10 22 → 12 → 2 x
11 22 → 2 x
12 22 → 10 x
13 22 → 9 x
14 22 → 8 x
15 22 → 7 x
16 22 → 6 x
17 22 → 5 x
18 22 → 4 x
19 22 → 3 x
20 22 → 2 x
21 22 → 1 o
22 22 → 1 o

ここから読み取れることは

  •  K N の約数でないときは、最終的には  N %  K が残る
  •  K N の約数のときは、 N K で割れるだけ割った値を  N' として、 N' %  K が残る

といったことだ。場合分けして考えてみよう。

 K N の約数でないとき

 N K で割ったあまりが 1 になればよいのだ。つまり、

 N ÷ K = q あまり  1
 N -1 = Kq

という風になればよい。これは、 K N-1 の約数であることを意味するのだ。よりちゃんというと、以下の条件を満たすことが必要十分条件である!!!


  •  K N-1 の約数
  •  K \gt 1

注意点として、もしこれが「 N K で割ったあまりが  r になるような  K を求めよ」という問題だった場合には、こういう風になる。

  •  K N-r の約数
  •  K \gt r

「あまりは割る数より小さくなければならない」という見えない制約に注意する。今回はあまりが 1 なので、深く気にしなくても大丈夫。

 K N の約数であるとき

そもそも  N の約数の個数が少ないので、これはもう全て試してしまうのがわかりやすいと思う。

まとめ

以上をまとめると、答えは以下を合わせたもの

  •  N-1 の約数のうち、 1 を除外したもの
  •  N の約数はすべて調べ尽くす

なお、前者と後者は被ることはない ( N-1 N は互いに素)。計算量は  O(\sqrt{N}) となる。

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

vector<long long> calc_divisor(long long n) {
    vector<long long> res;
    for (long long i = 1LL; i*i <= n; ++i) {
        if (n % i == 0) {
            res.push_back(i);
            long long j = n / i;
            if (j != i) res.push_back(j);
        }
    }
    sort(res.begin(), res.end());
    return res;
}

long long solve(long long N) {
    const auto &div1 = calc_divisor(N-1);
    const auto &div2 = calc_divisor(N);
    long long res = (int)div1.size() - 1; // 1 を除外
    for (auto d : div2) {
        if (d == 1) continue;
        long long NN = N;
        while (NN % d == 0) NN /= d;
        if ((NN-1) % d == 0) ++res;
    }
    return res;
}

int main() {
    long long K;
    while (cin >> K) cout << solve(K) << endl;
}

AtCoder AGC 004 C - AND Grid (700 点)

こういうの大好き!

問題へのリンク

問題概要

 H \times W の盤面 A が与えられる。各マスは白か黒かのいずれかである。次の条件を満たす、同じ大きさの白黒の二つの盤面の組 (S, T) を構築せよ

  • S の黒マスはすべて縦横に連結である
  • T の黒マスはすべて縦横に連結である
  • S の黒マスに対応する部分と、T の黒マスに対応する部分との共通部分が A に丁度一致する

制約

  •  3 \le H, W \le 500
  • A の外周は白マスである

考えたこと

こういうのはとりあえず、いくつかのケースで遊んでみると良さそう

.....
.#.#.
..#..
.....

とかは

.....  .....
.###.  .#.#.
..#..  .###.
.....  .....

という感じでできる。入れ子になってるとむずそう。こういうの

.........
....#....
...#.#...
..#.#.#..
.#.#.#.#.
..#.#.#..
...#.#...
....#....
.........

こういうのを攻略していくことで、一般論が見えてくるのではないかと思う。それも、実装しやすくて明快な一般論が欲しい!!!

パッと思いつくのは example 1 っぽい感じで

  • S は、各黒マスから左方向に、黒マスをずらっと伸ばしていく
  • T は、各黒マスから上方向に、黒マスをずらっと伸ばしていく

という感じ。でもこれだと余裕で被ってしまう。そもそも

..#..
.#.#.
#.#.#
.#.#.
..#..

こういう風な「内部の黒マス」は、S も T もどっちも、上下左右のどちらかには黒を伸ばさないといけない。四マスのうちのどれを S に、どれを T に割り当てたらよいのだろうか???

パリティ

こういうのを見ると、なんとなくパリティが絡みそうな気がしてくる。そもそも example がミスリードで、「一方は左に、もう一方は上に」という風にして被らせないのは至難の技なんだ。

それだったら、パリティで分岐して平行に伸ばした方がいい。つまり、こういう感じ。

ooooooooo  .........
.o.o#o.o.  o.o.#.o.o
.o.#.#.o.  o.o#o#o.o
.o#o#.#o.  o.#.#.#.o
.#.#.#.#.  o#o#o#o#o
.o#o#o#o.  o.#.#.#.o
.o.#.#.o.  o.o#o#o.o
.o.o#o.o.  o.o.#.o.o
.........  ooooooooo
  • S の方は、偶数列を塗りたくる
  • T の方は、奇数列を塗りたくる

という風にすれば、両者が被らなくて済むのだ。そして塗りたくったものが連結である必要があるので

  • S の方は上も塗りたくる
  • T の方は下も塗りたくる

という風にすればぴったり。これ、本当に上手い具合にちゃんと連結になってる。

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

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> fi(H);
    for (int i = 0; i < H; ++i) cin >> fi[i];
    vector<string> S = fi, T = fi;
    for (int w = 0; w < W; ++w) S[0][w] = '#', T[H-1][w] = '#';
    for (int w = 0; w < W; ++w) {
        for (int h = 1; h < H-1; ++h) {
            if (w % 2 == 1) S[h][w] = '#';
            else T[h][w] = '#';
        }
    }
    for (int h = 0; h < H; ++h) cout << S[h] << endl;
    cout << endl;
    for (int h = 0; h < H; ++h) cout << T[h] << endl;
    cout << endl;
}

VSCode (Visual Studio Code) のターミナルを右側に表示させる

VSCode は神!!!!!

けんちょんは、emacs から VSCode への移行を決意しました。そのキッカケとなったのは、

どーーーーーん!!!!!!!!!

f:id:drken1215:20200402151056p:plain

ターミナルを右側に表示させることができるのだ!!!
実は以前にも、emacs から VSCode への移行を試みたことがあった。だがそのときは挫折した。その理由は「ターミナルを右側に表示させる方法がわからなかったから」だ。

でも、今回できたので、VSCode への移行を決めたのだ。その方法は実は簡単だった。

terminal と書かれているところを右クリックすると、「Move Panel Right」というのが出てくる!!!!!!!!!!!
(ヴァネロピさんが教えてくれました。ありがとうございます。)

f:id:drken1215:20200402151603p:plain

これでこれからは、フォルダ機能と、コーディング画面と、ターミナルとを一元管理した環境で競プロができる!!!!!

Educational Codeforces Round 84 F. AND Segments (R2500)

実家 DP 苦手すぎる。今回は解法を簡単なものにするにあたって、「区間の左端も右端も単調増加と思って良い」というのが、割と効いてる気がする。

問題へのリンク

問題概要

長さ  N の数列であって、各要素の値が  0 以上  2^{K} 未満であるもののうち、以下の  M 個の条件を満たすものの個数を 998244353 で割ったあまりを求めよ。

  • 各条件は区間と値が指定される
  • 数列の区間の AND をとった値が、指定された値に一致する

制約

  •  1 \le N, M \le 5 \times 10^{5}
  •  1 \le K \le 30

考えたこと

すっごく典型色強めで面白そう!!!
こういうのはとりあえず区間が交差しているところについて考えないといけなくて、ひとまず

  • 区間が交差しているところの条件の値が異なっているものについては、結局どちらかだけを考えればよいか、両方とも無視してよくなる
  • 条件の値が等しいとこだけ慎重に扱えば良い

といったあたりのことが見えてきた。のだが、この時点でも複雑だな...と思っていた。もっと簡単に

  • 各桁ごとに完全に独立に考えて良い

ということを見落としていた。

各桁ごとの問題

各桁ごとに長さ  N の 0, 1 列を作る方法を考えて、それを掛け算すればよい。具体的には各区間について

  • 区間のすべての値が 1
  • 区間内に 0 が含まれる

という条件で表されることになる。前者については何も考えなくて OK。いもす法とかによって、あらかじめ 1 にしかならない場所を列挙しておくことはできる。

後者の条件は、包除原理したくなるけど、あんまり上手くいかない。でもこういうのはインライン DP でできるイメージはある。ひとまず、区間を右端順にソートしておく。

インライン DP

この手の区間をどうのこうのする DP、「ある状態がどこまで続くのかを添字に持つ」という風にすればよいイメージがある。こうしてみる

  • dp[ i ][ j ] := 数列の [0, i) について 0 か 1 を決める方法であって、区間の右端が [0, i) の内部に収まるようなものについての条件はすべて満たしていて、区間 [j, i) の値はすべて 1 で、a[ j ] の値は 0 であるようなものの個数

としてみる。DP の更新をするとき、右端を i にするような区間が複数個あるとき一瞬迷うのだけど、今回については、そのうちの左端が最も右にあるものだけを考えれば OK。その値を L[ i ] とする。なお、右端を i にするような区間が存在しないときは、便宜的に L[ i ] = -1 と考えて良さそう。このとき、

a[ i ] が 1 でなくてもよいときのみ

  • dp[ i + 1 ][ i + 1 ] += dp[ i ][ j ] ・・・ j in [0, i+1)

一般

  • dp[ i + 1 ][ j ] += dp[ i ][ j ] ・・・ j in [L[ i + 1 ] + 1, i + 1)
  • dp[ i + 1 ][ j ] = 0 ・・・ j in [0, L[ i + 1 ] + 1)

という風に更新できる。2 番目の式については in-place 化できて、3 番目の式も上手に遅延評価セグ木を使えば...という感じ。でも面倒。そこでさらに工夫する。

区間の包含関係を除去

実は今回は、3 番目の「dp の値を 0 にする」というのは不要になる。なぜなら、今回は

  • 区間 A が区間 B に含まれているような状態のとき、区間 B は無視してよい
  • したがって、区間の右端を単調増加になるように並べたとき、区間の左端も単調増加であると考えて良い

という状態になっているからだ。これを考慮すると、以下の感じで OK。計算量は  O(K(N + M) + M\log{M})

a[ i ] が 1 でなくてもよいときのみ

  • dp[ i + 1 ][ i + 1 ] += dp[ i ][ j ] ・・・ j in [L[ i ] + 1, i+1)

一般 (in-place 化で消える)

  • dp[ i + 1 ][ j ] += dp[ i ][ j ] ・・・ j in [0, i + 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; }

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() { 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 ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

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

struct Section {
    int x, y, val;
    Section(int x = 0, int y = 0, int val = 0) : x(x), y(y), val(val) {}
};
ostream& operator << (ostream &ss, Section s) {
    return ss << "(" << s.x << "," << s.y << "," << s.val << ")" << endl;
}

int N, M, K;
vector<Section> secs;

mint solve() {
    sort(secs.begin(), secs.end(), [&](Section a, Section b) {
            return a.y < b.y;
        });
    mint res = 1;
    for (int d = 0; d < K; ++d) {
        vector<int> one(N+1, 0), left(N+1, -1);
        for (auto s : secs) {
            if (s.val & (1<<d)) one[s.x]++, one[s.y]--;
            else chmax(left[s.y], s.x);
        }
        for (int i = 0; i < N; ++i) {
            one[i+1] += one[i];
            chmax(left[i+1], left[i]);
        }
        vector<mint> dp(N+1, 0), sdp(N+2, 0);
        dp[0] = 1; sdp[1] = 1;
        for (int i = 0; i < N; ++i) {
            if (one[i] == 0) dp[i+1] = sdp[i+1] - sdp[left[i]+1];
            sdp[i+2] = sdp[i+1] + dp[i+1];
        }
        mint tmp = sdp[N+1] - sdp[left[N]+1];
        res *= tmp;
    }
    return res;
}

int main() {
    while (scanf("%d %d %d", &N, &K, &M) != EOF) {
        secs.resize(M);
        for (int i = 0; i < M; ++i) {
            scanf("%d %d %d", &secs[i].x, &secs[i].y, &secs[i].val);
            --secs[i].x;
        }
        printf("%lld\n", solve().val);
    }
}

AtCoder ABC 159 D - Banned K (400 点)

差分更新系の教育的問題かな

問題へのリンク

問題概要

長さ  N の数列が与えらえる。各 index k に対して、

  • 数列から k 番目の要素を除いたものについて
  • その中から異なる 2 つの要素を選ぶ方法であって (順番は問わず)
  • その 2 つの要素の選び方が等しい

という選び方が何通りあるのかを求めよ。

制約

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

考えたこと

愚直に毎回の数列について計算したのでは  O(N^{2}) の計算量を要してしまう。今回のような、各  k について、それを除いたものについて考えるタイプの問題では

  • まず全体の数列についての答えを求めておいて
  • 各要素を取り除くことによる「影響」を計算し、
  • その影響分を引く

という風にするのが定石。その影響を計算することをしばしば「差分更新」と呼んだりする。つまり、差分だけ高速に計算してしまおうという発想だ。

全体

何にしてもまずは、全体の数列について答えを求める必要がある。でもこれは簡単だ。

  • nums[ v ] := 値 v が何個あるか

という配列を用意してあげて、各値 v について、

  •  n = nums[ v ] として
  •  \frac{n(n-1)}{2} を加算する

という風にして求めることができる。

差分更新

ここまでわかれば差分計算も簡単だ。値 v を除くとき、影響があるのは nums[ v ] の部分だけだ。よって、その部分についてのみ、before / after を計算して補正すればよい。具体的には、

  •  n = nums[ v ] として
  • before:  \frac{n(n-1)}{2}
  • after:  \frac{(n-1)(n-2)}{2}

という風になる。答えは、(全体) - before + after となる。計算量は全体で  O(N) でできる。

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

int N;
vector<long long> a;

void solve() {
    map<long long, long long> ma;
    for (int i = 0; i < N; ++i) ma[a[i]]++;
    long long res = 0;
    for (auto it : ma) res += it.second * (it.second - 1) / 2;
    for (int i = 0; i < N; ++i) {
        long long val = ma[a[i]];
        long long before = val * (val - 1) / 2;
        long long after = (val - 1) * (val - 2) / 2;
        cout << res + after - before << endl;
    }
}

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