成績 A……AC 187.64/250.00 B……AC 458.99/500.00 C……Opened 3/6位 A 一番右端にドミノを置くとき、その置き方は「縦縦」か「縦横横」か「横横縦」か「横縦横」か「横横横横」だけ。4xW にぴったりドミノを置くときの置き方を f(W) と書く。するとまずW列目に…

wrong

PKU 1847 だいくすとらどう考えてもFloydの方が楽です本当にありがとうございました PKU 2657 for(pos=0; !visited[pos] && !obstacle[pos]; ++pos /* !!!!!! */) { visited[pos] = true; pos = (pos+K) % N; if(pos == Z) break; } この部分を発見したとき…

PKU 1154 DFS

PKU 2367 トポロジカルソート PKU 2368 L >= 2 で K % (L+1) == 0 であるような最小のLが答。つまり3〜sqrt(K)まで試し割ればO(sqrt(K))で解ける。ただし3から試し割りすると K = 2*p のような形のときに約数 p を見逃すので注意が必要。 PKU 2369 サイクル…

PKU 3287 大きさが同じやつは絶対に一つにpackできないから、入力値のヒストグラムの頂上がまず答。その具体的な内容としては、入力値のヒストグラムの頂上をkとし、入力をソートしたものをDとすると、D[i]とD[i+k]について必ず D[i] D[0], D[k], D[2k], D[3…

PKU 2573 一番遅い二人を向こう岸に運ぶことを考える。t[1]を最も速い人、t[n]を最も遅い人とする(tはソートされている)。このとき二種類の方法が考えられる。1. (1, 2)で行く→1が帰ってくる→(n-1, n)で行く→2が帰ってくる 2. (1, n)で行く→1が帰ってくる→(1…

PKU 2465 dp[i][j] := i番目のガソリンスタンドに居て、残り燃料jの時の最小の支払額としてDP。 PKU 2466 まず求めたい数列を a、入力の数列を s とする。ただし両方ソート済み。そうするとまずs[0] = a[0]+a[1] s[1] = a[0]+a[2]は明らか。ここで、あるiに…

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は最大…

PKU 2330 奥の方から描いていくだけ。 PKU 2331 xについてDFSしてからyについてDFSする。 PKU 2333 点iと点jを結んだ時の面積は点iと点j-1を結んだ時の面積に三角形i,j,j-1の符号付面積を足せば求まるので、後はO(N2)通り全部試すだけ。L2がintに収まらない…

PKU 3744 ある場所からnステップ先の場所に行ける確率をf(n)とすると明らかに次の式が成り立つ。f(n) = pf(n-1) + (1-p)f(n-2)これの特性方程式はx^2 - px - 1 + p = 0これを解くとx = 1, p-1よってf(n) = c1 + c2(p-1)nと書ける。f(0) = 1, f(1) = p は明ら…

CEOIの問題は良いのが多いですね。