ABC119 C Synthetic Kadomatsu (C++)

irisruneです。今回はC++使ってた頃のコンテストなのでC++です。

atcoder.jp

自分が水色になった回でもある大変愉快な問題ですね。解くためのポイントは大きく2つあって、

1. の全探索アルゴリズムに持ち込めるか
2. 1.を実装できるか

まず1.について、この問題DPっぽいですがC問題でDPは滅多にない…と思うので除外。まだ全然過去問埋まってないからわからないですね。

それでなくてもという不自然に小さい問題規模に着目すれば全探索に行き着くことはできると思います。 問題はにモデル変換できるかなんですが…理屈ではよくわからないです。 解説見てもフィーリングとしか言えない。

とりあえず1.を達成できたことにします。では全探索を実装するわけですが…とりあえず自分のコードを。

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

int n, a, b, c;
vector<int> vl;
vector<int> vx;

void init() {
    cin >> n >> a >> b >> c;
    for(int i = 0; i < n; i++){
        int l;
        cin >> l;
        vl.push_back(l);
    }
}

int solveSub2(){
    int MP = -30;
    int la = 0;
    int lb = 0;
    int lc = 0;
    for(int k = 0; k < n; k++){
        if(vx.at(k) == 1){
            la += vl.at(k);
            MP += 10;
        }
        else if(vx.at(k) == 2){
            lb += vl.at(k);
            MP += 10;
        }
        else if(vx.at(k) == 3){
            lc += vl.at(k);
            MP += 10;
        }
    }
    if(la == 0 || lb == 0 || lc == 0) return 3000;
    MP += abs(a - la) + abs(b - lb) + abs(c - lc);
    return MP;
}

int solveSub1(int idx){
    int minMP = 3000;
    for(int j = 0; j < 4; j++){
        vx.at(idx) = j;
        if(idx < n - 1) minMP = min(minMP, solveSub1(idx + 1));
        else minMP = min(minMP, solveSub2());
    }
    return minMP;
}

int solve(){
    for(int i = 0; i < n; i++){
        vx.push_back(0);
    }
    return solveSub1(0);
}

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    init();

    cout << solve() << "\n";

    return 0;
}

突っ込みどころは多いですがそこは後でコードレビューしましょう。

原理としてはそれぞれの竹の用途を0,1,2,3に当てはめ、そこからMPを求めて最小値を取るだけです。 どうしてこういう解き方をしたかというと、を列挙してそれを用いるようなコードを過去に見たことがあるからでした。

一方、公式解説ではDFSで実装してるので大変スマートですね。こういう基本的な探索アルゴリズムを覚えておくことも重要だと思いました。

最後に今回のコードレビュー。

• 関数名が適当すぎる。
• 関数solve()の存在意義がない。
• 竹の用途のリストを作りながらMPを求めるより、いったん『竹の用途のリスト』のリストを作って順番にMPを求める方が明確。
• なんでもかんでもグローバル変数にするのは楽だけどよくない。

雑記

• 明日のAGCは冷えないことを祈ります。
• マラソンコンテストの初心者記事とかも書いてみたいですね。