http://poj.org/problem?id=3659 問題 n頂点の木が与えられる。全ての頂点との距離が1以下となる頂点集合の最小サイズを求めよ。 1 解法 dfsで各頂点の深さを求めて、深い方から順にその点がまだカバーされてなかったら親の頂点を頂点集合にいれていく。
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=528&page=show_problem&problem=3917 問題 人がn人いて、それぞれ(xi,yi)にいる。ある人が、ある人の銃声を別の人の銃声よりも早く聴いたという情報がm個与えられる…
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=528&page=show_problem&problem=3916 問題 w*hのグリッドにプールを作りたい。#のセルを.に変えるコストはd、.のセルを#に変えるコストはf、最終的な状況で#と.のセ…
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=528&page=show_problem&problem=3914 問題 図のようなブロックを使って指定されたように敷き詰めることができるか？ 1 解法 まず、白のブロック数が黒のブロック数…
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=518&page=show_problem&problem=3820 問題 0,1で構成されるm*n行列がある。隣り合う要素同士をswapすることによって各行、各列にある1の個数を同じにしたい。swapの…
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2962 問題 m種類の文字から構成されるn文字の文字列が与えられる。また2つの文字を合成した時にどの文字が何分でできるかの表も与え…
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個来る。全てのクエリをさばいた後に指定された部分行列のハッシュ値を…
