2024-11-24

AtCoder ABC 381 F - 1122 Subsequence (2D, 青色, 525 点)

$A_{i} \le 20$ という制約がいかにも怪しい！

問題へのリンク

問題概要

1 以上 20 以下の整数からなる、長さ $N$ の数列 $A_{1}, A_{2}, \dots, A_{N}$ が与えられる。

この数列の部分列 (連続でなくてよい) であって、任意の整数について、その部分列に含まれる個数が 0 個または 2 個であるものを考える。

そのような部分列に含まれる要素の個数の最大値を求めよ。

制約

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

考えたこと

「部分列」とあるので、最初は部分列 DP をするのかと考えた。が、良い感じの計算量になる方法は浮かばなかった。というのも「部分列 DP を更新する際に、どの値は既に使ったのか」を管理したいのだ。bit DP ができるなら、したい。

そこで、代わりに次の DP を考えることにした。

dp[S]： $A_{1}, A_{2}, \dots, A_{j}$ から、「整数値集合 $S$ に含まれる整数がちょうど 2 個ずつ含まれる」ような部分列をとれるような $j$ の最小値（とれない場合は $N+1$ ）

この DP を更新するために、以下のデータをあらかじめ用意しておく。これは、 $M = \max(A_{1}, A_{2}, \dots, A_{N})$ として、 $O(MN)$ の計算量で求められる。

nex[i][c]： $A_{j} = c$ となるような $j$ ( $\ge i$ ) の最小値

また、DP の更新に要する計算量は $O(2^{M} M)$ となる。以上をまとめて、計算量は $O(M(N + 2^{M}))$ と評価できる。

コード

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

int main() {
    const int MAX = 20;
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i], A[i]--;

    // nexind[i][c] := 各文字 c について A[j] = c なる j (>= i) の最小値
    vector nexind(N+1, vector(MAX, N));
    for (int i = N-1; i >= 0; i--) {
        for (int j = 0; j < MAX; j++) {
            nexind[i][j] = nexind[i+1][j];
        }
        nexind[i][A[i]] = i;
    }

    // bitDP
    int res = 0;
    const int INF = 1 << 29;
    vector<int> dp(1 << MAX, INF);
    dp[0] = 0;
    for (int bit = 0; bit < (1 << MAX); bit++) {
        if (dp[bit] == INF) continue;
        res = max(res, __builtin_popcount(bit) * 2);
        for (int v = 0; v < MAX; v++) {
            if (bit & (1 << v)) continue;
            int bit2 = bit | (1 << v);
            int nex = nexind[dp[bit]][v];
            if (nex >= N) continue;
            nex = nexind[nex+1][v];
            if (nex >= N) continue;
            dp[bit2] = min(dp[bit2], nex+1);
        }
    }
    cout << res << endl;
}

2024-11-23

競プロ典型 90 問 027 - Sign Up Requests（5Q, ★2）

AtCoder 競プロ典型90問競プロ典型90問とその類題競プロ典型90問難易度2 setやmap:検索や削除が速いこと連想配列(setやmap) 計算量改善:setやmapの活用クエリ処理問題各kに対してそのまま覚えたい典型問題

集合型を学ぼう！

問題へのリンク

問題概要

$N$ 個の文字列 $S_{1}, S_{2}, \dots, S_{N}$ がこの順に与えられる。

初出の文字列に対して、その添字を出力せよ。

制約

$1 \le N \le 10^{15}$
$1 \le |S_{i}| \le 15$

解説

0-indexed で考えます。つまり、文字列を $S_{0}, S_{1}, \dots, S_{N-1}$ とします（出力するときには 1 を足します）。

まずは計算量のことを考えずに解いてみましょう。一番自然な解法は次のように、各 $i = 0, 1, \dots, N-1$ に対して、 $S_{i}$ がそれ以前に登場しているかを判定する方法でしょう。

for (int i = 0; i < N; i++) {
    bool already = false;
    for (int j = 0; j < i; j++) {
        if (S[j] == S[i]) already = true;
    }

    if (!already) {
        // 初出だったら index を出力する
        cout << i+1 << endl;
    }
}

このコードでサンプルは通ります。しかし、提出すると TLE となるはずです。それは、このコードの計算量が $O(N^{2})$ であるためです。なお、計算量について知らない方は、次の記事を読んでみてください。

qiita.com

それでは、このコードを高速化しましょう。高速化できる余地があるとしたら、

「 $S_{i}$ がすでに登場しているかどうかを判定する」

という部分ではないでしょうか。ここで、集合型の登場です。C++ の set 型は次のクエリをこなせるデータ構造です（変数名を se とします）。

