AOJ 12/13

2014-12-13 | [Competitive programming]

2405

区間 DP をメモ化した上で適当な skip (外周道路しか通っていない点だと隣とつなげるほかないので 2 個進められる) を施したら通った

2240

自明な場合 ((0, 0) を封鎖できるなど) は無視して考える．

黒うさぎは，次の条件をみたす六角形領域を立入禁止にすることができる．

最初 (0, 0) をその領域としておいて，上の条件をみたすまで領域を拡張する． ただし，ナイーブにやると O(N^2) で間に合わない．

領域や縄張りの範囲を，x, y, x+y についてそれぞれのとりうる範囲を用いて表すことができる． すると，領域および (内部を含めた) 縄張りが共通部分を持つことと，x, y, x+y すべての範囲が共通部分を持つこととは同値になる． そのため，各座標について条件をみたしたら点数を 1 加点し，満点になったらその縄張りも含めるなどとするとよい．

ただし，領域が縄張りの内部にある場合は，どれかの座標が縄張りの範囲の端まで来るまでは縄張りを含めてはいけないので，点数の与え方を少し変える．

新たに条件をみたすものを見つけるのは，ソートしておくと先頭から見ればいいので高速に行える．

この立入禁止領域が得られていれば，判定はその点が領域に含まれるか調べるだけである． 結局，計算量はソートに支配されて O(N log N)．

2337

DP テーブルを順次更新 + データ構造でなんとかすると解ける

2375

N = 2 は不可能で，それ以外は可能である．

どの 3 点も同一直線上にない場合は K(K-1)/2 個の直線がある． 3, 4, 5 点が同一直線上にある事象があると，1 つの事象ごとにそれぞれ 2, 5, 9 個直線を減らせる．

K として，まず K(K-1)/2 >= N なる最小の K をとり，K(K-1)/2 - N が 1 か 3 の場合は K をさらに 1 増やすと，それが K の下界を与える．

複数の事象に絡む点を (0, 0) に限るとする． すると，同一直線上にある事象を発生させると，使える点をいくつか消費して，直線の数の余剰 K(K-1)/2 - N を減らすことができる． 2, 3, 4 点の消費 (2, 5, 9 個直線を減らせる) だけを考えても，N = 7, 9, 20 を除いては解を与えることができる． 余剰が 0 になった場合は，1 点のみの消費を繰り返す．

なお，ここで異なる消費タイミングにおける点たちが同一直線上にあると困るが，座標範囲が大きいので，直線を決めたらその上でランダムに点をとるだけでも十分安全である．

N = 7, 9, 20 の場合はあらかじめ手で答えを作って埋め込む．