http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4820 問題 数値がn個ある。長さ1の区間(左端は含み、右端は含まない)で全ての数値をカバーしたいのだが、何個の区間が必要か？ n 解法 greedyにやるだけ。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4819 問題 プログラミングコンテストがN個、問題がM問ある。各コンテストでは使える問題とコンテストで使用する問題の数が決まっている。同じ問題は使わないという条件下で最大何個のコ…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4818 問題 線分がN個ある。([0,L],0)のどこかを中心とした線分と交わらない円を書きたいのだが半径の最大値はいくらになるか？ 1 0 -20000 解法 円の中心を(x,0)とした時の半径の大きさ…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4817 問題 式を与えるのでパースして計算せよ。ただし、0除算、計算途中で90桁を超える、負の数になる場合はErrorと出力せよ。 演算子の個数 解法 パースして、多倍長整数を使って計算す…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4816 問題 幅m、高さnの行列がある。行列の各列を掛けた時に最大となる列はどこか？ 1 1 行列の各数値は32bit-signed integer 解法 負の数を扱える多倍長整数で解いた。負の数を別処理し…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2221&lang=jp 問題 略 解法 一番上の列から始めて、左から右の順に押すボタンを決めることにする。そうすると直前の5つのボタンの押し方が分かっていればボタンの左上にあるマスの得点…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2220&lang=jp 問題 略 解法 解法は主に3通りある。 1つ目は二部探索により実数解をひとつ見つけ、その解を使って次数を一つ落として二次方程式の解の公式を使って解く方法。 2つ目はカ…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2219&lang=jp 問題 略 解法 各能力値ごとにナップサック問題を解く。C問題より楽な気がするけど実際にはCより解かれてない。まあ私が1回生の時には解けなかったことを考えると当然かも…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2218&lang=jp 問題 略 解法 実装ゲー。ストレート、フラッシュの判定と各手札の枚数を数えて役をチェックすると楽。ストレートの判定の部分をミスって1WAした。出題の意図としては、ア…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2217&lang=jp 問題 略 解法 全てのマスに対してdfsを行い、現在のdfsで訪れたマスにきた場合はループのカウントをする。他の探索で訪れていた場合は無視する。

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2216&lang=jp 問題 略 解法 やるだけ。皆O(1)でやると思ってたらO(n)でやってる人が結構いてびっくりした。

nodchipさんと同じ部屋。 300 問題を読む。 +は2倍、*は二乗、-は0に/は0以外だと1になると。そもそもtが1以上だから-を使う必要は無くて、/を使う場合は最初に使うのが最適。 +,*の場合は数値は少なくとも2倍ずつは増えていくんで幅優先探索で全部調べれば…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2667 問題 チェス盤の上にピースが4つ置いてある。プレイヤーは1手ごとにピースを上下左右に移動させることができる。また、移動先にピースがある場合は1個だけ飛び越えて移動することが…

https://www.spoj.pl/problems/TOURS/ 問題 頂点数nの有向グラフが与えられる。このグラフを閉路に分割したいのだが、全ての頂点を使って、なおかつ各閉路の使用する頂点は重なってはいけない。そのような分割の仕方で最小のものを求めよ。 1 解法 各頂点を2…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2685 問題 都市がn個ある。汚水を処理して川に流したいのだが、自分の都市で処理するか、下流、上流の都市に処理してもらう方法がある。都市間につながっているパイプは一方向にしか水を…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2684 問題 L*Cのサイズの文字列とW個のパターンが与えられる。L*Cの文字列を縦、横、斜めの8方向どの方向から見ても良いのでパターンを探し出す。各パターンの出現位置を一つ求めよ。 0 …

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2663 問題 数値がciと振られた区間がn個与えられる。数値の集合Zで各区間との共通部分を取った時サイズがci以上となるものの最小のサイズを求めよ。 1 0区間 解法 区間を右端が小さい順…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2680 問題 整数nと文字列sが与えられる。sの長さnのsubstringは何種類あるか？ s 解法 Suffix Array。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3908 問題 コンピュータのプログラムを使ってn個の線分で図形を書いていく。線分は方向dと長さfを使ってプログラムに入力する。このプログラムは線分が交差やオーバーラップすると、その…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3907 問題 Aから順番にn種類の文字が使えるパズルを行う。このパズルにはs種類の禁止ワードがある。前から順番に文字を出していき、禁止ワードを作らないように文字を並べていく。そうし…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3906 問題 直流回路が2つある。直流回路の中にはシグナルを生成する素子が何個か存在する。回路が直列になっている場合はシグナルはそのまま繋げたものが出力される。並列になっている場…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3905 問題 隕石がn個ある。各隕石には初期位置と速度が与えられる。隕石の位置が0 解法 各隕石についてどのタイミングで、撮影可能になって、どのタイミングで撮影不可能になるかをすべ…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3904 問題 2*nの領域に1*2、2*1、2*2のタイルを敷き詰めたい。タイルの敷き詰め方は何通りあるか？ただし、左右でひっくり返して同じになる場合は同じ置き方とみなす。 3 解法 DPですべ…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3903 問題 携帯電話で電話番号を押したときの指の軌跡を表現するためには線分が何本必要か？ 5 解法 軌跡がマージできる部分を同じ数値とみなしたテーブルをつくりsetとかで出現回数を数…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3902 問題 頂点数nの木がある。木の葉はクライアントで、各クライアントはVODサーバから距離k以内に存在しないといけない。オリジナルのVODサーバは初めからひとつ存在する。最低何個の…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3901 問題 最長共通部分文字列の長さを求めよ。 文字列の長さ 解法 Suffix Arrayを使ってlcpを求める。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3900 問題 C,H,O,Nからなる分子式を与えるのでモル質量を求めよ。 0分子式の長さ 2分子式に出てくる数値 解法 やるだけ。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2666 問題 n台のコンピュータで構成されるネットワークがある。ネットワーク上の各コンピュータにはランクrが振られていて、それに応じてお互いのコンピュータの情報を持ち合う。あるコ…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2327 問題 連結で単純な平面グラフを与えるので、長さkの閉路で内部に頂点、辺を含まない物は何個存在するか。 3 x,y 解法 まず、各頂点の辺を角度順にソートする。次に開始地点の枝を決…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2326 問題 図のように部屋と廊下がある。各部屋間で机を移動させたいのだが、その部分の廊下が使われている場合は同時に机を移動させることは出来ない。最低何分で全ての机を移動させる…