2/5

PKU 2641

跳ね返るとか考えずにx方向にn*a, y方向にm*b動いたと考える。そしてatan。

PKU 2642

M個選んだ平均がcmin以上cmax以下 ⇔ M個選んだ合計がM*cmin以上M*cmax以下

dp[i][j] := i個選んで合計をjにするとき、最も安いコスト

としてDPする。M*cmaxは最大でも20000なので余裕。

PKU 2643

やるだけ

PKU 2645

赤の個数をr, 黒の個数をbとすると

r(r-1)/(r+b)(r+b-1) = p/q
(r+b)(r+b-1)/r(r-1) = q/p
(r+b)(r+b-1) = qr(r-1)/p

となって、

(r+b)² > qr(r-1)/p > (r+b-1)²

が分かる。またこれから

r+b = ceil(sqrt(qr(r-1)/p))

が分かる。rを決めつけるとbはO(1)で求まるから、その結果が (r+b)(r+b-1) = qr(r-1)/p と 2 <= r+b <= 50000 を満たすかチェックする。

PKU 2607

Floydして全部試す。

PKU 2608

やるだけ。

PKU 2609

ナイーヴな考え方だと状態数が200*10000*10000で破滅する。

i台目の車について考えてる時、片方のフェリーにjまで車が乗っていればもう片方のフェリーにどこまで車が乗っているかは、i-1台目までの車の合計からjを引くことで一意に定まる。よって状態数を200*10000に減らすことができて、あとはDP。

PKU 2610

やるだけ。

PKU 2611

ad-hoc

できるだけ後ろの方の桁で、自分より大きいやつに変えられるところを探す。んで変えたところより後の部分をできるだけ小さくしたら答。

PKU 2613

logとる手抜き解法でWAったので素直に素因数分解しました。

PKU 2614

使える値の範囲が[floor(0.99a),a]だったとして、 an >= floor(0.99a)(n+1) を満たすような n を求める。これを満たすようなnについて何が言えるかというと、[floor(0.99a),a]からn個とってきて作れる値の範囲と、n+1個とってきて作れる範囲の値がかぶるということ。b = floor(0.99a) とすると

an >= b(n+1)
an >= bn+b
an-bn >= b
(a-b)n >= b
n >= b/(a-b)

となるから、[b, a]からceil(b/(a-b))個以上とってくれば、b*ceil(b/(a-b))以上の数は全て作ることができる。

a = 4500 を代入することで441015以上の数は全て作れることがわかる。この事実から計算時間を削減することができる。

あとはDP。

PKU 2560

MST