CD問題過去問解き記録（三井住友PC2019_D、ABC128_C）

今日も今日とてAtCoderの過去問解き。本日はC問題1問、D問題1問。
問題のチョイスはこちらの1-6-4より。

三井住友信託銀行プログラミングコンテスト2019 D問題

自分はD問題を解いたことがなく、ほぼ問題を見ようとしたこともないため、「茶色になるためには」の記事内でこの問題が紹介されてて少しビビってしまったが、とはいえ機械的に取り組むことに。
D問題はC問題に比べて必要となる知識量が多そうというイメージではあるが、中でには全探索で解ける問題もあるんだね。

問題はこちら。
atcoder.jp

ラッキーナンバーNから任意の3文字を取り出し、3桁の数字を作るという問題。
初動でまず思いついたのは「可能な組み合わせを全探索する」方法。しかしそれではO((3×10^4)^3) = O(10^13) の計算量になり、余裕のTLEであることが分かる。
どのように工夫して計算量を減らすか。問題紹介の文脈から全探索で解けることは分かっているのは何かズルい気もしつつ考える。

次に思いついたのは「重複する数字が見つかったら、以降の探索を打ち切る」という方式だ。
例えば、作成される3桁の数字の1文字目としてあり得るのは、0-9の10通りのみ。
従って1文字目として探索されたことがある数字を記録しておけば、計算量はO(10×(3×10^4)^2)に減らすことができる。
さらに、2文字目についても同様の操作を行えば、更にO(10×10×3×10^4) = O(10^6)まで減らすことができ、これはTLEを防ぐことができるラインだ。

後は、この方針通りに実装するのみ。
道中、set周りのメソッド（挿入や検索）が曖昧だったので調べたり、charとstringの扱いの違いを理解していなかったりで時間を喰われ、最終的にACを出すまでに掛かった時間は約49分。
最終的なコードはこちら。

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;

int main() {
    int N;
    string S;

    cin >> N;
    cin >> S;
    set<string> keys;
    set<char> c1s;
    rep(i, N-2) {
        char c1 = S[i];
        if (c1s.find(c1) != c1s.end()) continue;
        c1s.insert(c1);
        string S2 = S.substr(i + 1);
        set<char> c2s;
        rep(k, N-2-i) {
            char c2 = S2[k];
            if (c2s.find(c2) != c2s.end()) continue;
            c2s.insert(c2);
            string S3 = S2.substr(k+1);
            set<char> c3s;
            rep(l, N-2-i-k) {
                char c3 = S3[l];
                if (c3s.find(c3) != c3s.end()) continue;
                string key = string(1, c1)+string(1, c2)+string(1, c3);
                keys.insert(key);
            }
        }
    }
    cout << keys.size() << endl;
    return 0;
}

まあ、現状の自分のレートからすると「C問題をACすること」が第一目標なので、1時間以内に解き切れればセーフである。

続いて2問目。

ABC128 C問題

atcoder.jp

問題が複雑で条件の理解に結構苦労した。
ただ、要は取りうる全てのスイッチのon/offの組み合わせに対し、愚直に全探索して「電球が全て点灯するパターン」をカウントしていけばいいだけではある。

計算量としてはO(2^10)より少し多いくらいの計算量であるから、TLEを気にする必要は無し。
実装的な部分で「スイッチのon/offの全パターンをどう表現すればいいのか」に悩んだ。まさかrep(i, 2)をN回繰り返すような愚直なプログラムは書きたくない…。

ChatGPTに聞いてみると、「bitシフト演算」というものを使うと良いらしい。例えば、2^Nまでのループを回したい場合は、

for (int bit = 0; bit < (1<<N); ++bit) {
}

のように、bitシフト演算を使って表現することができる。これは2^Nと同じ計算をしているらしい。
また、これを各スイッチのon/offの組み合わせに変換する際は、

vector<bool> switches(N);
rep(i, N) {
    switches[i] = bit & (1 << i);
}

のようにする。
これは、まず1にiビットシフト演算を適用することで「iビット目のみが1で他が全て0」であるような整数を作っている。
次に、その整数とbit（これはforで回しているローカル変数）をAND演算し、「bitのiビット目が1である場合true、0である場合false」を返すような操作を実現することができる。
調べながらやってたけど、こんな風にできるんだね。

最終的に作成したコードは以下。

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <vector>
#include <bitset>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> K(M), P(M);
    vector<vector<int>> S(M);
    int all_swit_light = 0;
    rep(i, M) {
        cin >> K[i];
        S[i] = vector<int>(K[i], 0);
        rep(j, K[i]) cin >> S[i][j];
    }
    rep(i, M) cin >> P[i];
    vector<bool> switches(N);
    for (int bit = 0; bit < (1<<N); ++bit) {
        rep(i, N) {
            switches[i] = bit & (1 << i);
        }
        int flag = 1;
        rep(i, M) {
            int sum_swit = 0;
            rep(j, K[i]) {
                if (switches[S[i][j]-1]) sum_swit += 1;
            }
            int on_swit_per2 = sum_swit % 2;
            if (on_swit_per2 != P[i]) {
                flag = 0;
            } else {
            }
        }
        if (flag==1) {
            all_swit_light += 1;
        }
    }
    cout << all_swit_light << endl;
    return 0;
}

掛かった時間は1:04:48:34。
問題の条件が複雑で、入力形式も2次元ベクトルの取り扱いとかに少し苦戦し、実装面でも細かいミスを逐一修正しながらやって1時間を超えてしまった。
しかし、逆に言えば1時間を掛けて一つの作品を作り上げたと言うこともでき、ACの文字を見たときは少し感動というか達成感があった。
難しいと感じる問題ほど解けた時は達成感を感じるものだ。

本日は以上。
いよいよ明後日が復帰後2回目のABCなので、それに向けて万全の準備をしていきたいところではある。