クエリ	詳細	書き方	計算量
挿入	要素 $v$ をデータ構造に挿入する（すでにあれば何もしない）	`se.insert(v)`	$O(\log N)$
削除	要素 $v$ をデータ構造から削除する（すでになければ何もしない）	`se.erase(v)`	$O(\log N)$
検索	要素 $v$ がデータ構造に含まれるかどうかを判定する	`if (se.count(v))`	$O(\log N)$

なお、ここでの計算量は、データ構造のサイズを $N$ とした場合のものです。

このデータ構造のすごいところは、データ構造内に要素 $v$ が含まれるかどうかを $O(\log N)$ の計算量で判定できることです。この set 型を用いて、上記のコードは次のように書き直せます。

for (int i = 0; i < N; i++) {
    if (!se.count(S[i])) {
        // 初出だったら index を出力する
        cout << i+1 << endl;
    }

    // S[i] をデータ構造に挿入する
    se.insert(S[i]);
}

挿入や検索に要する計算量は $O(\log N)$ ですので、上記の解法全体の計算量は $O(N \log N)$ となります。これであれば、十分間に合います。

コード

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

int main() {
    int N;
    string S;
    set<string> se;

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> S;

        if (!se.count(S)) {
            // 初出だったら index を出力する
            cout << i+1 << endl;
        } 
        se.insert(S);
    }
}

2024-11-23

第 4 回 PAST F - 構文解析 (4Q)

AtCoder PAST過去問 NoviSteps4Q 連想配列(setやmap) ソートソート:ペア値 K番目を求める集計処理

集計処理した上で、再度大きい順にソートする問題

問題へのリンク

問題概要

$N$ 個の文字列 $S_{1}, S_{2}, \dots, S_{N}$ が与えられる。

この列に一回以上出現する単語を、その出現回数の多い順に並べたとき $K$ 番目の単語を出力せよ（一意に決まらない場合は "ambiguous" と出力せよ）。

制約

$1 \le N \le 10^{5}$
$1 \le |S_{i}| \le 10$

考えたこと

まずは集計処理しよう！　すなわち、次のような連想配列 (C++ ならば map<string, int> 型を求めよう。

nums[str]： $N$ 個の文字列の中に、文字列 str が何個あるか

これを求めたあとは、各文字列ごとに再び (個数, 文字列) のペアを配列に格納していこう。これを大きい順にソートして $K$ 番目を求めれば良い。

ただし、タイがある場合は "AMBIGUOUS" と返す必要がある。ここでは、次のように判定した。

$K$ 番目に大きい頻度と、 $K-1$ 番目に大きい頻度が一致する ( $K-1 \ge 0$ の場合)
$K$ 番目に大きい頻度と、 $K+1$ 番目に大きい頻度が一致する ( $K+1 \gt 種類数$ の場合)

については、 "AMBIGUOUS" と返せばよい。

全体として、文字列の長さの最大値を $L$ として、計算量は $O(LN \log N)$ と評価できる。

コード

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

int main() {
    int N, K;
    cin >> N >> K, K--;
    string S;
    map<string, int> nums;
    for (int i = 0; i < N; i++) {
        cin >> S;
        nums[S]++;
    }

    vector<pair<int, string>> v;
    for (auto [str, num] : nums) v.emplace_back(num, str);
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());

    if (K > 0 && v[K].first == v[K-1].first) 
        cout << "AMBIGUOUS" << endl;
    else if (K+1 < v.size() && v[K].first == v[K+1].first)
        cout << "AMBIGUOUS" << endl;
    else
        cout << v[K].second << endl;
}

2024-11-23

AtCoder ABC 146 E - Rem of Sum is Num (1D, 青色, 500 点)

AtCoder AtCoder500点 ABC-E 青色diff NoviSteps1D 式変形 f(i,j)をiとjとに分離する条件の言い換え Zero-Sum Ranges 解空間:O(N^2)個の区間解空間:O(N^2)通りの選択肢区間スライド系問題区間

ちょっと工夫が必要な感じ

問題へのリンク

問題概要

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

数列の区間であって、総和を $K$ で割った余りと、区間内に含まれる要素の個数とが等しいものの個数を求めよ。

制約

$1 \le N \le 2 \times 10^{5}$
$1 \le K, A_{i} \le 10^{9}$

考えたこと

結構ややこしい。落ち着いて条件を整理しよう！！

まず、0-indexed で考えることにして、数列 $A$ の累積和を $S_{0}, S_{1}, \dots, S_{N}$ としよう。このとき、問題は次のように再解釈できる。

長さ $N+1$ の数列 $S_{0}, S_{1}, \dots, S_{N}$ が与えられる。

