KUPC
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箇所でクエリ投げて式に当てはめるだけ
今年もKUPCのジャッジをやっていました。今回原案を担当した問題はF,I,Kです。 去年の反省からDまでしか解けなくて暇になることが無いようにF以降の問題には部分点を入れています。また、KUPCでは実装が重い問題は出さずに、解法が思いつくまでに時間のかか…
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つを考えるとエネルギーを右側に全力でかけるか、両方のプレートで同じだけの熱を与えるようにエネルギーを掛けるかの効率の良い方を選択すれば良い。これ…
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2277 問題 略 解法 1が返ってくるまでランダムな列をクエリに投げる。1が返ってきたら後は2分探索すれば良い。2回目以降は動作していると分かっているビットには0を入れておくこと。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2276 問題 略 解法 まず地点を[0,PI]の区間に直す。次に明らかにいらない区間を全て削除する。後はDPをすれば良い。普通にDPするとO(N^2K)かかるが、その区間を選ぶよりも明らかに良い区間がある…
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2275 問題 略。 解法 区間篩 or Fox Numberでない数を全列挙。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2274 問題 略 解法 validな列になるまで列をランダムで構成する。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2273 問題 略 解法 解説参照。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2272 問題 略 解法 DPするだけ。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2271 問題 略 解法 やるだけ。
KUPCのジャッジをやっていました。主に問題の作成とテストをしてました。てきとうに感想などを書きます。 大規模なコンテストの主催者側に回るのは初めてなので割と楽しめました。特に本番中は他の人の解答を見て遊んでた気がします。 コンテストの問題に無…