Algorithm
昨年のJOI合宿のDay 1では3問の問題が出題されました．http://www.ioi-jp.org/camp/2011/2011-sp-tasks/2011-sp-day1.pdf一問目の Banner は易しいもので，三問目の Joitter は若干の思考ととコーナーケースに引っかからない注意深さが求められるものでした…
問題文 http://d.hatena.ne.jp/asi1024/20101225/1293242247 解法 幼女から母親までの距離 >= 幼女から一番近いハンターまでの距離 のとき 幼女に一番近いハンターが先に幼女へ辿りつけるので無理 幼女から母親までの距離 母親が幼女への最短経路を行ければ…
問題文 http://d.hatena.ne.jp/asi1024/20101224/1293157742 解法 まあ、パッと見貪欲で終了って言ってもいいけど、詳しく解説してみる。簡単なDPから貪欲にする方針で。 dp[i] := 本棚 i..M を修理するのにかかる最低時間 とすると求める答は dp[1] で、こ…
順当にいけば満点。ソース掲載(提出したものとは違うやつもある)。
オンライン参加できるらしいので参加。10問中8問解けた。4位らしい。 A やるだけ B i個目までやっていて、直前に右足を使った場合の最小を lr、左足の場合を rl とでもする。i+1個までの lr_next, nr_next を求められるとうれしい。i個目の場所をS[i]とする…
結果 hos.lyricさんが600点(全問完答)で、2位の420点に大差をつけて優勝でした！おめでとうございます！2位以下は接戦で、上位陣は3完にあとどれだけ点数を上乗せできるかがポイントだったようです。 問題 A, B, C, D, E, Fの6問でした。すべてお花を題材に…
オンライン参加できるらしいので参加。10問中5問解けた。暫定3位(→USAGI Codeが真にぱないことになって結果は4位でした)。昨日のも3位だったらしい。 A グラフにして連結成分を1つの頂点にまとめてDAGにしてからDPDPは、ある頂点 v について、頂点 v とそれ…
オンライン参加できるらしいので参加。10問中6問解けた。 A やるだけだが壮絶にバグる。 B rが小さくて座標が整数なので答えは必ず10000以下になることがわかる。あとは dp[i][j][k] := ニンジンをk個貰っていて、現在いる都市が j、その前にいた都市が i と…
問題概要 横M、縦Nの二次元フィールドに辺がx軸y軸とそれぞれ平行な長方形の障害物がP個ある。i個目の障害物はCiの金で撤去可能であり、与えられた予算はBである。このフィールド上にできるだけ広い正方形の土地を確保せよ。 1 1 1 次の3つのテストグループ…
結果 Hardが運良く(1.994sかかるケースがあった)通って3完。以下時系列順。
問題概要 数直線上にいくつかの点のペアが存在し、その片方に乗るともう片方に飛ばされるように(テレポートするように)なっている。全ての点の座標は1以上で2,000,000以下。同じ座標に複数の点は存在しない。この数直線上で0から出発し、どんどん右へ進んで…
問題概要 LとPのみからなるN文字の文字列であり、どの連続した区間をとっても一方の文字が他方の文字より3文字以上多いことがないという制約を満たす文字列がひとつ与えられる。与えられた文字列が、この制約を満たす文字列のうち辞書順で何番目かを求めよ。…
問題概要 N個の頂点とN個の辺を持ち、どの頂点も最低1つの辺で接続されているような重み付き無向グラフが与えられる。好きな頂点から出発して、次のどちらかの移動を繰り返す。ただし同じ頂点に2度訪れることはできない。 辺を辿って移動する。 どのように辺…
問題概要 スタックが1個あって、次の3つの操作が許されている。 文字を1つpush 文字を1つpop スタックの底から頂点までをなぞって文字列を印字する さて、N個の文字列が与えられるので、上の3つの操作をできるだけ少ない回数だけ使ってこれらの文字列を全て…
解法 まず木の節点の番号をpreorderで付け直す。すると、ある節点の子の節点の番号は連続する整数になるので、全ての節点についてその子の節点番号の区間を計算しておけば「節点bは節点aの子か？」という問にO(1)で答えることができて便利。これは木を辿るだ…
解法 難しすぎる。説明するよりソース見た方が早いところもあるのでとりあえず基本的な方針だけ説明する。ソースにはコメントをしっかり書いておいたのでそれなりに読めるはず。まず、順位が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日目：ボロボロ 納得の行く結果ではありませんがカナダで全力出します。
たぶん116点。凡ミスで4点落とすのはもう嫌だお……。というか2でミスったの俺だけだろ……。
1億(108)まで篩ってみると1秒ほど差が出た。アセンブリの方が1.762秒で普通の方が2.772秒。(Core2Quad Q9450) #define MAX 100000000 #define SQRT_MAX 10000 char flags[MAX/8+1]; void Eratosthenes() { __asm__ ("movl $2, %%ecx \n\t" "erloop1: \n\t" "…
2.2-1 Θ(n3) 2.2-2 def selection_sort(A): n = len(A) for i in range(n-1): minimum = i for j in range(i+1, n): if A[minimum] > A[j]: minimum = j A[i], A[minimum] = A[minimum], A[i] ループ不変式は、「第3-8行のforループが開始されるとき、部分配…
2.1-1 2つの41の順序関係が維持されている(安定である)ことに注目するぐらい。 2.1-2 def insertion_sort(A): for j in range(1, len(A)): key = A[j] i = j-1 while i >= 0 and A[i] < key: A[i+1] = A[i] i -= 1 A[i+1] = key 2.1-3 def linear_search(A, …
以下の高次方程式の解を全て求められる。試しにを解いてみると >>> solve([16, -152, 324, 162, 80, 50]) [(1.7058483573106117e-15+0.5000000000000019j), (1.7058483573106117e-15-0.5000000000000019j), 4.999999960549872, -0.5000000000000036, 5.00000…
Exact Cover Problem 今回解説するKnuth's Algorithm Xは、Exact Cover Problemという問題を解くためのアルゴリズムです。Exact Cover Problemについてはうまい日本語訳が分からない(「敷き詰め問題」とか？)ので英語のまま書いています。数学で言うと、ある…
PKU 3076を解くのに書いた。 参考 http://en.wikipedia.org/wiki/Algorithm_X http://en.wikipedia.org/wiki/Dancing_Links
IOI 2009公式サイト内の順位表この順位表の19位が俺です。本名モロバレだけど気にしない。ちなみに点数の内訳は garage 100 mecho 100 regions 35 salesman 17 簡単な問題はしっかり解けてて良いが、難しい問題に全く歯が立ってないのが致命傷。
2-SATとは SATとはsatisfiability(充足性)の略で、与えられた論理式を満たす真偽値の組合せが存在することをいう。特に2-SATとは、変数がx_1からx_nまであるとして以下の形の論理式について変数の真偽値の組合せを考える問題である。 ここで 論理積でつなが…
タイトルの通り。
