AtCoder Beginner Contest 031 C

リハビリの続き。相変わらずREPとかは使います。

#define REP(i, n) for(int i = 0; i < n; i++)

今回の問題はリハビリには丁度いい問題でした。

C - 数列ゲーム

ざっくり見積もって、

• 高橋君の数字の選び方 50通り
• 青木くんの数字の選び方 50通り
• スコア計算にかかるオーダー 50

なので 50 * 50 * 50 = 125000 で 10⁵ 程度のオーダー。全列挙しても余裕で間に合うので全列挙することにする。 *1 注意点としては

• 問題に書いてあるルールをしっかり読み、正確にコードに再現すること。例えば、
  • 数列に現れる数字はマイナスもあり得る −50≦a_i≦50
  • 青木君は、自分のスコアが同じになるなら一番左を選択する
  • 青木君は 高橋君が丸を付けなかったもの から数字を選ぶ　　　など
• エンバグ *2 しやすいタイプの問題なので注意。例えば、「入力例1」が通り「入力例2」が通ったが「入力例3」が通らなかったため、プログラムを修正した。この時に、「入力例3」は通るようになったが、別のバグで「入力例2」が通らなくなっていた。みたいなことがありがち。全部のテストケース通ることを確認して提出しないとスコアが下がってがもったいない。

言語は C++

int main(int argc, const char * argv[]){
    int n, a[50];
    cin >> n;
    REP(i, n) {
        cin >> a[i];
    }
    
    // スコアの最小値より小さければなんでもいい
    // スコアはマイナスになりうるので注意
    int max_tscore = -500000;
    // taka（高橋君）と ao（青木くん）がそれぞれ何番目の数字を選んだか
    REP(taka, n) {
        int max_ascore = -500000, sonotokino_tscore = 0;
        REP(ao, n) {
            // 同じやつは選べない
            if(taka == ao) continue;
            
            int left = min(taka, ao);
            int right = max(taka, ao);
            int len = right - left + 1;
            // スコア計算
            int tscore = 0, ascore = 0;
            REP(i, len) {
                if(i % 2 == 0) { // 奇数番目の時（つまりindexが偶数の時）は高橋君のスコア
                    tscore += a[left + i];
                } else {
                    ascore += a[left + i];
                }
            }
            // 青木君はなるべく大きくなるように、かつなるべく左のやつを選ぶ
            if(max_ascore < ascore) {
                max_ascore = ascore;
                sonotokino_tscore = tscore;
            }
        }
        max_tscore = max(max_tscore, sonotokino_tscore);
    }
    cout << max_tscore << endl;
}

*1:オーダーは10⁷以上になるとちょっとヤバイ

*2:バグを直そうとしたら別の新たなバグを埋め込んでしまう