−目次
AtCoder Beginner Contest 404(Promotion for Engineer Guild)F,G問題メモ
F - Lost and Pound
問題文
- NN 個の押しボタンがあります。このうち 11 個が当たりで、残りの N−1N−1 個はハズレです。
- 青木君はどのボタンが当たりであるか知っており、高橋君は知りません。また高橋君には NN 個のボタンの区別はつきません。
- このボタンを使って青木君と高橋君がゲームを行います。ゲームは以下の一連の流れの TT 回の繰り返しからなります。
- 青木君が NN 個のボタンをランダムな順序に並べる
- 高橋君が「ボタンを 11 つ選び、そのボタンを押す」という操作を MM 回行う。同じボタンを複数回選んでもよい
- ゲーム開始時からこれまでに当たりのボタンが何回押されたかを青木君が高橋君に教える
- TT 回の繰り返しで、当たりのボタンを合計 KK 回以上押すことができたとき、かつ、そのときに限り高橋君の勝ちです。
- 勝つ確率が最大になるように高橋君が行動したときの、高橋君の勝率を求めてください。
- 真の解との絶対誤差または相対誤差が 10−610−6 以下のとき正解と判定される。
制約
- 1≤N≤2×1051≤N≤2×105
- 1≤T≤301≤T≤30
- 1≤M≤301≤M≤30
- 1≤K≤301≤K≤30
- 入力は全て整数
解法
めっちゃ誤読して、ボタンは最初以外、並び替えられないものと考えてしまっていた。
結果によって当たりボタンを絞り込んでいけると思ったら、そうではなかった。
毎回並び替えられてしまうので、今回の操作で押したボタンに当たりが含まれていても、次回はどこに行ったかわからない。
よって、毎回、左詰で押していくと考えてよい。
ボタンの押し方の数は、合計が MM になるような正整数の組合せの数、つまり MM の分割数になる。
分割数は M=30M=30 でも 56045604 個であり、その具体的な分割の仕方を同時に求めても、O(M3)O(M3) で済む。
その上で、以下の関数を考える。f(T,K)f(T,K) を求められればよい。
- f(t,k):=f(t,k):= 残りターン tt、残り必要押し回数 kk である時の勝率
ある押し方で、ボタンを押す回数を X={x1,x2,...,xp}X={x1,x2,...,xp} 回とする。(∑ixi=M∑ixi=M)
- ボタン ii が当たりである確率は 1/N1/N
- その時、これ以降の勝率は f(t−1,k−xi)f(t−1,k−xi)
また、
- どれも当たりでない確率は (N−p)/N(N−p)/N
- その時、これ以降の勝率は f(t−1,k)f(t−1,k)
押し方 XX の勝率は、これらの和となる。
- p∑i=1f(t−1,k−xi)N+(N−p)f(t−1,k)Np∑i=1f(t−1,k−xi)N+(N−p)f(t−1,k)N
全ての押し方の中の最大値が、f(t,k)f(t,k) となる。
よって、状態数 O(TK)O(TK)、1回の遷移 O(p(M)M)O(p(M)M) となる。(p(M)p(M) を MM の分割数とする)
全体 O(M3+TKMp(M))O(M3+TKMp(M)) で求められる。
G - Specified Range Sums
問題文
- 整数 NN と長さ MM の整数列 L=(L1,L2,…,LM),R=(R1,R2,…,RM),S=(S1,S2,…,SM)L=(L1,L2,…,LM),R=(R1,R2,…,RM),S=(S1,S2,…,SM) が与えられるので、次の問題を解いてください。
- 以下の条件を満たす長さ NN の 正整数列 AA が存在するか判定し、存在する場合は AA の総和としてありうる最小値を求めてください。
- 全ての ii ( 1≤i≤M1≤i≤M ) について、 Ri∑j=LiAj=SiRi∑j=LiAj=Si を満たす。
制約
- 入力は全て整数
- 1≤N,M≤40001≤N,M≤4000
- 1≤Li≤Ri≤N1≤Li≤Ri≤N
- 1≤Si≤1091≤Si≤109
解法
AA の代わりに、累積和 B0,B1,...,BNB0,B1,...,BN を考えることにする。B0=0B0=0 として、BNBN の取り得る最小値が答えとなる。
各条件 (L,R,S)(L,R,S) は、BL−1+S=BRBL−1+S=BR という制約となる。
また、AA は正整数列より、Bi+1≤Bi+1Bi+1≤Bi+1 という制約もある。
前者の制約は、ポテンシャル付きUnionFindで、(L,R)=(1,2),(2,3),(1,3)(L,R)=(1,2),(2,3),(1,3) のように、ループする関係性について矛盾するか調べられる。
矛盾したら答えは無し。
矛盾しなかったら、各連結成分の中で1つの値が決まったら残りも全部決まる。
後は後者の制約に違反しないように、各連結成分のオフセットを決めるか、矛盾することを判定できればよい。
各連結成分 cc について、以下のように暫定オフセット値 Oc を調べていく。
最初は各 c に対し Oc=0 とする。
- i=1,2,...,N の順に、以下の2つを計算する。
- p: i の属する連結成分 ci のオフセット Oci を元にした値
- q: i−1 の箇所から1大きい値
- p<q の時、現在のオフセットでは足りないということなので、足りない分、オフセットを更新する。
1周しただけでは、正しい答えが求まる保証はない。
i が後の方でのオフセットの更新の影響が、前の方に遡るかもしれないので。
だが、更新の発生は「連結成分の数」周以内に収まる(TODO 未証明)。
Bellman-Ford と似た要領で、何周か更新を繰り返した上で、
次の1回でも更新が発生した場合、矛盾する区間があったということになる。