競プロ日記#25/09/04

競技プログラミングの鉄則

A19 - Knapsack 1

• A18（鉄則本でいうと4章の3項）の「二次元DPの部分和問題」の応用だなと思った
• dp[N][W]が最大値とは限らない（この問題でいうと「重さを最大化する＝価値も最大になる」とは限らないため）に気を付ける

int main() {
    long long N,W,w[109],v[109];
    long long dp[109][100009];
    cin >> N >> W;
    for (long long i = 1;i <= N;i++){
        cin >> w[i] >> v[i];
    }
    for (long long i = 0;i <= N;i++){
        for (long long j = 0;j <= W;j++){
            dp[i][j] = -LLONG_MAX;
        }
    }
    dp[0][0] = 0;   
    for (long long i = 1;i <= N;i++){
        for (long long j = 0;j <= W;j++){
            if (j < w[i]){
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - w[i]] + v[i]);
            }
        }
    }

    long long Answer = 0;
    for (long long j = 0;j <= W;j++){
        Answer = max(Answer,dp[N][j]);
    }
    cout << Answer << endl;
}

A20 - LCS

• 当たり前に解説AC。この辺から解説読んでも簡単には理解できなくなってくる。

典型90問

061 - Deck（★2）

• 流石にこのくらい露骨に問題を用意してくれればdequeを使えばよいということにすぐに気づける
• 山札の上がFront扱いなのでそこだけ注意
• 今気づいたが問題名がそこそこのヒントになっていた

int main() {
    long long Q;
    cin >> Q;
    deque<long long> D;
    for (long long i = 1; i <= Q; i++) {
        long long t,x;
        cin >> t >> x;
        if (t == 1){
            D.push_front(x);
        } else if (t == 2){
            D.push_back(x);
        } else {
            cout << D[x - 1] << endl;
        }
    }
}

067 - Base 8 to 9（★2）

• 記数法変換。問題の意味がイマイチ分からなかった（意味というか意図？）が素直に書かれている通りに実装。
• アルゴ式で使った記数法変換の関数をそのまま使った

long long baseNToDecimal(long long N,string S) {
    // N進数の文字列 S を 10進数に変換
    long long sum = 0;
    long long base = 1;  // N^i を逐次計算
    for (long long i = S.length() - 1; i >= 0; --i) {
        long long digit = S[i] - '0';
        sum += digit * base;
        base *= N;
    }
    return sum;
}

string decimalToBaseN(long long N,long long S) {
    // 10進数の整数 S を N進数の文字列に変換
    string reversed;
    if (S == 0){
        return "0";
    }
    while(S > 0){
        reversed += to_string(S % N);
        S = S / N;
    }
    reverse(reversed.begin(),reversed.end());
    return reversed;
}

int main() {
    string N;
    long long K;
    cin >> N >> K;
    long long ans = 0;
    for (long long i = 0;i < K;i++){
        long long eight = baseNToDecimal(8,N);
        string nine = decimalToBaseN(9,eight);
        replace(nine.begin(), nine.end(), '8', '5');
        N = nine;
        ans = stoll(nine);
    }

    cout << ans << endl;

}

078 - Easy Graph Problem（★2）

• 単純無向グラフの典型問題
• 鉄則本でやった通りに実装。最後に自分自身より頂点番号が小さい隣接頂点がちょうど 1 つ存在するを満たすものを抽出するのだけ忘れずに

int main() {
    long long N,M;
    cin >> N >> M;
    vector<long long> G[100009];
    for (long long i = 0; i < M; i++){
        long long A,B;
        cin >> A >> B;
        G[A].push_back(B);
        G[B].push_back(A);
    }
    long long ans = 0;
    for (long long i = 1; i <= N; i++){
        long long count = 0;
        for (long long j = 0;j < G[i].size();j++){
            if (G[i][j] < i){
                count++;
            }
        }
        if (count == 1){
            ans++;
        }
    }

    cout << ans << endl;
}

余談だん

NoviStepsの運営の方？が鉄則本の問題をXのポスト上でNoviStepsのレーティングで分けてくださってたのを思い出した。（当該ポスト）
これを参考にせいぜい3Qまでの難易度のものだけを各章さらっていく方針に変更する。
各章全クリも目指したいが分不相応な難易度のものに取り組んだところでコンテスト中はE問題以降に関しては問題を見ることすらなく終わるのがほとんどなので意味がない。
今回のA20 - LCSとかよい例で、解説を読んで何とか理解して解説AC＋B問題でアウトプットしたところでコンテスト中に問題を見て「鉄則本でやったA20のLCSのアルゴリズムを応用すればよいんだ！」ということに気づかないで終わると思う。
理解していることとそれを手足の様に扱えるのとは全く別の話。