http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2964 問題 3面ダイスが3個ある。それぞれのダイスの1,2,3が出る確率も分かっている。この3つのダイスを降る確率を適当に決め、別の3…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2963 問題 頂点数nの木がある。各辺にはドアがあり、鍵の必要な物がある。鍵が必要なドアはC個あり、各ドアには色がついていて同じ…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2961 問題 n頂点のグラフが与えられる。全域木の中で使ってる辺のコストの最大値-最小値の最小値を求めよ。 2 解法 辺を重み順にソ…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2960 問題 n頂点のグラフが与えられる。そこの頂点のどこかに猿がいるので撃ち殺したい。猿を殺すために銃を撃つと、猿がそこに居な…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2958 問題 オンラインジャッジのスコアボードの、各行と各列に何個ACがあるかの情報が与えられる。スコアボードを修復せよ。複数の…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2957 問題 n*n行列A,Bが与えられる。A*A=Bとなるかどうか判定せよ。 1 Aの各成分は10以下。 解法 乱択アルゴリズムで解く。詳しくは…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2955 問題 横方向と縦方向に芝をかる。それぞれの方向で、全ての場所の芝が刈られるか答えよ。 解法 英文読んでやるだけ。

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2959 問題 AGTCからなるn文字の文字列Sがある。各文字は一文字だけ前後(AをGとかCに)に変更ができるが、隣接した物を同時に変更する…

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=229&page=show_problem&problem=3073 問題 1からnの数列がある。この数列の[a,b]の範囲をリバースして数列の一番後ろにくっつけるという操作をm回行う。最終的な数列を出力…

今回は落ちなかった。 A,B,C やるだけ。 AでC言語直打ちしたらexit(0);忘れて無駄にRE食らった。 D とりあえず前に敵が居ない場合とかは適当に処理するとして、それ以外の場合ってどうすんの？ 1歩前に進んだら後ろの奴が1歩ずつ進めるようになって、敵はそ…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=42&page=show_problem&problem=2121 実装：45分 デバッグ：1時間45分 問題 シャフトがn個あり、このシャフト間をベルトで結んでsからeのシャフトを結びたい。ただし…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=42&page=show_problem&problem=2122 実装：50分 デバッグ：30分 問題 めんどくさいので略。YUHAのACM-ICPC 2007-2009総集編を参照。 解法 英語を読んで、シュミレー…

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 問題 さめがめの最大得点を求めよ。 幅、高さ 色の数 解法 全探索＋枝刈りで解く。枝刈りは残ってる色の個数をそれぞれ二乗し…