読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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. 使える言語と音声の言語が一致する人数が最も多い。
  2. 使える言語と字幕の言語が一致する人数が最も多い。

この条件を満たす映画をどれでもいいので一つ示せ。

  • 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 以下であれば可能、そうでなければ不可能である。

適当にやるとオーバーフローするので注意。

Codeforces Round #350 (Div. 2) D. Magic Powder