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

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

JOIG 2024 A - 三連続 (難易度 2)

for 文の練習問題!

問題概要

o と x からなる長さ  N の文字列  S が与えられる。

 S の中に o が 3 つ連続している箇所があれば "Yes" を出力し、そうでなければ "No" を出力せよ。

制約

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

考えたこと

for 文を用いて判定しよう。具体的には、各 i について

  • S[i] == 'o'
  • S[i+1] == 'o'
  • S[i+2] == 'o'

が成り立つかどうかを判定していって、一箇所でも成り立てば "Yes" を出力すればよい。

コード

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

int main() {
    int N;
    string S;
    cin >> N >> S;
    bool res = false;
    for (int i = 0; i + 2 < N; ++i) {
        if (S[i] == 'o' && S[i+1] == 'o' && S[i+2] == 'o') res = true;
    }
    cout << (res ? "Yes" : "No") << endl;
}

JOIG 2024 E - 名前 (難易度 9)

いかにも JOI にありがちな添字の持ち方をする DP!

問題概要

英小文字と英大文字からなる長さ  N の文字列  S と、長さ  M の文字列  T が与えられる。また 0 以上 3 以下の整数  K が与えられる。

次の条件を満たす文字列  X の長さの最小値を求めよ。

  •  X は、英小文字と英大文字からなる
  •  X は、文字列  S を部分文字列 (連続でなくてよい) とする
  •  X は、文字列  T を部分文字列 (連続でなくてよい) とする
  •  X に含まれる同じ文字の間には、 K 個以上の別の文字がある

制約

  •  1 \le N, M \le 500
  •  0 \le K \le 3

考えたこと

いかにも DP っぽい。基本的には次のような DP を考えたくなる。

dp[i][j] ← 文字列  S の先頭から  i 文字分を部分列にもち、文字列  T の先頭から  j 文字分を部分列にもつような文字列  X の長さの最小値

しかし、これだと「同じ文字の間には、 K 個以上の別の文字がある」という条件を満たせるかどうかが分からない。そこで、文字列  X の末尾  K 文字分の情報を配列 dp に持たせることにしよう。

さらに、その末尾  K 文字分の情報について、各文字の情報としては、アルファベット文字 52 通りではなく、

  •  S から取って来たものであるか
  •  T から取って来たものであるか

のみに着目した 4 通りで十分である。そこで、次の配列 dp を考える ( K \le 3 より、付加情報は 3 次元分を持っている)。


dp[i][j][x][y][z] ← 文字列  S の先頭から  i 文字分を部分列にもち、文字列  T の先頭から  j 文字分を部分列にもつような文字列  X のうち、次の条件を満たす文字列の長さの最小値

  •  X の末尾の文字について
    •  x を二進法で表したときの  2^{0} の位の値が 1 のときには、 S から取って来た文字である
    •  x を二進法で表したときの  2^{1} の位の値が 1 のときには、 T から取って来た文字である
  •  X の末尾から 2 番目の文字について
    •  y を二進法で表したときの  2^{0} の位の値が 1 のときには、 S から取って来た文字である
    •  y を二進法で表したときの  2^{1} の位の値が 1 のときには、 T から取って来た文字である
  •  X の末尾から 3 番目の文字について
    •  z を二進法で表したときの  2^{0} の位の値が 1 のときには、 S から取って来た文字である
    •  z を二進法で表したときの  2^{1} の位の値が 1 のときには、 T から取って来た文字である

なお、この配列 DP を更新しようとするとき、ループが生じることがある。よって、for 文を用いるのではなく、幅優先探索の要領で更新していくようにしよう。

計算量は  O(NM 4^{K}) となる。

コード

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

const int MAX = 510;
int dp[MAX][MAX][4][4][4];

