C: Fountain Walk - AtCoder Grand Contest 019
格子マップ及びいくつかの頂点が与えられる。格子の辺は100m、与えられた頂点にはN個の噴水があり、半径10mの外周を通ることが可能である。格子点は同一水平線上または同一垂直線上にたかだか1個である。
スタートとゴールが与えられたときに、最短経路を答えよ。
まず分かることは角を曲がる時噴水を通ると、普通に格子点で曲がったときよりも距離が短くなり、噴水を縦または横に通り過ぎると格子点を直進するときよりも距離が長くなる。なので、なるべく格子点を曲がるときに通るのがよい。ここで、同一直線状に噴水はたかだか1個しかないことから、ゴールとスタートの間のマス目のサイズををH*Wとすると、min(H, W) + 1個しか存在しないことになる。まずはこの区間にある噴水をできるだけ通ることを考える。そこで区間内の噴水をx方向にソートする。その上で、噴水のy座標の最長増加列を計算すると、その列に含まれる噴水はゴールまでに通ることが可能である。この最長増加列の個数をkと置く。
k < min(H, W) + 1 のとき、全て曲がり角として噴水を通ることが可能なので、その差分を通常の格子点の最短経路(w + h)*100から引けばよい。
k = min(H, W) + 1のとき、最低でも1個は噴水を横切ってしまう。なのでその差分を足しておく。
全体でO(N)。
B: Reverse and Compare - AtCoder Grand Contest 019
文字列Aが与えられる。任意の添字i, jを選び、連続部分文字列A[i]..A[j]を反転させる。(i=jならなにもしないのと同値)。この操作を1回だけしたときに得られる文字列は何通りあるか？
左の文字から順に数えていく。今見ている文字がcのとき、そこより右の文字がすべてc以外なら右にある文字数だけ、反転したら別の文字列が構成できる。もし、cがk>0 個あるとき、その反転は両脇のcを除いた反転と同じなので、現時点ではカウントしないこととする。こうやって和をとっていけば全部の組み合わせがカウントできる。
アルファベットはa-zなので、これらの文字のカウントの累積和を作っておくことで、あるインデックスより左にある特定の文字、と言うものをO(1)でカウントできる。合わせて計算量はO(N)。
A: Ice Tea Store - AtCoder Grand Contest 019
アイスティーの単価がQ, H, S, D円でそれぞれ0.25l, 0.5l, 1l, 2l買える。在庫はいくらでもある。Nリットルのアイスティーを買いたいとき、必要な金額はいくらか？
要は2lのものをいくら買うか、ということである。まずリットル単価別にソート、もし2l以外でより安いものがあればそれで全部買う、2lが一番安い場合は2lのものを買えるだけ買い、もし1l分だけ他に欲しい場合は次に単価の安いものを買う。O(1)。
F - Sandglass - AtCoder Regular Contest 082
容量Xで一秒間に1砂がおちる砂時計がある。時刻集合r[i]が与えられて、各時刻に砂時計をひっくり返すことがスケジュールされている。時刻0で砂時計の上半分をAという。
このとき、q個のクエリ「初期のAにある砂の量がaのとき、時刻tのAの砂の量はいくらか」に答えよ。
初期の砂の量をx, 現在の時刻をtとする時、時刻tでの砂の量を返す関数を f(x, t) とおく。この関数をtを固定してシミュレートしてみると、ある時刻(※1)までは一定で、そこから傾き1の直線になり、更に別の時刻(※2)から一定になる、という関数になる。つまり(※1)の時刻と値、(※2)の時刻の3個の数値がtによって変化しているだけである。
この3個の値を更にtを変えてシミュレートしてみると、時刻が進むたびに全体にグラフが下に移動し、0を下限として(※1)が潰れていく、その後ひっくり返して全体に上にグラフが移動し、Xを上限として(※2)以降が潰れていくというのを繰り返し、状況によっては最終的に潰れて常にxによらない固定関数に近づく。これをシミュレートしてやればよい。O(Q)。
E: Snuke and Spells - AtCoder Regular Contest 082
点集合が与えられる。部分集合Sが凸包の頂点をなすとき、そのSのスコアをexp(2, (Sの内部と境界にある点の数) - |S|) と定義する。この点のすべてのSについてそのスコアの和を求めよ。
スコアの意味をよく考えてみると、点集合全体の部分集合の数から、凸包にならない部分集合の数を引いたものである。凸包にならないものとは、ある一直線上に並んだ2点以上の部分集合と、1点のみの部分集合、空集合になる。1点と空集合はn + 1を引けばよい。
同一直線状に並んだ2点以上の部分集合は、二重ループを回し、直線のハッシュなどをキーにして、ハッシュの値などに点をどんどん追加していく。その後、得られた直線 (最大で n(n-1)/2 個)に対応する点集合(サイズkとする)について、その中の2点以上の部分集合 2^k - k - 1 の和となる。
最後に2^nから上記の和とn + 1を引けば答え。O(n^2)。
E - Bichrome Tree - AtCoder Regular Contest 083
頂点数Nの木とN個の数列X[i]が与えられる。各頂点に対し、ある非負整数を割り当て、かつ白または黒に塗り分けるとき、次の条件をみたすようにしたい。
条件：頂点i を根とするサブグラフについて、頂点i と同じ色の配下(i自身も含む)のノードに割り当てた数字の和がX[i]になる
この条件を満たせるか？
根から、「子の色と異なる数字の和の最小値」 というものを返すdfsを行う。条件から子の色と同じ数字の和は常にX[子ノード]で固定になる。また、現在見ているノードで条件が達成できるかどうかは、「子の色と異なる数字の和」または「子の色と同じ数字の和＝X[子ノード]」の小さい方を足していったときにX[現在ノード]の値を超えないか(※)、である。
この条件を根まで満たせるようにするには、「子の色と異なる数字の和の最小値」というものをどんどん根に向かって返していって矛盾が起きるかどうか判定すれば良い。
(※)はいわゆる0-1ナップサック問題で、X[現在のノード]に最も近い和(これをyとおく)になるように取ればよい。すると、「現在の色と異なる数字の和」は(※)の数のうち、最大のものの和から、yを引いたものを返せばよい。O(max(N, 頂点次数) * max(X)) 。
D - Restoring Road Network - AtCoder Regular Contest 083
隣接行列形式でN都市間の距離が与えられる。この隣接行列で表された距離が最短距離となるようなN都市間の経路グラフは構成できるか？できるならば、経路の長さの和が最短であるようなものの経路の和を求めよ。
隣接行列に対してWarshall Froydで最短性の確認を行う。この時、ある経路について行列要素が更新された場合、最短路とならない。
逆に最短路であった場合、Warshall Froydの中で、各(i, j)に対し、d[i][j] == d[i][k] + d[k][j] という条件を満たした回数をカウントしておく。この回数が3以上であった場合、あるiともjとも異なるkが存在して、d[i][j] == d[i][k] + d[k][j] を満たしていることがわかる。これは別の経路を通ってiからjに最短路でいけるということを示しており、(i, j)間の直通経路は削除しても良い。そのため、このカウントが2であるような要素について、経路の長さの和をとってやればよい。O(V^3)。
(カウントが1は対角線にしか出てこない。また0がないのはWarshall Froydの最短路になっていることから明らか)
