Source
XOR回廊で使ったジェネレータ。前半部分はgithubにも置きました。自由に使ってください。
http://kupc2012.contest.atcoder.jp/tasks/kupc2012_11# 問題 略 解法 解説参照
http://kupc2012.contest.atcoder.jp/tasks/kupc2012_9# 問題 略 解法 解説参照。デバック時間は測定忘れた。
http://kupc2012.contest.atcoder.jp/tasks/kupc2012_7# 問題 略 解法 解説参照。ソースは平面走査の解答。
http://kupc2012.contest.atcoder.jp/tasks/kupc2012_6# 問題 略 解法 解説参照。
http://kupc2012.contest.atcoder.jp/tasks/kupc2012_5# 問題 略 解法 解説参照。ソースコードが無駄に複雑なのは誤解等を先に作ったため。
http://kupc2012pr.contest.atcoder.jp/tasks/kupc2012pr_4# 問題 略 解法 ヒントに書いてある通り。1000*1000だったので普通の行列乗算でも通ってしまった。
http://kupc2012pr.contest.atcoder.jp/tasks/kupc2012pr_3# 問題 略 解法 3箇所でクエリ投げて式に当てはめるだけ
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=229&page=show_problem&problem=3073 問題 1からnの数列がある。この数列の[a,b]の範囲をリバースして数列の一番後ろにくっつけるという操作をm回行う。最終的な数列を出力…
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=42&page=show_problem&problem=2121 実装:45分 デバッグ:1時間45分 問題 シャフトがn個あり、このシャフト間をベルトで結んでsからeのシャフトを結びたい。ただし…
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=42&page=show_problem&problem=2122 実装:50分 デバッグ:30分 問題 めんどくさいので略。YUHAのACM-ICPC 2007-2009総集編を参照。 解法 英語を読んで、シュミレー…
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2349 設計:1時間 実装:1時間 デバッグ:1時間 TLE解消:2時間 問題 N個の国がある。各国には都市がMi個あり、国際空港がFi個ある。国の間を移動するには国際空港からしかできない。上記の条件で…
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://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=2319 問題 略 解法 片方の経路をfixし、もう一方の経路で最短路を見つける。validな経路はそこまで多くないので枝刈りをすれば間に合う。難しすぎるので詳しいことは略。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2318 問題 略 解法 解説参照。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2317 問題 略 解法 紐をまとめて切るだけ。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2316 問題 略 解法 やるだけ。鋭く凹んでる場合に今の軸の反対側の頂点が次の軸になることがあるので注意。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2315 問題 略 解法 解説参照。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2314 問題 略 解法 解説参照。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2313 問題 略 解法 解説参照。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2312 問題 略 解法 DPで解く。大きい数値は隣接して置いた方が良いので、一番大きい数値を置いた後に、残りの数値を大きい順に左端か右端に順々に置いていけば良い。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2311 問題 略 解法 やるだけ。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2310 問題 略 解法 レーザーを出す角度を使った平面走査で解く。答えが変わる角度はセルの右下の頂点を通る時であるのでそこをイベント点に突っ込む。各イベント点では同じ角度のイベント点を全て…
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つを考えるとエネルギーを右側に全力でかけるか、両方のプレートで同じだけの熱を与えるようにエネルギーを掛けるかの効率の良い方を選択すれば良い。これ…