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人が順番に空砲を撃って、その…