ferinの競プロ帳

競プロについてのメモ

2018-02-04から1日間の記事一覧

SRM643 div1 easy TheKingsFactorization

考えたこと 素因数分解は試し割りでO(sqrt(N))なので愚直にやるのは間に合わない ヒントとして与えられた素因数でNを割っておいていい primes[i] = primes[i+1] ならば間に入る素因数はprime[i]で確定 O(primes[i+1]-primes[i])かけて全て試せば間に入る素因…

SRM642 div1 easy WaitingForBus

考えたこと 期待値と言われたので線形性を考えるとn回バスが到着するまでの時間の期待値は求まる気持ちになる 何回目のバスに乗ることになるかがわからないので上のが求まったとしてもよくわからない気がする i回目のバスでsに達しておらずi+1回目のバスでs…