int main() {
    int N, M, K;
    string S, T;
    cin >> N >> M >> K >> S >> T;
    
    // S から i 文字、T から j 文字とっていて、最後 3 文字のステータスが sts である状態で
    // 文字 c をくっつけられるか
    auto check = [&](char c, int i, int j, int x, int y, int z) -> bool {
        if (c == '?') return true;
        int pi = i-1, pj = j-1;
        vector<int> vec({x, y, z});
        for (int k = 0; k < K; ++k) {
            if (vec[k] & (1 << 0)) if (pi >= 0 && c == S[pi--]) return false;
            if (vec[k] & (1 << 1)) if (pj >= 0 && c == T[pj--]) return false;
        }
        return true;
    };
    
    // i, j, 最後 k, その前 l, さらにその前 m
    memset(dp, -1, sizeof(dp));
    
    // 0: ?, 1: from S, 2: from T
    int res = 0;
    dp[0][0][0][0][0] = 0;
    queue<array<int, 5>> que;
    que.push({0, 0, 0, 0, 0});
    while (!que.empty()) {
        auto [i, j, x, y, z] = que.front();
        que.pop();
        
        if (i == N && j == M) {
            res = dp[i][j][x][y][z];
            break;
        }
        
        // 次の文字の候補
        vector<char> nc({'?'});
        if (i < N) nc.push_back(S[i]);
        if (j < M) nc.push_back(T[j]);
        
        // 文字 c を新たに加える
        for (auto c : nc) {
            if (check(c, i, j, x, y, z)) {
                int ni = i, nj = j, nx = 0;
                if (ni < N && S[ni] == c) {
                    ++ni;
                    nx |= 1 << 0;
                }
                if (nj < M && T[nj] == c) {
                    ++nj;
                    nx |= 1 << 1;
                }
                if (dp[ni][nj][nx][x][y] == -1) {
                    dp[ni][nj][nx][x][y] = dp[i][j][x][y][z] + 1;
                    que.push({ni, nj, nx, x, y});
                }
            }
        }
    }
    cout << res << endl;
}

JOIG 2024 C - 座席 2 (難易度 6)

色んな解法が考えられそうな問題で、ドツボにハマりやすくて危険な問題だったと思う。落ち着いて整理してシンプルに考える力が問われる。実は、二分探索などは必要ない問題である。

問題概要

 N 人の選手  0, 1, \dots, N-1 がいる。選手  i の出身国は  C_{i} であり、座標  X_{i} の位置に座っている。

各選手  i に対して、

  • その選手  i とは出身国が異なる選手のうち、
  • その選手  i との距離が最も近い選手について、

その距離の最小値を求めよ。

制約

  •  2 \le N \le 3 \times 10^{5}
  •  1 \le C_{i}, X_{i} \le 10^{9}

考えたこと

この問題と似ている問題で、よく知られているのは次のような問題だと思われる。

drken1215.hatenablog.com

つまり、一直線上に  N 点が与えられて、 Q 回のクエリが投げられて、各クエリについて座標値が与えられるので、その位置から最も近い点を求めるというものである。この問題は二分探索 (lower_bound()) をすれば解ける典型的な問題であった。

今回の問題も、この過去の問題と同様に、二分探索による解法を考えたくなる。しかし、大きく異なる点が 2 つある。

  • 選手に「色」のような属性があって、同じ色の選手は除外しなければならない
  • この問題は、クエリ処理問題ではない。つまり、選手のいる座標値以外の座標については考える必要がない

特に後者は見落としがちだと思う。後者に着目して、シンプルに思考する力が問われている。

選手を座標順に並べる

今回、一旦選手を座標順に並べてみよう。具体例として、選手を (座標, 出身国) と表したとき、

(10, 3), (11, 1), (15, 1), (21, 1), (29, 2), (31, 2), (41, 3)

というデータを考えてみる。このデータに対して出身国だけを抽出すると、

3, 1, 1, 1, 2, 2, 3

のようになる。このとき、もし、各要素に対して、

  • left[i] i 番目よりも左の要素であって、出身国が異なるような要素の添字の最大値 (存在しない場合は -1)
  • right[i] i 番目よりも右の要素であって、出身国が異なるような要素の添字の最小値 (存在しない場合は N)

を求めることができれば、この問題は解ける。各要素  i に対して「i 番目の要素と left[i] 番目の要素の座標値の差」と「i 番目の要素と right[i] 番目の要素の座標値の差」の最小値を答えればよい。

そして、leftright の値も、for 文を用いて容易に求められる。たとえば left は次のように求められる。

vector<int> left(N, -1), right(N, N);
for (int i = 1; i < N; ++i) {
    if (v[i].col == v[i-1].col) left[i] = left[i-1];
    else left[i] = i-1;
}

計算量

最初にすべての選手を座標順にソートする部分が最も計算量を要して、 O(N \log N) の計算量となる。

