TopCoder煮ブログ

SRM 511 DIV1

結果 | 03:17 |

ほぼ１年ぶりの参加。

1358→1412 185.05pt 409位/932人

○×－ (challenge: 0)

Zoo (Easy)

2種類の動物がいて、それぞれが自分より背が高い同種類の数を応える、このときにありえる組み合わせの数を答えよ、という問題。

ソートしてから調べた。0,0,1,1,2,2,3,3,... のように２つずつ進めば正しい状態、どこかで 4,5,6,7... のように１つずつ出てくればそのあとは数が飛んでも2つ以上出てきてもアウト。

そんな感じで書いて、数が多い場合を試して submit。

    long long theCount(vector <int> answers) {
        sort(answers.begin(), answers.end());
        int n1 = 0, n2 = 0;
        for (int i = 0; i < answers.size(); i++){
            if (answers[i] == n1){
                n1++;
            } else if (answers[i] == n2){
                n2++;
            } else {
                return 0;
            }
        }

        long long ret = 1;
        for (int i = 0; i < n2; i++){
            ret *= 2LL;
        }
        if (n1 != n2){
            ret *= 2LL;
        }
        return ret;
    }

戻り値の型が long long なので慎重に書いたが、あとで考えれば最大値は 2^20 だったので long の範囲に収まる。だまされた。

FiveHundredEleven (Medium)

２人が交互にカードを順番に選択して、選択済みカードの OR が 511 になったら負け。２人とも十分に賢いとしたら勝つのはどちらか？、という問題。

カードの数が高々50枚なので総当りでいけそうだと思ったのだが、ロジックを書いている途中で「最適な出し方はどう書けばいいのか」でこんがらがってしまった。このタイプの問題、解けたことないから苦手なのだろう。

やけになって、return rand() % 2 == 0 ? ""Fox Ciel" : "Toastman"; というコードを書いたらチャレンジされた。

???? (Hard)

みてない。解けた人は２人だった。

まとめ

Easy はもう少し早く解きたかった。