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の最短路になっていることから明らか)
C - Sugar Water - AtCoder Regular Contest 083
A, B, C, D, E, Fが与えられる。空のビーカーに次の操作のいずれかを何回でも行える。
- 100A[g]の水追加
- 100B[g]の水追加
- C[g]の砂糖追加
- D[g]の砂糖追加
現在水100[g]当たりE[g]砂糖が溶け、ビーカーには最大F[g]の砂糖+水が入るとすると、最大濃度のときの砂糖水と砂糖の重量を答えよ。(答えはいくつかある)
A, B, C, Dの操作を行い、メモ化再帰で容量Fに到達するまで全探索する。それぞれの制限が小さいからといってメモ化をサボるとTLEになるので注意。メモ化のキーは現在の{水の量, 砂糖の量}など。double型ではなく、整数型で全部決定できるのでできればその方針で行う。
ACしたら力尽きてブログを更新する気力がなくなる件
時間かけてACした問題は復習も兼ねてブログに書くべきなんだけど、通した時点で力尽きてしまうのなんとかしたいですね。3連休に一気に積みAC？をまとめるか…
D: Derangement - AtCoder Regular Contest 082
順列p[i]が与えられる。何回かp[i] とp[i + 1]をSwapするという操作を行い、すべてのiについてp[i] ≠ i となるようにしたい。操作の最小回数を求めよ。
p[i] = i となるような連続部分列があったとする。この時、この部分列の長さ l に対して、この部分列をすべてp[i] ≠ l となるようにするにはペアを作って l / 2(小数以下切り捨て)回で可能である。これは、最初から順にペアを作ってそれらをSwapしていけば偶数この場合はすべて条件をみたすようにでき、奇数個の場合は最後の1個を、その次のp[i] ≠ iであるような要素と入れ替えれば条件を満たすことができるからである。終端にちょっとだけ注意する。
よって、p[i]の中でp[i] = iとなるような部分列を抽出し、(int)(l / 2) を足していけばよい。O(N)。
C: Together - AtCoder Regular Contest 082
数列a[i]が与えられる。ある数Xを選んで、各a[i]に対して-1, 0, +1のいずれかを加えることで、a[i]=Xとなるiの個数が最大になるようにしたい。最大値を求めよ。
v[n]=(a[i]=nとなるようなiの個数) という配列を作っておきます。すると、v[n-1] + v[n] + v[n + 1]の最大値が求める答えになります。ただし、両端に注意。O(N)。
