J言語ってどんな言語？ Jのサイトによれば「モダンで、高級で、汎用的で、ハイパフォーマンスな」言語らしい。 有限オートマトンを2バイトで実装できるらしい。 超幾何級数を2バイトで計算できるらしい。 関数のメモ化が2バイトで実装できるらしい。 実際の…

解法 難しすぎる。説明するよりソース見た方が早いところもあるのでとりあえず基本的な方針だけ説明する。ソースにはコメントをしっかり書いておいたのでそれなりに読めるはず。まず、順位が1の射手について考えると、何ラウンドか経った後に的1に来て、その…

解法 まず各労働者iについて、値 Si / Qiを考える。これについて以下のことがわかる。 Sa / Qa b / Qb のとき、労働者bを給料Sbで雇うと労働者aは給料(Qa / Qb) * Sb で雇える 労働者bを給料Sbで雇ったとき、法律の規定で労働者aには(Qa / Qb) * Sb以上の給…

解法 dp[r1][c1][r2][c2] := 左上(r1, c1)、右下(r2, c2)の長方形部分をカットするときの最小コストとしてDPすればよい。実装はメモ化再帰の方が楽だし部分問題全部解くから時間的にも問題はない。実行時間は O(N2M2(N+M)) と大きめだが N, M

解法 ソートしよう！！！！！！！

結論から言うとカナダ行きます。 1日目：問題の名前に動揺してしまう 2日目：普通に解ける問題を落とす 3日目：勝利 4日目：ボロボロ 納得の行く結果ではありませんがカナダで全力出します。

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

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人になるようなグループの選…

成績 A……AC/0WA 0:21 B……-/- C……-/1WA Aを手早く通せたので3/6位

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

2010年ですね。1月2日になりました。でもこの時間帯に書けば1月1日扱いなんですね。とりあえずPKU100問解くとか言っておきながら全然解けてないですね。2010年は約束を守れる男になるのが目標です。

シャンテン数計算と有効牌計算のプログラムを書いてて思ったんだけど、 123456789m北北北北 みたいな手牌はイーシャンテンと見なすのが普通なのかな。今のプログラムはテンパイ(空テン)と判断してしまうんだけど。