http://poj.org/problem?id=3659 問題 n頂点の木が与えられる。全ての頂点との距離が1以下となる頂点集合の最小サイズを求めよ。 1 解法 dfsで各頂点の深さを求めて、深い方から順にその点がまだカバーされてなかったら親の頂点を頂点集合にいれていく。

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

http://poj.org/problem?id=3411 問題 N頂点、辺数mの有向グラフが与えられる。各辺は頂点cに行ったことがあるならばコストPi、そうでないならばRiで通れる。頂点1から頂点Nまで行く最小コストを求めよ。 N,m 解法 たどり着いた街が同じ場合はn歩までしか歩…

http://poj.org/problem?id=2546 問題 2円の共通部分の面積を求めよ。 解法 ライブラリを使って終了。 ライブラリは続きを読むに置いてみた。

http://poj.org/problem?id=2545 問題 素数p1,p2,p3から構成される数値の列でn番目の物を答えよ。 p1,p2,p3,n,答えは全て10^18未満 解法 10^18未満にそのような数値は64^3個も存在しないので、オーバーフローに注意しながら全て列挙すれば良い。

http://poj.org/problem?id=2543 問題 エクセルの表っぽいやつが与えられるのでA1の値を計算せよ。 解法 最初に入力を全部読んで、メモ+構文解析。 空行があり、N行分の入力が存在しない場合があるので注意。

http://poj.org/problem?id=2542 問題 トランプの6〜Aを使ってカードゲームを行う。まず先手がカードを1枚場に出す。以降次の操作を繰り返す。 後手はそのカードに勝つカードを1枚場に出す。その次に先手は場に出ているカードと同じランクのカードを出す。 …

http://poj.org/problem?id=2541 問題 魔法使いが天気予報を行う。a日からのt日間が最近t日と同じ天気の変動をしている場合、明日の天気はa+t日目の天気と一致する。そのような列が複数ある場合は最も最近のものを採用する。そのような列がない場合はt=13,12…

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

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=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日進めるか、もしくは次の月の同じ日付が存在すればその日に日にちを進めることができる。そうして交…

http://acm.pku.edu.cn/JudgeOnline/problem?id=3043 問題 H*Wのグリッド上に文字が書かれている。グリッドの上では左と下には行けず、右や上の方にいく場合は何マスでもジャンプできる。このグリッド上で辞書に載っている単語を作るパスは何通りあるか？ 1 …

http://acm.pku.edu.cn/JudgeOnline/problem?id=3042 問題 直線上に牧草がN個ある。それぞれの牧草を食べるまでの時間の和を最小化したい。自分の初期位置がLの時、最小値はいくらか？ 1 1 解法 メモ化再帰で解く。 calc(dir, left, right)は左側はleftまで…

http://acm.pku.edu.cn/JudgeOnline/problem?id=3046 問題 T種類の数値がそれぞれNi個存在する。それらの数値を使って大きさS〜Bの集合を作りたい。何種類の集合の作り方が存在するか？ 1 1 解法 DPで解く。 DP[i][j]はi種類目の数値までを使って大きさjの集…

http://mirac.jp:8080/cgi-bin/pku_prob.cgi?nosub=1&id=3041 解法 NxNの宇宙空間に小惑星がK個ある。行または列にある全ての小惑星を蒸発させることのできる強力な兵器があり、その兵器を用いて小惑星を全て破壊したい。最低何回兵器を使わなければならない…

http://acm.pku.edu.cn/JudgeOnline/problem?id=3045 問題 牛たちN頭が縦に乗っていく。各牛の重さがWi,強さがSiで与えられたとき、その牛が崩れるリスクはその牛の上に乗っている全ての牛の重さの合計からその牛の強さを引いた物である。牛を最適に並べると…

http://acm.pku.edu.cn/JudgeOnline/problem?id=3189 問題 牛がN頭、牛が何頭か入る家畜小屋がB個ある。 それぞれの牛たちには家畜小屋の好みのランクがあり、牛たちの間でなるべく不公平にならないようにしたい。 牛を全て小屋に入れたときに、それぞれの牛…

http://acm.pku.edu.cn/JudgeOnline/problem?id=3725 問題 1〜nまでの数字を辞書順に並べた時、mがk番目の数値となるとする。k,mが与えられるので最小のnを求める問題。 1 解法 nを二部探索し、nを固定した場合にmが何番目にくるかを考える。 1〜nまでの数字…