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の問題は良いのが多いですね。

PKU 2206 dp[i][j] := i番目までの数を使ってjができるかどうかでDP。 PKU 1426 mod n で幅優先。 PKU 3641 やるだけ。

PKU 3279 一行目を全部試すだけ。IMPOSSIBLEの出力を忘れてWA食らいまくったのもいい思い出です。 PKU 1417 "x y yes" => xとyは同じグループ"x y no" => xとyは違うグループとしてグループ分けをする。あとは人数でDP。合計がp1人になるようなグループの選…

PKU 2705 シミュレーションするだけ。 PKU 2706 Union-Find + 線分交差判定別にUnion-FindじゃなくてDFSやBFSで調べてもいい。 PKU 2744 DPdp[k][n] := 最後にタイヤを交換したのが地点 an のとき、地点 k に辿り着くまでの最短時間 PKU 3298 i個目までの時…

PKU 3134 BFSある xn に辿り着く最短経路が10を越えたら探索打ち切るad-hoc枝刈りで通した。 PKU 1944 ある二つのノード a, a+1 は絶対に繋がないと決めつけてやる。 O(NP)。何をとち狂ったのか O(N2P) を投げ続けるなどしてサーバに無駄に負担をかけてしま…

PKU 1833 next_permutation PKU 1742 DP配列を必要量の10倍確保するなどしてTLEを食らった。 PKU 3522 辺の配列 E が重みでソートされているとして、min(1 が答。m回最小全域木を作ってみればよい。 PKU 3523 A*ひたすら頑張って探索 & 高速化ゲー。C++でRun…

PKU 2110 だいくすとら PKU 1166 全探索 PKU 1167 反復深化深さ優先探索 + 枝刈り PKU 2704 典型DP PKU 2195 最小費用流 PKU 3692 補グラフから最小頂点被覆を除く PKU 2386 BFS

PKU 1926 繰り返すだけ。 PKU 1988 Union-Find + αブロックiについて、iを含むスタックの高さと、iより上にあるブロックの個数を記憶しておく。 PKU 2629 やるだけ PKU 2711 流すだけ

PKU 3027 やるだけ PKU 1632 枝刈り探索で間に合う PKU 3465 まず y > Ai ならDefendする必要はなくて y 方針としてはとりあえずAttackしまくる。Attackしまくりつつ、もしその時にDefendかHealを選んでいたらどれだけHPを回復できるかという値をヒープに突…

早朝PKU

12月15日 16. PKU 1217 DP。dp[r][a][b]を、「rラウンド後にAの得点がa、Bの得点がbである確率」としてやる。 17. PKU 1226 全探索。 12月16日 18. PKU 2914 無向グラフの全域最小カット。 19. PKU 2920 やるだけ。 20. PKU 2922 経路中最も低い部分の高さを…

JOI予選で満点がとれなかったのでPKUを年内に100問解く決意をしたのですが、解法の復習はやはり勉強になるということで記録をつけます。

徹夜で頑張りすぎた。今日：10問 今日までの合計：134問

今日：1問 今日までの合計：124問

今日：3問 今日までの合計：123問

今日：6問 今日までの合計：120問

今日：1問 今日までの合計：114問

今日：8問 今日までの合計：113問

今日：3問 今日までの合計：105問

祝100問突破今日：4問 今日までの合計：102問

そして今日もTopCoder SRM今日：6問 今日までの合計：98問