Codeforces 578B. "Or" Game
問題
n個の整数a_iが与えられる。
高々k回、整数xを整数a_iから一つ選んでかける、という操作を行える。
各整数のORをとったものa_1 | a_2 | ・・・| a_nの最大値はいくつになるか？
1<=n<=2*10^5
1<=k<=10
2<=x<=8
0<=a_i<=10^9
考え方
直感的に、xが2以上なので、x^kをかけた方が最大bitを更新できるので、a_iの最大値にx^kをかけた方がよさそうに感じる。
しかし、k=1程度だと、a_iの最大値でないものにかけた方が良い結果が得られる場合が存在してしまう。
(a={12,9},k=1,x=2の場合、12に2をかけるよりも9に2をかける方がよい。)
xをかける操作を複数のa_iに分けた方が良いかというと、最大bitを更新できたほうがよいので、x^kを一つにかけた方が良い。
どれにかけた方がよいかは試すしかなく、計算量を減らして探す必要がある。
1番目からi-1番目までのORを取ったもの、と、i+1番目からn番目までのORを取った物がわかれば、この2つとa_i*x^kとのORを取れば、a_iをx^k倍したときの全体のORがO(1)で求められ、最初の2つの範囲のORはO(n)で計算できる。
これらの中で最大のものを返せば良い。
Codeforces 578A. A Problem about Polyline
問題
(0,0)->(x,x)->(2x,0)->(3x,x)->・・・のようなぎざぎざした線を考える。
今、整数点(a,b)をこの直線が通る事がわかっている。
可能なxの中で最小のものを返す。なければ-1を返す。
1<=a,b<=10^9
考え方
まず、y軸の方は0からxまでしか変化し得ないので、b以上でなければならないので、x>=b。
x=bとすると、aがxで割り切れるならば、山なりの頂点になる。なので、x=bが答えになる。
そうでなければ、山と山の間に点が存在しうる。xを増やす方にしか変化しないので必ず、左側の山を下る線上に点が存在するはず。なので、点(a,b)を通るような45度で下るような線を考えれば良い。
45度で下るような線はy'=-x'+pなのでp=a+bとなって、y'=-x'+(a+b)。
そして、この線は{a/b+(a/b)%2}番目の線なので、(a+b)/(double){a/b+(a/b)%2}が答えになる。
また、答えがないケースとして、最初の山に上る線より左側、{a/b+(a/b)%2}==0であるような場合は答えがない。
Codeforces 577B. Modulo Sum
div2Bのレベルなの・・・？
問題
n個の要素からなる数列aと整数mが与えられる。
空でない部分列の和がmで割り切れるような部分列があるかチェックし、あるならYES、ないならNOを返す。
1<=n<=10^6
2<=m<=10^3
0<=a_i<=10^9
考え方
各a_iはmod mを取っておいても問題ない。なので、問題は「0〜(m-1)のn個の整数の和のmod mが0となるものがあるか？」になる。
計算量を無視して考えると、
dp[i][j]:=i番目までを使って、和 mod m = jとなるような和が作れるか？(YES/NO)
というdpで、dp[i][j]が作れる(YES)なら、dp[i+1][(j+a_{i+1})%m]とdp[i+1][j]も作れる(YES)。
各iのうち、dp[i][0]が2以上(1つは何も足さない場合)になっているものがあれば、0となるものを作れるのでYES。
ただし、これだと、O(n*m)になってTLEになってしまっている。
もし、「部分列」ではなく、「連続する部分列」である場合は、先頭からi番目までの和を計算しておくと、同じ和が2回以上でてくれば、その和が出てきたインデクスをl, rとすると、(l+1)〜rまでの和は0になっている、とチェックできる。
実は、n>mであるならば、先頭からi番目までの和はn個でてきて(鳩)、m種類の値(鳩の巣)のどれかになるので、鳩の巣原理より必ず同じ和となる2つ以上の場所が存在する。
なので、n>mなら必ずYESになり、n<=mならば、上のdpで計算してもO(m^2)なので、計算量的に間に合う。
SRM462 div1 250
問題
バス停からn台のバスが確率的に選ばれて1台だけ出発し、そのバスが戻ってくるまで他のバスは出発できない。
バスiは、戻ってくるまでtime[i]時間だけかかる。また、バスiはprob[i]/100の確率で選ばれる。
バス停に時刻sで訪れた時にバスの出発までに待たなければならない時間の期待値を求めよ。
n<=100
time[i] <= 10^5
prob[i] <= 100
s <= 10^5
考え方
愚直に全パターンを求めるとO(N^N)程度確認する必要があるので、TLE。
dp[i]:=時刻iにバスがちょうど戻ってくる確率
がわかると、(i-s)時刻だけ待つ確率がdp[i]で求まるので、s以上のiについて、dp[i] * (i-s)を足し合わせればよい。
dp[i]は時刻sを超えたiから出発する分については考える必要がないので、0〜sから出発する場合のみ考えればよく、時刻iでバスjを使う場合、dp[i+time[j]] += dp[i] * prob[j]で求めていける。
SRM500 div1 250
英語の読解力が低い・・・
問題
N人でマフィアというゲームを行う。
各ターン、N人全員が「弱いと思われる候補者」に投票し、投票数が最大の人が1人ならばその人が負ける。
投票数が最大の人が複数人いる場合、その人たちを「弱いと思われる候補者」の対象として投票しなおす。
今、M個(<=N個)の「投票先の情報」が配列で与えられる。誰の投票先かはわからない。
投票先が「弱いと思われる候補者」に居ない場合、または、(N-M)人の投票先がわからない人の場合、一番投票数が少ない人にいれる。ただし複数人いる場合はその人たちの中から一様ランダムに選んで投票する。
最初のターンは全員が「弱いと思われる候補者」の状態からスタートし、各人の中で負ける確率が一番高い人のその確率を返す。もし、無限ターン行っても負けの人が決まらない場合は確率0.0を返す。
考え方
N人の候補者から投票して、a人になったとする。a=1なら負けの人が決まるので1.0で終了。
a人は同票数で、a人以外に投票されてた票が次のターンではa人に均等に投票される。
均等に投票されるので、a人に投票すると、N%a人が1票多い状態になる。
b=N%a人が次の候補者なので、同様にN%b人が1票多い状態になって次の候補者になる。
これを繰り返してN%x=0になる場合、無限ターン行うことになる。N%x=1ならば候補者が決まる。
候補者が決まる場合、その候補者はa人のうちどれかだが、どの人も等しく選ばれる可能性があるので、結局、確率1.0/aが答えになる。
反省
「弱いと思われる候補者の配列」の解釈を間違っていた。(投票順番が関係すると思ってた)
yukicoder No.23 技の選択
問題
体力がHのモンスターを倒したい。
毎ターン、通常攻撃と必殺技攻撃ができ、
・通常攻撃の場合は、必ずAのダメージ
・必殺技攻撃の場合は、1/3で失敗し0ダメージ、2/3でDのダメージ
を与えられる。
モンスターを倒すのに、攻撃の回数の期待値が最小となるようにしたいとき、その期待値を求める。
1<=H,A,D<=10^4
考え方
通常攻撃をx回行った場合、H-A*xのダメージが残っており、これを必殺技攻撃で減らす事を考える。
もしH-A*x<=0ならば通常攻撃だけで倒すので、必殺技は必要なく、攻撃回数の期待値はx。
必殺技ではDだけ減らせるので、必殺技攻撃の回数をy回とすると、「y=(H-A*x)/D+((H-A*x)%D!=0)」回の攻撃が必要となる。
「確率pであたる攻撃を、y回当てるまでにかかる回数」＝Xとおく。ここで求めたいのは、E[X]。
愚直に考えると、ちょうどi回でy回攻撃できるとすると、
E[X]=Σ_{i=y}^∞ i * q_i
E[X]=Σ_{i=y}^∞ i * Comb(i-1, y-1) * pow(1.0/3.0, i-y) * pow(2.0/3.0, y)
と考えられる。しかし、無限回の足し算が必要だったり、iが大きくなると、powの部分がかなり小さくなってしまうため、十分な精度で求める事ができない。
別な見方として、Xを分解し、
E[X]=E[最初に攻撃があたるまでにかかる回数 + 2回目に攻撃があたるまでにかかる回数 + ... + y回目に攻撃があたるまでにかかる回数]
とする。
期待値の線形性より、
E[X]=E[最初に攻撃があたるまでにかかる回数] + E[2回目に攻撃があたるまでにかかる回数] + ... + E[y回目に攻撃があたるまでにかかる回数]
とかける。
それぞれ、攻撃があたるまでにかかる回数の期待値は、それぞれ確率が同じなので、期待値も同じになることから、
E[X]=y * E[最初に攻撃があたるまでにかかる回数]
とできる。
「最初に攻撃があたるまでにかかる回数」というのは、「成功確率がpのベルヌーイ試行を繰り返し、最初に成功する試行回数」なので、幾何分布に従う。なので、E[最初に攻撃があたるまでにかかる回数]=1/pが言える。
http://ja.wikipedia.org/wiki/%E5%B9%BE%E4%BD%95%E5%88%86%E5%B8%83
なので、E[X]=y/p=y*3.0/2.0となり、xについてループをまわして「x+y*3.0/2.0」が最小となるものを探せばよい。
(「回数の期待値」っていうのかな？)
Codeforces 550A. Two Substrings
A問題で簡単だと思って油断すると、怪しいケースを見逃したりするので注意。
問題
長さがnの文字列sが与えられる。
「AB」と「BA」の2つの文字列が部分文字列としてオーバーラップしないように含まれるか？を確認し、含まれるならYES、そうでないならNOを返せ。
1<=n<=10^5
考え方
愚直にABをみつけたらそこをつぶしてからBAを探す方法ではO(n^2)でTLE。
文字列sについて、BAが出現する位置、その個数を求めておく。
すると、ABが出現したとき、BAが他のところで出ていればよく、それは個数をみればよさそうに思う。
しかし、ABAのような場合、ABを見つけたとき、一つ後ろのオーバーラップする位置にあるBAが選べなくなる。なので、個数から1引いて、個数が1以上かどうかを確認する必要がある。
上記以外に、BABのケースの場合、ABをみつけて、一つ前のオーバーラップする位置にあるBAが選べなくなる。なので、同様に個数から1引いて確認すればよい。
その他の場合はオーバーラップしないので、前後に出現するBAを確認し、あれば引いて、そのあとの個数を確認すればよい。
これならO(n)で求められる。
