Codeforces Round #350 (Div. 2) A,B,C,D
今回は比較的解きやすい問題だったせいか E まで解けた人が多く、解くスピードも求められたようだ。
A. Holidays
http://codeforces.com/contest/670/problem/A
問題
一年が n 日ある惑星の話で、平日 5 日と休日 2 日が交互にやってくる。1 年を通した休日の数の最大値と最小値を求めよ。
- 1≦n≦106
解法
7 通り試せばいい。ちなみに休休平平平平平が最大で、平平平平平休休が最小になる。
Codeforces Round #350 (Div. 2) A. Holidays
B. Game of Robots
問題
数列 id[n] が与えられる。id[0], id[0], id[1], id[0], id[1], id[2], id[0], id[1], id[2], id[3], ... と並べていったとき k 番目に現れる数は何だろうか。
- 1≦n≦106
- 1≦k≦min(2*109, n(n+1)/2)
- 1≦id[i]≦109
解法
{id[0]}, {id[0], id[1]}, {id[0], id[1], id[2]}, ... とグループ分けし、k 番目がどのグループの何番目にあるかを求めればいい。やり方は次の 2 つのどちらかだろう。
- k≧i(i-1)/2 を満たす i を求める
- 1,2,3,4,... の順に引けるだけ引いていく
ひょっとしたら 2 つ目の方法の計算量を不安に思うかもしれないが、引く数の合計は 2 乗オーダーなので O(√k) になる。
Codeforces Round #350 (Div. 2) B. Game of Robots
C. Cinema
C++ の unordered_map をそのまま使うと TLE するケースが混じっているらしい。そういうのは Educational Round で先に出して。
問題
人が n 人いて、i 番目の人が使える言語は a[i] である。m 個の映画があり、i 番目の映画は音声の言語が b[i]、字幕の言語が c[i] である。次の条件で映画を絞り込む。
- 使える言語と音声の言語が一致する人数が最も多い。
- 使える言語と字幕の言語が一致する人数が最も多い。
この条件を満たす映画をどれでもいいので一つ示せ。
- 1≦n, m≦200,000
- 1≦a[i], b[i], c[i]≦109
解法
言語 i が使える人数 num[i] としたとき、(num[ b[i] ], num[ c[i] ]) が最大となる i を求めればいい。言語番号が 109 まであるので配列ではなく map を使おう。
Codeforces Round #350 (Div. 2) C. Cinema
D. Magic Powder
D1 の想定解なんだろう？二分探索じゃなくて順次探索なのかな。
問題
1 枚のクッキーを作るには材料 i が a[i] グラム必要である。いま材料 i は b[i] グラムある。すきな材料を合計で K グラムまで増やせる。最大でいくつのクッキーが作れるだろうか。
- 1≦n≦105
- 1≦k≦109
- 1≦a[i],b[i]≦109
解法
「x 枚のクッキーを作れるか」で二分探索する。x 枚作るのに何グラム不足しているかを O(n) で計算して不足分が k 以下であれば可能、そうでなければ不可能である。
適当にやるとオーバーフローするので注意。
