https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=346&page=show_problem&problem=2504 問題 略 解法 忘れた

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1339 実装：23分 問題 トーラス上で3x3のスライドパズルをするので最短手数を求めよ。 解法 やるだけ。状態管理が遅くてTLEになったのでunordered_mapとか使った。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1337 実装：15分 問題 矩形で領域が複数の箇所に分割されている。何分割されているか求めよ。 1 0 解法 nが小さいので座標を2倍して座標圧縮した後にBFSで領域を数えた。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1336 実装：7分 問題 n匹のアリが長さlのトンネルの中を歩く。 トンネルの中は整数座標以外ではアリ同士はすれ違うことができるが、整数座標の場合はぶつかってそれぞれのアリが反対を向く。 アリ…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1335 実装：4分 問題 n以下の数がちょうどk個であるような集合で、数値の和がsになるのは何通り？ 1 1 1 解法 数値が小さいのでn,k,s全部をキーにしたDPをした。

環境が変わったのでちょっとテストしてから本番へ。 250 ループ回すだけ。 Round1ってこんなに簡単だったけ？ 500 かえるジャンプ 1ずつ増やして確かめれば良くない？と思ったら浮動少数だった。 2分探索は使えんよなあ。 この手の問題は限界を攻めるのがパ…

https://www.spoj.pl/problems/CARDSHUF/ 問題 [1,N]までの数列に対して、i番目の数値をj番目に移動するという操作をM回繰り返す。最終的にできた数列を元の数列に戻すのに何回操作を行わないといけないか答えよ。 1 解法 平衡二分木でO(logN)で操作を行い最…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0553 問題 略 解法 尺取メソッドでやる。 潜れる場合は何も考えずに潜る。潜ると死ぬ場合は、headとtailの間で回復量最大の泉で回復する。HPの上限に達する場合は2番目に回復量が大きい泉と比較し…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=350&page=show_problem&problem=2531 問題 携帯型原子力発電機で街の各家庭に電力を供給したい。発電機からの距離がl以下の時にその家には電力が供給される。1台の…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=322&page=show_problem&problem=2267 問題 右方向にr個、左方向にq個止まる候補の箇所がある。各箇所はxiの場所にあり時間t1ｎそこに行くとmax(0, pi-t)の利益を1度…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=293&page=show_problem&problem=2013 問題 Nに含まれる桁の数値を全て含む数値をFriend Numbersと呼ぶ。範囲[A,B]の中でK番目のFriend Numbersを求めよ。 1 解法 dp…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2301 問題 シンプルなゲームをするので自分が何点差で勝つか求めよ。 1 石の数の合計 解法 αβ法でやるだけ。 注意点とか細かいルールは以下のとお…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2298 問題 m*nのグリッドがある。各マスで上下左右に移動する確率を与えるので、(1,1)から(m,n)まで行くのに掛かる時間の期待値を求めよ。 2 答え…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2306 問題 n次多項式を与えるのでそれが重解を持つかどうか判定せよ。 0 30 解法 重解を持つ条件はf(x)=0かつf'(x)=0となるxが存在することである…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2302 問題 長さnのハッシュにn個の値を線形探索で値を入れていく。もしもN-1まで開いてない場合は失敗となる。m個分はどのタイミングでどの箇所に…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2304 問題 円環の中に長さNの数列がある。この数列の各数値に対して自分自身と左側のL倍と右側のR倍を足した数値を新しい数値にするという操作をS…

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://poj.org/problem?id=3659 問題 n頂点の木が与えられる。全ての頂点との距離が1以下となる頂点集合の最小サイズを求めよ。 1 解法 dfsで各頂点の深さを求めて、深い方から順にその点がまだカバーされてなかったら親の頂点を頂点集合にいれていく。

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=528&page=show_problem&problem=3917 問題 人がn人いて、それぞれ(xi,yi)にいる。ある人が、ある人の銃声を別の人の銃声よりも早く聴いたという情報がm個与えられる…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=528&page=show_problem&problem=3916 問題 w*hのグリッドにプールを作りたい。#のセルを.に変えるコストはd、.のセルを#に変えるコストはf、最終的な状況で#と.のセ…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=528&page=show_problem&problem=3914 問題 図のようなブロックを使って指定されたように敷き詰めることができるか？ 1 解法 まず、白のブロック数が黒のブロック数…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=518&page=show_problem&problem=3820 問題 0,1で構成されるm*n行列がある。隣り合う要素同士をswapすることによって各行、各列にある1の個数を同じにしたい。swapの…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2962 問題 m種類の文字から構成されるn文字の文字列が与えられる。また2つの文字を合成した時にどの文字が何分でできるかの表も与え…