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マスを順番に見る＋どこまで見たかと数値の周りにあ…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1314 問題 matlabの演算を実装しろ。 解法 やるだけ。indexed-primaryとtransposed-primaryはprimaryの直後にwhileループで実装する。スカラーも行列型で実装すると楽。

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=521&page=show_problem&problem=3735 問題 二部探索木がdfs順序で与えられる。その二部探索木をdfsで戻る時順に値を出力せよ。 ノード数 ノードの値 解法 dfs順序か…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=521&page=show_problem&problem=3740 問題 20*20の盤面に最大5個の長方形の大陸がある。大陸の大きさの合計は25である。大陸を動かして正方形を作りたいが最小何回…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=521&page=show_problem&problem=3737 問題 t以下の素数しか無いと考えた時にn桁の双子素数となる物の小さい方を答えよ。 3500 t 解法 tが小さいのでn桁目の最初の1…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=521&page=show_problem&problem=3736 問題 変数がn個、集合がm個ある。各集合Siのサイズは2または3である。変数に0または1を割り当てる時、全ての集合に0と1の両方…

250 素数の問題 素数じゃなかったら1回で終了。素数だったら1引けばいいだけ。 素数判定するだけじゃん…。ミラーラビンをコピペする。 おっと3の場合は答えが3になるな。 とりあえず書いた。submit。 1000 どうせ1000か500のどちらかしか解けないんで両方開…

codeforces見たら昼間からあったので参加してみた。 A問題 問題が読めない。 なんかおかしいと思ったらstatuesをstatusと読んでた。 やるだけ。submit。pretest WA。 移動しない場合を忘れた。submit。pretest AC。 C問題 こっちの方が簡単そうなんで手をつ…

本番 いもすさんがテンプレ打ち込んでいる間にAとBを読む。Aが先に読めて少しめんどいやるだけ問題だったんでいる君にやってもらう。その間にBが読めてBの方が簡単だったのでBに移行して書く。AC。 Cは計算量が分かんないけど探索で解けそうだったが、Dが拡…

前日に国際会議用のスライドを作ってて寝ずに参戦。いる君もほとんど寝てなかったらしい。 始まるまで なんかPC^2の調子がおかしいらしくて開始時間がずるずる伸びる。しまいにはatcoderですることに。その間はだべったり、自己紹介したりで時間をつぶした。…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=22&page=show_problem&problem=2000 問題 遺伝子がn個あり、それぞれの長さはliである。共通部分の長さの最大値を答えよ。 li 1 解法 間に0,1,2,...と挟んで各文字…