AtCoder Grand Contest 030
Updated:
Source codes
Solutions
A - Poisonous Cookies
$\min(A + B + 1, C) + B$ を出力する。
B - Tree Burning
$1$-indexed とする。同じ問題を 2 回解くことにより、つまり $X _i \gets L - X _i$ として sort することで、初期地点から反時計回りに進むとして一般性を失わない。
$i = 1, 2, \dots, N$ に対し、反時計回りに回って $X_i$ までを燃やし、時計回りに回って残りを燃やすことを考える。つまり $X_i$ と $X_{i + 1}$ の間で道が分断されているとして良い。
ひとまず $k$ 往復することを考える。すると $k$ 個は奥の方から貪欲に選んでいくと良いとわかる。つまり $X_i, X_{i - 1}, \dots, X_{i - (k - 1)}$ を反時計回りで燃やす。 実際は逆順 で、往復しながら徐々に燃やしていく。
答えを距離を大きくしたいので、この $k$ は大きければ大きいほどいいに決まっている。ここで finish の仕方が次の $2$ 通りあることに注意する。
- 最後は時計回りで finish する。つまり両方とも $k$ 往復するが、最後だけは $X_{i + 1}$ の地点で finish する。
- 最後は反時計回りで finish する。つまり反時計回りに $k$ 往復、時計回りに $k - 1$ 往復するが、 $X_i$ の地点で finish する。
$right = i$ とし、 $left = N - right$ とすると、 1. は $k = \min(right, left)$ である。 2. は $k = \min(right, left + 1)$ である。
あとは累積和をもっておけば答えが簡単に出る。 $S[i] = \sum _{j = 1}^{i} X _j$, $T[i] = \sum _{j = i}^N (L - X _j)$ として、略記のため $r = right$ とすると、それぞれ
\[
2 (S[r] - S[r - k] + T[r + 1] - T[r + 1 + k]) - (L - X[r + 1]), \\
2 (S[r] - S[r - k] + T[r + 1] - T[r + 1 + (k - 1)]) - X[r]
\]
が答えであるとわかる。これらの最大値を求めればよろしい。計算量は $O(N)$ である。
ポイント
最初は「最小値」だと思っていた。こんなの楽勝じゃん！ と思っていたけど、最大値だった。
この問題のポイントは「区切る $i$ と $k$ を一旦固定して考える」ことと「逆順を考慮する」ことである。 finish の仕方自体は、奥の方で行うけれども、 貪欲に奥の方から燃やしていけるようにルールを改変する ことが発想の鍵となる。後は $k$ を注意深く大きくすればいいし、 $i$ については累積和を使えば良いのは、定跡通り。
最後は finish するところが奥の方であることを忘れていてしばらく通っていなかった。
C - Coloring Torus
ポイント
D - Inversion Sum
『STEINS;GATE』のように、入れ替える、入れ替わらないをそれぞれ選んでいくたびに、世界が分岐していくと考える。 $2^Q$ 個の 世界線 と呼ぶことにする。
$T[i][j] = A _i > A _j$ となる世界線の個数
が正しく求まれば、答えは以下で求まる。 \[ \sum _{0 \leq i < N} \sum _{i < j < N} T[i][j]. \]
最初は $(i, j) \in N^2$ に対し、
\[
T[i][j] =
\begin{cases}
2^Q & (A _i > A _j), \\
0 & (otherwise)
\end{cases}
\]
としていく。ここから $q = 0, \dots, Q$ に対し、 $x = X[q]$, $y = Y[q]$ としていき、
$A _x, A _y$ を swap するかどうかで世界線がどのように分岐するのか考える。すると、以下のようにわかる。
- $j \in N \setminus \{ x, y \}$ に対し、「世界線の選択」の後に $A _j > A _x$ となるための必要十分条件は、 swap 前に $A _j > A _y$ であって swap するか、または swap 前に $A _j > A _x$ であって swap しないことである。したがって、 $T[j][x] \gets (T[j][x] + T[j][y])/2$ とすればよい。同様に考察すると、以下のことをすれば良い。
\[
\begin{align}
T[j][x], T[j][y] & \gets \frac{1}{2} \left( T[j][x] + T[j][y] \right), \\
T[x][j], T[y][j] & \gets \frac{1}{2} \left( T[x][j] + T[y][j] \right). \end{align} \] - $A _x, A _y$ の間についても同様に考察すると、以下のようにすれば良い。 \[ T[x][y], T[y][x] \gets \frac{1}{2} \left( T[x][y] + T[y][x] \right). \]
当然 $2^{-1} \in \mathbb{Z}/(10^9 + 7)\mathbb{Z}$ は普通に求めればよろしい。実装上の注意点としてはきちんと temp の配列を用意しておいて、書き換えることである。
計算量は、最初と最後に $O(N^2)$ の計算量が必要で、 $1$ 回の世界線の分岐で $O(N)$ の計算が必要であるから、 $O(N^2 + QN)$ である。
ポイント
全部の場合について和を取る問題は、だいたい和の取り方を変える問題である。類題は例えば以下がある。
これは本当におしかった。解答の一歩手前まで行っていたのだが、最初のセッティングでミスをしていた。 できるだけ解答に近くダイレクトに Table をもっておくのが安全 だと思った。それが教訓です。
E - Less than 3
ポイント
F - Permutation and Minimum
ポイント
Others
Rating が上がった。最近論文書きすぎていて頭がおかしくなっていたけれども、パフォーマンスは良かった。