はまやんはまやんはまやん

hamayanhamayan's blog

Codeforces Round #407 問題と解説

http://codeforces.com/contest/788
http://codeforces.com/contest/789

A. Anastasia and pebbles

K個だけ入るポケットが2つある。
N種類の小石がそれぞれW[i]個ある。
1日に各ポケット

  • 最大K個だけ入れられる
  • 同じ種類しか入れられない

最短何日で全て回収できるか

B. Masha and geometric depression

B[1], Qが与えられる。
B[i] = B[i - 1]*Qで計算される。
B[1]から初めてL <= abs(B[N+1])となるまで数列を列挙する。
M個のダメ数A[i]がある。
B[1]~B[N]の中でダメ数ではない数は何個あるか。
もし、数列が無限に列挙されるならば、"inf"と答える。

C. / A. Functions again

N要素の数列Aが与えられる。
f(L,R) = sum{i=L...R-1}(abs(A[i] - A[i + 1]) * (-1)^(i-L))
任意のL,Rの中でf(L,R)の最大値を求めよ。

D. / B. Weird journey

N頂点M辺の無向グラフがある。
このグラフ上で

  • M-2辺は丁度2回通る
  • 2辺は丁度1回通る

ように経路を良い経路とする。
良い経路は何通りあるか。
なお、経路で使った辺の多重集合が同じであれば同じ経路とみなす。
自己辺はあるが多重辺は無い。

E. / C. The Great Mixing

K個の数A[i]がある。
A[i]を重複を許して任意個選択する。
分母を(選択した個数)*1000
分子を選択したA[i]の総和
とした分数がN/1000と等しくなるための選択の個数の最小値を求めよ。

以下、解説
















A. Anastasia and pebbles

別に順番は関係ないので、順番に処理していく。
ceil(W[i] / K)を全て足していく。
これで必要なポケットの総和が得られるので、2で割って切り上げすると必要日数が求まる。

B. Masha and geometric depression

数列を愚直に列挙し、ダメ数に含まれるかは配列Aをソートしておき、lower_boundあたりで取ってくればOK
どちらかというと問題は"inf"になる所にあって、以下の条件のとき"inf"となる

  • B[1] = 0
  • Q = 0, Q = 1, Q = -1

でも実は二番目には罠があってB[1]が既にL <= B[1]となってる場合がある。
この時は次の数列を作る前に終了してしまい、答えが"0"となる。
infまわりが難しい問題。

C. / A. Functions again

http://codeforces.com/contest/788/submission/25902216
まず配列Aの隣接要素の差を取った配列Bを作る。
B[i] = A[i + 1] - A[i]
そして、式によるとプラマイが交互に出てくるので

  • B[i]の奇数番目に*(-1)をした数列
  • B[i]の偶数番目に*(-1)をした数列

の2つの区間和最大が計算できればよい。
sssslide.com
こんな凄いスライドがある。
このスライドのようにDPをするとO(N)で求めることができる(sol関数)のでAC

D. / B. Weird journey

http://codeforces.com/contest/788/submission/25923989
最初に辺で全て連結されているか確認する(chk関数)

まず、全部の辺が2本多重辺として張られていると考える。
ここから、任意の2本の辺を抜いて考えるとき、準オイラー路が作れるならば、それは良い経路である。
愚直にやるとO(M^2)なのでダメ。

オイラー路の条件は「2つの頂点だけ次数が奇数で他は次数が偶数」である。
全部の辺を2本とすると、全ての頂点の次数は必ず偶数になる。
そのため、まず1本の辺を抜くと、その端点は必ず奇数となる。
もう1本抜いて次数が奇数の頂点を2つにしようとすると、抜くべき辺は1本目に抜いた辺と隣接する辺となる。
そのため、これを数え上げればよい。

が、これだけやるとWA。
実は今回は自己辺が厄介な役割をする。
自己辺は抜いてもその頂点の次数の偶奇は変化しない。
自己辺以外だけで考えると上だけでいいが、自己辺が含む場合は、

  • 任意の自己辺と任意の普通の辺
  • 任意の2組の自己辺

を抜いても準オイラー路の条件をみたす。
そのため、次数をカウントするときに、自己辺は抜いてカウントする。
そして、後から自己辺が関係するものを足せば答え。

E. / C. The Great Mixing

http://codeforces.com/contest/788/submission/25937694
例をまず考えてみる。

Example1は、N=400, K=4, A={100, 300, 450, 500}
要素A[i]をB[i]個使うとする。すると
100B[1] + 300B[2] + 450B[3] + 500B[4] / (B[1] + B[2] + B[3] + B[4]) * 1000 = 400 / 1000
をみたすB[1]+B[2]+B[3]+B[4]の最小値を求める問題となる。
等式を変形すると、
100B[1] + 300B[2] + 450B[3] + 500B[4] = 400 * (B[1] + B[2] + B[3] + B[4])
(100 - 400)B[1] + (300 - 400)B[2] + (450 - 400)B[3] + (500 - 400)B[4] = 0
となり、A[i]-Nをうまく選択して0となれば良いことが分かる

任意の個数を使って総和が0となるようにすれば良いが、この時の計算過程は[-1000,1000]だけ考えればいいっぽい(他の人の解答見てると)。
あと答えは存在するならば1000を超えないらしい。
なんで?

やり方はdpかBFS(最短経路的な感じで考える)があるが、dpで解く方法を見てみよう。
dp[i][j] := i個足して総和がjとなるかどうか
愚直にこれをループで全部回しても多分大丈夫だが、自分の解答では領域を使いまわしてjの部分はbitsetを使っている。