http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2280 問題 略 解法 解説参照。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2279 問題 略 解法 列・行は別々に解いて良い。山を構成できるかどうかはN個のベクトルの半順序を計算し、DAGにした後、ルートが存在するかどうかと、そのDAGが2つのパスで被覆できるかを2部グラ…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2278 問題 略 解法 一番左端のプレート2つを考えるとエネルギーを右側に全力でかけるか、両方のプレートで同じだけの熱を与えるようにエネルギーを掛けるかの効率の良い方を選択すれば良い。これ…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2277 問題 略 解法 1が返ってくるまでランダムな列をクエリに投げる。1が返ってきたら後は2分探索すれば良い。2回目以降は動作していると分かっているビットには0を入れておくこと。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2276 問題 略 解法 まず地点を[0,PI]の区間に直す。次に明らかにいらない区間を全て削除する。後はDPをすれば良い。普通にDPするとO(N^2K)かかるが、その区間を選ぶよりも明らかに良い区間がある…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2275 問題 略。 解法 区間篩 or Fox Numberでない数を全列挙。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2274 問題 略 解法 validな列になるまで列をランダムで構成する。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2273 問題 略 解法 解説参照。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2272 問題 略 解法 DPするだけ。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2271 問題 略 解法 やるだけ。

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3560 問題 n人の人がいて掲示板に発言を書きこんでいく。それぞれの人はsignatureと発言を持っている。掲示板に発言を書きこむのは直前の発言をした人以外で出てきた人である。次に書きこむ確…

300 ボードを斜めにする問題 やるだけ？メモ化再帰で書いてみた。submit。 525 グラフの問題。 16ってことはbitDPとかそれ臭い。 しかし一人に一個ずつ伝えるとか状態遷移が訳わからんすぎる。(間違い) うーむ、分からん。枝刈り探索でやってしまえ。 書いた…

来年以降に海外の地区予選に行く人のために2011年度台湾大会の話を書いておきます。 だいぶ前 国内予選で学校別で2位になって、ACM日本支部から海外のアジア地区予選に行くための補助がでるらしかった。ということで補助が出るからには行かない理由は無いと…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=387&page=show_problem&problem=3098 問題 無限の長さと高さがある万里の長城がある。万里の長城を通って向こうに行くためには万里の長城に穴を掘るしか無い。人がN…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=387&page=show_problem&problem=3096 問題 N頂点,辺数Mの有向グラフGが与えられる。各辺には容量cと重みaが与えられる。この辺には整数の水を流すことができ、かか…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=387&page=show_problem&problem=3095 問題 n*m行列が与えられる。行列の(i,j)の要素をcijと書いた時にL 1 1 1 解法 制約をlogを取って書き下すと となる。この大小…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=387&page=show_problem&problem=3093 問題 順列Pでai>iとなっている物の数をE-valueと呼ぶ。長さNの順列でE-valueがkの物の数を求めよ。 1 0 解法 Eulerian Number…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=387&page=show_problem&problem=3089 問題 頂点数nの木の上で二人で旅行のルートを決める。旅行のルートの長さは[L,R}以内に入ってなければならない。アリスは条件…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=353&page=show_problem&problem=2759 問題 矩形の穴が空いた矩形のポスターをn枚窓に貼り付ける。ポスターは重なって貼ることもある。最終的にポスターが張られてい…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=353&page=show_problem&problem=2763 問題 P2Pのファイルネットワークがある。ネットワーク上には初期状態でサーバが複数台あり、クライアントも複数台ある。各クラ…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=353&page=show_problem&problem=2761 問題 頂点数n、辺数mのグラフが与えられる。このグラフ上で二人でゲームをする。各手番で先手はグラフの辺を赤に塗り、後手は…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=353&page=show_problem&problem=2762 問題 ある金額kの商品は以下のルールで交換できる。 k-1毎の金貨を支払う 同じ額の商品と交換する 別の商品+ある一定枚数のコ…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=353&page=show_problem&problem=2755 問題 ゾンビを使って5*5のプラントを破壊したい。プラントを壊す方法は2種類ある。1つ目はある行の防御力の合計よりも高い攻撃…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1317 問題 換字暗号により暗号化された文がある。使用されえる単語をn個与えるので復号しろ。 1 解法 暗号文の単語に含まれる文字の種類が多い順にソートしてバックトラックで解く。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1324 問題 頂点数nで重み付きの辺がm本でさらに各頂点に通行料feeと高さhが与えられた有向グラフが与えられる。始点(fee=0,h=0)から終点(fee=0,h=1000)まで往復したい。ただし、通行料を取られる…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1318 問題 辺数nのグラフが与えられる。srcからdestまで行きたいのだが途中でLGPガスを補給する必要がある。車の燃料タンクにはcap分だけLGPガスを搭載できる。またLGPガスステーションはグラフ中…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1316 問題 ドーナッツに文字が書かれている。文字を8方向のいずれかで見た時に、2回以上でる文字列でかつ最も長いものを答えよ。2つ以上ある場合は辞書順最小のものを答えよ。 3 3 解法 全列挙す…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1315 問題 各個人の部屋に入った時間と出た時間が与えられる。プログラムの女神と一緒に最も長く部屋にいた人の時間をtとする。そのような人の数*tを求めよ。 解法 やるだけ。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1322 問題 数式を与えるので計算しろ。 解法 上端、下端、右端を持ってパースするだけ。分数を見つけたら適当に上下に分割する。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1321 問題 マインスイーパーの盤面を与えるので爆弾を置く数を最小化しろ。 1 ヒントの数 爆弾を置けるのは*かヒントの位置 解法 各数値の周り9マスを順番に見る＋どこまで見たかと数値の周りにあ…