http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=511&page=show_problem&problem=3718 問題 頂点数n、枝数mのグラフGが与えられる。グラフの辺は最初壊れていて、それを直すのにコストwiかかる。1番目の頂点からk番…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1089 問題 略 解法 ConvexCutを使えばケーキをある角度で切った時の面積はでる。ここで角度0と角度PIで切った時、その左側の面積が片方は半分以下になり、片方は半分以上になる。なので中間値の定…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2367 問題 略 解法 てきとうにはしょりながら文字列を全部展開して、すべての部分文字列とstrstrで存在するかどうかを比較した。はしょる方法は400文字以上の繰り返しは繰り返し回数を適当に減ら…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2385 問題 m頂点の凸多角形の街がある。その街にはシェルターがn個ある。ある人がどの場所にいる確率も一様な時、シェルターまでの最短距離の二乗の期待値を求めよ。 3 1 座標 解法 ボロノイ図を…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2374 問題 略 解法 忘れた。たしか多い方からgreedyに取っていきつつ、取っていった分をずらしてごにょごにょすれば行けた気がする。 下のコードはたしかm-judgeではTLEしたけど、AOJでは通った。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2380 問題 図の様なパズルがあるので最短何手でクリア出きるか答えよ。答えが6以上になる場合は-1を出力すること。 解法 反復深化とか幅優先探索てきとうに。間に合わない場合はてきとうに最後の…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2372 問題 略 解法 Fib(10)くらいまでのIka Numberの表を2次元で書き下してみると法則性が分かるので後は実装するだけ。

A問題 SubstringとSubsequece 普通にやるとn^3くらい掛かりそうだけど適当に節約したらn^2に収まった。 書いた。submit。pretest AC。 B問題 レミングスの問題。 ソートして順番に取ってとかあれこれ考えたが分からんから、とりあえず飛ばした。 C問題 チョ…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2373 問題 略 解法 とする。どの長さを使うかと、どの様に並べるかは全探索する。その二つが決まったらを制約条件の下で求め目れば良い。これはラグランジュの未定乗数法を使うと解くことが出来、…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2379 問題 サイコロの展開図が8個ある。そのサイコロを8個を組み合わせて2倍の大きさのサイコロを作りたい。作るときの条件は サイコロの内側は黒色 サイコロの1つの表面の色は統一されている サ…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2386 問題 N頂点の完全無向グラフがある。ハミルトンパス出きるように辺に向きをつけたい。辺の向きを付ける時のコストを与えるのでその様なグラフを作るときの最小コストを求めよ。 1 0 解法 完…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2383 問題 ステージがN個ある。全てのステージをプレイしたいのだが、以前クリアしたステージの難易度-Tよりも簡単なステージはプレイできない。ステージの並べ方は何通りか？ 1 解法 ステージを…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2382 問題 W,Hのフィールドに居るN体のスライムを蹴って、一箇所に集めたい。スライムは一度蹴ると端か他のスライムに当たるまで止まらない。また蹴ったスライムが他のスライムに当たると2体は合…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2376 問題 略 解法 dp[odd][even][e]を計算して解く。oddは頂点の数が奇数の連結成分の個数、evenは頂点の数が偶数の連結成分の個数、eは連結成分内でまだ使用してない辺の個数の偶奇を表す。eの…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2370 問題 略 解法 まずグラフを2彩色出来なければ答えは-1になる。2彩色できたら各連結成分に白の数と黒の数のminと差を記憶しておく。追加する辺の数を最大にするには2部グラフの片側に何個頂点…

250 偶奇を見るだけ。 mod2が負の数にならないように注意して書いた。 450 角度全部見るだけでは？ 書いた。submit。 一応全探索と比較して一致することを確認。 1050 実装がめんどくさそうな問題 Challenge Phase 250で負の数で死んでる人がいそう 一人いた…

A問題 ソートしてgreedyにやるだけじゃん。 書いた。submit。pretest WA。なんか言ってるし、とりあえず放置。 B問題 割引されるのは一番高くてもstoolの商品なんで、一個ずつ入れるのが良い？ これもソートしてgreedyにやるだけじゃん。 書いた。submit。pr…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=397&page=show_problem&problem=2953 問題 図の様な入力と出力が2^n個あるスイッチ式の変換器で電話網を繋げる。m個の条件を満たすような変換の仕方をした時に、各…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=397&page=show_problem&problem=2948 問題 制限速度がvmaxの山道を通ってなるべく速く家に帰りたい。ただし燃料が少ないのでそれを考慮に入れなければならない。ス…

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=279&page=show_problem&problem=3864 問題 C種類のpi円の車がci個ある。一度使った車はサービスセンターで修理をしないと以降使うことはできない。修理の種類はR個あって、…

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=279&page=show_problem&problem=3868 問題 頂点数Nの森が与えられる。K個の頂点を訪れるのに何回辺を通る必要があるか聞くクエリがq個来るので全て捌け。 1 解法 前処理とし…

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=279&page=show_problem&problem=3867 問題 問題分に書いてあるようなクエリ(ある区間に1次関数を足す、ある区間の値をxにする、ある区間のsumを取る)がq個来る。全て捌け。 …

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=279&page=show_problem&problem=3866 問題 N人の人が2次元上にる。全ての人の耳の良さは同一であり、半径R以下の距離でなった音が聞こえる。N人が順番に空砲を撃って、その…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=519&page=show_problem&problem=3997 問題 N人で総当たり戦を行う。それぞれの人に対して整数aiが与えられる。それぞれの人の勝利数をbiとした時に、を求めよ。ただ…

300 やるだけ問題きた。 でも気をつけておかないとコーナケースで落ちる系と見た。 端がない場合とか真ん中がない場合とかに気をつけて書いてみた。 450 この手の問題にしてはやたらN,M,Kが小さいなあ。 K個先までしか見ないからそこの値保持しておけばいい…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=408&page=show_problem&problem=2885 問題 図のようなチェインコードで境界が与えられるので内部の黒点の数を答えよ。 チェインコードの長さ 解法 チェインコードを…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=408&page=show_problem&problem=2886 問題 n個タスクがある。以下の2つのタイプの制約ある。 タスクiはタスクjの終了後A分以降にやらなければならない。 タスクiは…

21:10開始と思ったら21:05から開始したよ。 300 え、これDPやるだけなんじゃあ。 書いた。合わない。サンプル見たら最低1回ずつは聞かないとダメという条件忘れてた。 てきとうに直せばいけるだろう。…。包含原理を使えばあーなって…。 サンプル一致したんで…

http://codeforces.com/problemset/problem/145/E 問題 4,7で構成される長さnの列がある。m個のクエリが来るのでさばけ。クエリは次の2種類。 区間[l, r]の4と7を反転させるクエリ。 区間[1, n]の非単調減少列の長さを答えるクエリ。 1 1 解法 セグメントツ…

A問題 Lucky Number回ですか。 幅優先探索をしようと思ったら数値が10^5以下じゃなくて文字列の長さが10^5以下だった。 greedyにやるだけなんで書いた。submit。pretest AC。 C問題 DPっぽいけどO(nk)は死ぬなあ。 Lucky Number以外はまとめて良くて、Lucky …