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を使っている。
