http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=229&page=show_problem&problem=3150 問題 W*Hの盤面に図のように順番に番号を付け、1番から順に左上から順に並べ直す作業をする。この作業を何回やれば数値が1から順に並ぶ…

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=242&page=show_problem&problem=3155 問題 長さnの順列でバブルソートをした時の交換回数の期待値を求めよ。 1 解法 数値のペアに着目すると2つの値は正順になっているか逆…

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=242&page=show_problem&problem=3154 問題 長さnの数列Aと数値uが与えられる。次に[l,r]の範囲のv未満の数値の個数をkとした時に、a[p]をu*k/(r-l+1)にするクエリがm個来る…

http://poj.org/problem?id=3370 問題 要素数nの数列Aがある。Aの部分集合でcの倍数となっているものを一つ答えよ。 1 1 解法 常に解が存在することを示す。 a1を使用した場合S1=a1%cの値が作れる。a1,...,akの値を使用している時に、ak+1のを使用するとSk+1…

近年のICPC World Finalsの問題を見ていると実装が重い問題が多く、それ用の練習をすべきな気がするけどいい問題集がなかったので自分の見てきた範囲内で集めてみた。ちょっと問題が偏っているけど仕方がない。以下注意書き。 アジア地区予選だと最終防衛問…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2329 実装：40分 デバッグ：10分 問題 n個のマップがある。それぞれのマップにはmi頂点の平面埋め込みされたグラフが与えられる。またマップ間を移動する手段としてワープがあり、ワープを使って…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2384 設計：40分 実装：50分 デバッグ：1時間 問題 うさぎがk匹、岩がn個ある。うさぎは初期位置から岩を順に飛んでいってそれぞれの目的地に行きたい。ただし他のうさぎが踏んだ岩を踏むことは出…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2349 設計：1時間 実装：1時間 デバッグ：1時間 TLE解消：2時間 問題 N個の国がある。各国には都市がMi個あり、国際空港がFi個ある。国の間を移動するには国際空港からしかできない。上記の条件で…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2368 実装：30分 デバッグ：15分 問題 略 解法 まず全ての線分の端点と交点をset,mapに突っ込んでおく。次に各線分に対してsetに突っ込んでいた点が乗っているかチェックして、乗っている場合は距…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2341 問題 単語がn個ある。その単語を重複有りで並べ替えて出来るm文字の文字列でk番目のものを答えよ。ただし、使う単語の順番が異なった場合それは違う文字列とみなす。 1 1 1 解法 解説通りにx…

300 問題文は読みやすいな。 えーととりあえず同じ物どうしでグループ分けして、それを繰り返してスイッチとランプが同じ集合になるか考えれいいんかな。 そうっぽいので実装。logをどう取ればいいか分からんかったんで前計算しておくことしてsubmit。 450 …

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2343 問題 N*N行列に値が入っている。行列を回転させたり、列や行をswapさせる命令や行列のある場所に値を書き込むクエリがQ個来る。全てのクエリをさばいた後に指定された部分行列のハッシュ値を…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2393 問題 H*Wの盤面に仕切りをしいて迷路を作りたい。ただしある地点から別の地点への行きたかはちょうど一通りなければならい。迷路の作り方は何通りあるか？ 1 1 解法 迷路の作り方は全域木の…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=43&page=show_problem&problem=2454 問題 ウィンドウがn+1個ある。一つ外側のウィンドウがリサイズされると、内側にあるウィンドウは幅やウィンドウとの距離を一部…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=43&page=show_problem&problem=2452 問題 2*M枚のカードをルールに従って山を作るように互いに置いていく。どちらが勝ち、スコアの差分がどうなるか求めよ。 5 解法…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=44&page=show_problem&problem=2786 問題 APLのインタプリタを作れ。式は全て右から評価すること。 (例えば - / 1 2 3 は (1 - (2 - 3))=2という意味) invalidな入…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=44&page=show_problem&problem=2790 問題 H*Wの盤面があって、そこに左下から右下へ運河を作る。運河の長さを最大化せよ。 答えは一意に定まる。 2 2 解法 一行分ど…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=511&page=show_problem&problem=3723 問題 さめがめの最大得点を求めよ。 幅、高さ 色の数 解法 全探索＋枝刈りで解く。枝刈りは残ってる色の個数をそれぞれ二乗し…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=511&page=show_problem&problem=3718 問題 頂点数n、枝数mのグラフGが与えられる。グラフの辺は最初壊れていて、それを直すのにコストwiかかる。1番目の頂点からk番…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1089 問題 略 解法 ConvexCutを使えばケーキをある角度で切った時の面積はでる。ここで角度0と角度PIで切った時、その左側の面積が片方は半分以下になり、片方は半分以上になる。なので中間値の定…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2367 問題 略 解法 てきとうにはしょりながら文字列を全部展開して、すべての部分文字列とstrstrで存在するかどうかを比較した。はしょる方法は400文字以上の繰り返しは繰り返し回数を適当に減ら…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2385 問題 m頂点の凸多角形の街がある。その街にはシェルターがn個ある。ある人がどの場所にいる確率も一様な時、シェルターまでの最短距離の二乗の期待値を求めよ。 3 1 座標 解法 ボロノイ図を…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2374 問題 略 解法 忘れた。たしか多い方からgreedyに取っていきつつ、取っていった分をずらしてごにょごにょすれば行けた気がする。 下のコードはたしかm-judgeではTLEしたけど、AOJでは通った。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2380 問題 図の様なパズルがあるので最短何手でクリア出きるか答えよ。答えが6以上になる場合は-1を出力すること。 解法 反復深化とか幅優先探索てきとうに。間に合わない場合はてきとうに最後の…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2372 問題 略 解法 Fib(10)くらいまでのIka Numberの表を2次元で書き下してみると法則性が分かるので後は実装するだけ。