http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2393 問題 H*Wの盤面に仕切りをしいて迷路を作りたい。ただしある地点から別の地点への行きたかはちょうど一通りなければならい。迷路の作り方は何通りあるか? 1 1 解法 迷路の作り方は全域木の…
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=43&page=show_problem&problem=2454 問題 ウィンドウがn+1個ある。一つ外側のウィンドウがリサイズされると、内側にあるウィンドウは幅やウィンドウとの距離を一部…
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=43&page=show_problem&problem=2452 問題 2*M枚のカードをルールに従って山を作るように互いに置いていく。どちらが勝ち、スコアの差分がどうなるか求めよ。 5 解法…
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=44&page=show_problem&problem=2786 問題 APLのインタプリタを作れ。式は全て右から評価すること。 (例えば - / 1 2 3 は (1 - (2 - 3))=2という意味) invalidな入…
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=44&page=show_problem&problem=2790 問題 H*Wの盤面があって、そこに左下から右下へ運河を作る。運河の長さを最大化せよ。 答えは一意に定まる。 2 2 解法 一行分ど…
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=511&page=show_problem&problem=3723 問題 さめがめの最大得点を求めよ。 幅、高さ 色の数 解法 全探索+枝刈りで解く。枝刈りは残ってる色の個数をそれぞれ二乗し…
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とした時に、を求めよ。ただ…