その後の left, right を求めたり、それを用いて答えを求める部分は  O(N) の計算量で実行できる。

コード

#include <bits/stdc++.h>
using namespace std;
void chmin(int &a, int b) { if (a > b) a = b; }

// 選手の情報 (もとの添字, 国を表す数値, 座標)
struct Student {
    int id;
    long long col;
    long long pos;
    Student(int i = 0, long long c = 0, long long p = 0) : id(i), col(c), pos(p) {}
};

const int INF = 1LL<<30;
int main() {
    int N;
    cin >> N;
    
    // 選手を座標順にソートする (選手の元の添字も記録しておく)
    vector<Student> v(N);
    for (int i = 0; i < N; ++i) {
        int c, x;
        cin >> c >> x;
        v[i] = Student(i, c, x);
    }
    sort(v.begin(), v.end(), [&](Student a, Student b){return a.pos < b.pos;});

    // 座標順に、各生徒から見て、前後に見たときの最初の「色が違う選手の位置」を求めていく
    vector<int> left(N, -1), right(N, N);
    for (int i = 1; i < N; ++i) {
        if (v[i].col == v[i-1].col) left[i] = left[i-1];
        else left[i] = i-1;
    }
    for (int i = N-2; i >= 0; --i) {
        if (v[i].col == v[i+1].col) right[i] = right[i+1];
        else right[i] = i+1;
    }
        
    // 答えを集計する
    vector<int> res(N, INF);
    for (int i = 0; i < N; ++i) {
        if (right[i] < N) chmin(res[v[i].id], v[right[i]].pos - v[i].pos);
        if (left[i] >= 0) chmin(res[v[i].id], v[i].pos - v[left[i]].pos);
    }
    for (int i = 0; i < N; ++i) cout << res[i] << endl;
}

AtCoder ARC 167 E - One Square in a Triangle (銅色, 800 点)

天才構築ゲー。これ完全自力で一発 AC できて嬉しかった!!

問題概要

正の整数  S が与えられる。次の条件を満たす三角形が存在するかどうかを判定し、存在すれ場合は 1 つ求めよ。

  • 頂点がすべて格子点であり、座標値は  0 以上  10^{8} 以下である
  • すべての頂点が格子点である面積 1 の正方形のうち、三角形の内部 (周上及び頂点を含む) に全体が含まれているものはちょうど 1 つある

(マルチテストケース)

制約

  •  1 \le S \le 10^{8}

考えたこと

 S がある程度大きければ、ぶっちゃけ常に作れるのでは......と予想がたった。とりあえず、三角形の 1 つの頂点を原点に固定して考えることにした。

最初に考えたのは、

  •  (x, x+1) (x+1, x) で、 S = 2x + 1 になる (しかし、内部に正方形が含まれない)
  • しかし、 (px, p(x+1)) (x+1, x) ( p \ge 2) で、 S = p(2x + 1) になる (これは内部に正方形を 1 個しか含まない)

ということだった。この時点で、 S 6 以上の合成数の場合はできた。

次にこの議論を膨らませることで、


  •  (2, 0) (p, p) ( p \ge 2) で、 S = 2p になる
  •  (3, 1) (p, p+1) ( p \ge 3) で、 S = 2p+3 になる

ということがわかった。これらはいずれも内部に 1 個しか含まない。よって、 4 以上の偶数と、 9 以上の奇数はできた!!!

残り

この時点で、残ったのは

 S = 1, 2, 3, 5, 7

のみとなった。これらはおそらくダメだとなった。たとえば  S = 7 のとき、 7 は素数なので三角形の周上の格子点は頂点のみであるから、ピックの定理から、三角形内部の格子点の個数は 3 個となる。これと頂点とを合わせて正方形になるかというと難しそうであった。

コード

以上を実装した。とても短いコードになった。計算量は  O(1) である。

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

void solve() {
    long long S;
    cin >> S;
    if (S <= 3 || S == 5 || S == 7) cout << "No" << endl;
    else if (S % 2 == 0) {
        cout << "Yes" << endl;
        cout << "0 0 2 0 " << S / 2 << " " << S / 2 << endl;
    } else {
        cout << "Yes" << endl;
        cout << "0 0 3 1 " << (S - 3) / 2 << " " << (S - 1) / 2 << endl;
    }
}

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

AtCoder ARC 171 D - Rolling Hash (黄色, 600 点)

