Codeforces #315 Div.2
今回はまさかのAをHack,B,C遅解きになってしまい、振るわず。1601->1548(-53)
思うにAの問題が理解できず、Bでsetを使ってTLEしたことがキテる。
問題文が理解しにくい。最初のS秒の再生でどこまでダウンロードできるかだけど再生してる実時間の(q-1)/q倍ダウンロードがされる（これをrとする）。つまり、最初にダウンロードが再生されるまで行くとrSされにダウンロードされており、さらにそこまで聞けて…
S+rS+r^2S+r^3S+r^4S+...= S/(1-r) = qS
となる(無限等比級数の総和公式を使用)。二回目の再生ではS=qSになったのとおなじなのでq^2Sまで再生できる。よって結局q^nS>Tとなるnをさがせばいい。対数をとってもできそうだけど怖いのでnを増やしていった(どうせO(log(T/S)))
問題的にはAよりわかりやすい疑惑がある。Time limitが1secなのでnlognとかきつい？setを使ってたらTLEしてしまった(別にここでsetを使う意味はない)
まず、どのIDが何回でてくるかカウントする。1~nのなかにあり一回も出てこないIDをvector<int>とかにpush_backしてメモっておく。舐めるようにまわして重複してたり、1~nの範囲でないのを見つけたらメモった中の数字に置き換える。
といった感じ。
あんまり見ないタイプ?の問題。nまでの回文数とnまでの素数どっちが大きいかって題材。
p,qが定められそのすべてのAについて適するnが存在する。
という仮定を元にnを調べる。この仮説は結局正しい。ここでどうやって最大のnを求めるかだがnの最大値をNと決め打ちしてforをまわしてやってそれぞれで判定を行うだけ。まあ要するに愚直に試しまくる。nが最も大きくなるケースはp=42,q=1である。そのときのnは1179858なのでN=1200000ぐらいにしておけばいいとわかる。
・Nのオーダーをざっと見積もれないのかという話
素数の分布はnまでの素数は近似的にn/logn個になることが知られている。
一方回文数については
1桁では9個
2桁では9個
3桁では90個
という風になり、10^(logn/2)ぐらいというがばがばの憶測が立つ。
10^nまででは10^n/log(10^n) , 10^(n/2)
比較するとだいたいn=10^6ぐらいとあたりがつく。
Dは機会があれば