$0 \le i \lt j \le N$
$S_{j} - S_{i}$ を $K$ で割った余りが $j - i$ に一致する

という条件を満たす $(i, j)$ の組の個数を求めよ。

ここで、もし $j - i \lt K$ であることが保証されるならば、話は早くて、

$S_{j} - S_{i} \equiv j - i \pmod K$
⇔ $S_{i} - i \equiv S_{j} - j \pmod K$

を満たすような $(i, j)$ を求めればよくて、map を用いて自然に解ける。

そして、 $j - i \ge K$ となることがあり得たとしても、少し考えてみれば、結局、次の条件を満たす $(i, j)$ の組の個数を求めればよいことがわかる。

$i \lt j$
$j - i \lt K$
$S_{i} - i \equiv S_{j} - j \pmod K$

これを求めるためには、 $j = 0, 1, \dots, N$ に対して、

$j - K \lt i \gt \lt j$
$S_{i} - i \equiv S_{j} - j \pmod K$

を満たす $i$ の個数を求め、その値を足していけばよい。この操作は、やはり map を用いてできる。計算量は $O(N \log N)$ と評価できる。

コード

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

// Sj - Si ≡ j - i mod K かつ j - i < K
// Si - i ≡ Sj - j mod K かつ j - i < K
int main() {
    long long N, K;
    cin >> N >> K;
    vector<long long> A(N), S(N+1, 0);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        S[i+1] = S[i] + A[i];
    }

    long long res = 0;
    map<long long, long long> nums;
    for (int j = 0; j <= N; j++) {
        long long rj = ((S[j] - j) % K + K) % K;
        res += nums[rj];

        // S[j] を追加
        nums[rj]++;

        // j - i = K となる i を削除
        int i = j - (K - 1);
        if (i >= 0) {   
            long long ri = ((S[i] - i) % K + K) % K;
            nums[ri]--;
            if (nums[ri] == 0) nums.erase(ri);
        }
    }
    cout << res << endl;
}

を満たす $i$ の個数を

2024-11-23

AtCoder ABC 166 E - This Message Will Self-Destruct in 5s (1Q, 緑色, 500 点)

AtCoder AtCoder500点 ABC-E NoviSteps1Q 緑色diff 数列解空間:O(N^2)個の区間解空間:O(N^2)通りの選択肢 setやmap:検索や削除が速いこと計算量改善:setやmapの活用連想配列(setやmap) 式変形 f(i,j)をiとjとに分離する条件の言い換え

上手に式変形しよう！

問題へのリンク

問題概要

正の整数からなるサイズ $N$ の数列 $A_{1}, A_{2}, \dots, A_{N}$ が与えられる。次の条件を満たす組 $(i, j)$ の個数を求めよ。

$0 \le i \lt j \lt N$
$A_{i} + A_{j} = j - i$

制約

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

考えたこと

条件が不思議だ。普通は $i, j$ よりも $A_{i}, A_{j}$ の方が大きいことが多いのに、 $A_{i} + A_{j} = j - i$ となる条件を問うとは。

さて、この手の数式を見たときに考えるべきことは「左辺は $i$ だけ、右辺は $j$ だけというように式変形する」ということだ。次のようになる。

$A_{i} = A_{j} = j - i$
⇔ $A_{i} + i = j - A_{i}$

この式が示すことは、次のようなことだ。

各 $j = 0, 1, \dots, N-1$ に対して、 $B = j - A_{i}$ としたとき、 $A_{i} = B$ を満たす $i$ (\lt j) の個数を合算していけばよい

この処理は map などを用いてできる。計算量は $O(N \log N)$ となる。

コード

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

// Ai + Aj = j - i
// Ai + i = j - Aj
int main() {
    int N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    map<long long, long long> Aplus;
    for (int i = 0; i < N; i++) Aplus[A[i] + i]++;
    long long res = 0;
    for (int j = 0; j < N; j++) {
        res += Aplus[j - A[j]];
    }
    cout << res << endl;
}

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

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

AtCoder ABC 381 F - 1122 Subsequence (2D, 青色, 525 点)

問題概要

制約

考えたこと

コード

競プロ典型 90 問 027 - Sign Up Requests（5Q, ★2）

問題概要

制約

解説

コード

第 4 回 PAST F - 構文解析 (4Q)

問題概要

制約

考えたこと

コード

AtCoder ABC 146 E - Rem of Sum is Num (1D, 青色, 500 点)

問題概要

制約

考えたこと

コード

AtCoder ABC 166 E - This Message Will Self-Destruct in 5s (1Q, 緑色, 500 点)

問題概要

制約

考えたこと

コード