http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=285&page=show_problem&problem=2036 問題 モーションセンサーがk個ある。モーションセンサーはマンハッタン距離でdの位置まで有効である。このdは全てのセンサーで…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=285&page=show_problem&problem=2040 問題 無向中国人郵便配達問題を解け。 2 1 解法 一般の最小重み完全マッチング。のはずだけどなぜか2部グラフの最小重み完全マ…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=285&page=show_problem&problem=2042 問題 人を2つのグループに分けたい。人同士の間には仲の良さがあり、その人の幸福度は同じグループに入っている人の中の良さの…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3552 問題 半径Rの円盤に半径rのドリルでn個の穴を開ける。重心を求めよ。 0 解法 穴がかぶることが無ければ普通に重心の公式で求めれば良い。穴がかぶってしまうので穴の形を考えて厳密に面…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3559 問題 矩形の毒沼がn個ある所でスタートからゴールまで行きたい。毒沼に入らず(境界含む)にゴールまで行くには最低何回曲がらないといけないか答えよ。 0 座標 解法 座標圧縮してダイクス…

問題 B進数を16segで表示する。180度回転して一致するK番目の数値を答えよ。 1 1 解法 反転して一致するものが0のみでK!=1のときは解が無い。他の場合は適当に反転して一致しない物が存在しない数をスキップしながら1ずつ足して順番に見つけていく。

問題 数列がN個ある。また数列に関してという制約がM個ある。この制約をすべて満たす数列は存在するか？存在する場合は辞書順最小の数列を求めよ。 N M 0 解法 強連結成分分解しグラフを縮約する。制約を満たすためには同じ強連結成分に含まれるもの同士の間…

問題 長さNの数列Aがある。Aのsubsequenceで単調増加でも単調減少でもない物の数は何個？ 1 解法 O(n^2)のDPをするだけ。無駄にTLEがきつい。

問題 のサイズを求めよ。 1 1 解法 やるだけ。

問題 andoroidとかのロックで押した順番が与えられる。同じ番号を押していて、線の形が同じになる押し方の数を答えよ。 解法 やるだけ。

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3555 問題 h*wの盤面のアイスクライマーで一番上にたどり着くまでの最小の時間を求めたい。ルールは以下のとおり。 左右に進むのにt1かかる 敵がいる場合は無理 進んだ先に足場がない場合も無…