コンテスト後に解いた。こっちの方が解きやすかった。

問題概要

制約

  •  2 \le P \le 10^{9}
  •  1 \le N \le 16

考えたこと

最初は  B の指数を気にするのかな......などと考えていたが、考えていくうちに  B の値など、ただの飾りであることがわかってきた。

まず、問題の条件を言い換える。 B' \equiv B^{-1} として、数列  A に対して  C_{i} = A_{i} B'^{i} とする。さらに  C の累積和を  S とする。このとき、問題の条件は、各  (L_{i}, R_{i}) に対して

 S_{R_{i}+1} \not\equiv S_{L_{i}} \pmod{P}

であることと等価であることがわかる。mod  P において、 B を自由にかけたり割ったりしても同値性を保てるためだ。

特に、 P \gt N のときは、かならず Yes になる。たとえばすべての区間について条件が課されていたとしても、

  •  S_{0} \equiv 0
  •  S_{1} \equiv 1
  •  S_{2} \equiv 2
  •  \dots
  •  S_{N} \equiv N

とすればよいためだ。これを満たすような数列  A は容易に逆算できる。

一般の場合

一般の場合であっても、数列  S と数列  A とが一対一に対応することには変わりない。よって、次の条件を満たすように  S_{0}, S_{1}, \dots, S_{N} の各値を割り当てることが可能かどうかを判定する問題になったと言える。


  • 数列  S_{i} の各値を  0 以上  P-1 以下の値とする
  • ただし、 S_{0} \equiv 0 とする
  •  (L_{i}, R_{i}) に対して  S_{R_{i}+1} \not\equiv S_{L_{i}} となるようにする

これはよく考えると、彩色問題である。頂点  0, 1, \dots, N からなる、 M 本の辺  (L_{i}, R_{i} + 1) を結んだグラフの彩色数を求めて、それが  P 以下であるかどうかを判定すればよいのだ。

彩色数は  O(2^{N}N) の計算量で求められるアルゴリズムがある。次の記事で解説している。

drken1215.hatenablog.com

コード

//
// 彩色数を求める O(N2^N) のアルゴリズム
//
// cf.
//   https://drken1215.hatenablog.com/entry/2019/01/16/030000
//
// verified
//   ARC 171 D - Rolling Hash
//     https://atcoder.jp/contests/arc171/tasks/arc171_d
//
//   AOJ 2136 Webby Subway
//     http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2136
//


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


// 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();
    }
};

int chromatic_number(const vector<vector<int>> &G) {
    const int MOD = 998244353;
    using mint = Fp<MOD>;
    
    int n = (int)G.size();
    vector<int> neighbor(n, 0);
    for (int i = 0; i < n; ++i) {
        int S = (1<<i);
        for (int j = 0; j < n; ++j) if (G[i][j]) S |= (1<<j);
        neighbor[i] = S;
    }
    
    // I[S] := #. of inndepndet subset of S
    vector<int> I(1<<n);
    I[0] = 1;
    for (int S = 1; S < (1<<n); ++S) {
        int v = __builtin_ctz(S);
        I[S] = I[S & ~(1<<v)] + I[S & ~neighbor[v]];
    }
    int low = 0, high = n;
    while (high - low > 1) {
        int mid = (low + high) >> 1;
        
        // g[S] := #. of "k independent sets" which cover S just
        // f[S] := #. of "k independent sets" which consist of subseta of S
        // then
        //   f[S] = sum_{T in S} g(T)
        //   g[S] = sum_{T in S} (-1)^(|S|-|T|)f[T]
        mint g = 0;
        for (int S = 0; S < (1<<n); ++S) {
            if ((n - __builtin_popcount(S)) & 1) g -= mint(I[S]).pow(mid);
            else g += mint(I[S]).pow(mid);
        }
        if (g != 0) high = mid;
        else low = mid;
    }
    return high;
}

void ARC_171_D() {
    long long P, B, N, M;
    cin >> P >> B >> N >> M;
    
    vector<vector<int>> G(N+1, vector<int>(N+1, 0));
    for (int i = 0; i < M; ++i) {
        int l, r;
        cin >> l >> r;
        --l;
        G[l][r] = G[r][l] = 1;
    }
    if (chromatic_number(G) <= P) cout << "Yes" << endl;
    else cout << "No" << endl;
}

int main() {
    ARC_171_D();
}