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 問題 図のように部屋と廊下がある。各部屋間で机を移動させたいのだが、その部分の廊下が使われている場合は同時に机を移動させることは出来ない。最低何分で全ての机を移動させる…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2325 問題 図にあるようにフリップの操作とシフトの操作ができるトラックが存在する。黒のディスクと白のディスクを分離できるか？ 10 解法 よく見るとフリップの操作は1つ飛ばしのスワ…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2324 問題 2つのDNAを与えるので類似度を求めよ。 1 解法 DP。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2323 問題 係数が0か1しかないd次関数f(x),g(x)が存在する。h(x)=f(x)g(x)としたときh(x)を求めよ。ただし、係数はmod2をとる。 d 解法 多項式ライブラリを使って普通に多項式のかけ算を…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2322 問題 木の棒がn本存在する。木には長さlと重さwが存在する。この木を整形する機械があるのだが、機械の準備をするために1分かかってしまう。しかし、直前に整形した木よりも長さも…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2321 問題 カレンダーを使って二人でゲームを行う。手番のプレイヤーは現在の日付を1日進めるか、もしくは次の月の同じ日付が存在すればその日に日にちを進めることができる。そうして交…