10/10 PKU

Algorithm PKU

3014 Cake Pieces and Plates

M個のケーキをN枚の皿に分配する方法は何通りあるか。皿を並び替えると一致するものは同じと考える。

DP。modをつかうとTLEするが使わないとTLEしない謎問題。

3761 Bubble Sort

バブルソートにおいて、「ソートされていなければ、左から順に見ていって、大小が逆なら入れ替える」こと（ラウンドという）を繰り返すアルゴリズムを採用する。
N個の要素があるとき、ソートにKラウンド必要な並び方は何通りあるか。要素は互いに異なる。

(K+1)N-K-1*(K+1)! - KN-K*K! を計算する。
階乗は事前に計算しておけば間に合う。

3977 Subset

N個の数がある。1個以上選んで、和の絶対値を最も小さくせよ。

半分全列挙

3983 快算24

5*(5-(1/5))を出力せよ。（本当はそんな問題じゃないけど）

やるだけ

3970 Party

N個の数の最小公倍数を求めてほげほげせよ

やるだけ

3994 Probability One

2で割るだけ

3744 Scout YYF I

YYFは最初地点1にいて、確率pで1マス、確率1-pで2マス進む。いくつかのマスには地雷がある。地雷を踏まないで通過できる確率を求めよ。

「この地雷は必ず踏む！」と決めた時の確率は決定できるので、そのあと包除原理を用いて踏まない確率を求める。
計算の誤差により、-0.0000000が生じることがあるので注意（確率は負にはならない）。

3272 Cow Traffic

サイクルのない有向グラフがある。牧草地と納屋の間のすべての経路を考えるとき、最もその道を通るような経路の多い道について、その経路数を求めよ。

経路P→Qについて、経路数は(牧草地→P)*(Q→納屋)で求まる。あとはやるだけ。