2011-07-02
SRM 511 DIV1
結果 | |
ほぼ1年ぶりの参加。
1358→1412 185.05pt 409位/932人
○×- (challenge: 0)
Zoo (Easy)
2種類の動物がいて、それぞれが自分より背が高い同種類の数を応える、このときにありえる組み合わせの数を答えよ、という問題。
ソートしてから調べた。0,0,1,1,2,2,3,3,... のように2つずつ進めば正しい状態、どこかで 4,5,6,7... のように1つずつ出てくればそのあとは数が飛んでも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)
2人が交互にカードを順番に選択して、選択済みカードの OR が 511 になったら負け。2人とも十分に賢いとしたら勝つのはどちらか?、という問題。
カードの数が高々50枚なので総当りでいけそうだと思ったのだが、ロジックを書いている途中で「最適な出し方はどう書けばいいのか」でこんがらがってしまった。このタイプの問題、解けたことないから苦手なのだろう。
やけになって、return rand() % 2 == 0 ? ""Fox Ciel" : "Toastman";
というコードを書いたらチャレンジされた。
???? (Hard)
みてない。解けた人は2人だった。
まとめ
Easy はもう少し早く解きたかった。
コメント