AtCoder Grand Contest 032

Updated:

AtCoder Grand Contest 032

解説放送

ソースコード

解法のメモ

A - Limited Insertion

解答

クエリを逆順に処理することを考える。すると挿入した座標 $=$ その数字なので、直前に挿入する数字が何であったのかの候補が決まる。そのうち一番大きいものを挿入するのが正解である。仮に $i < j$ が挿入可能であるならば $j$ の方を挿入していないとおかしい。というもの $i$ を挿入していたとすると $j$ 番目の方は $j - 1$ 以下の座標になるので、どうやっても挿入できない。以上により挿入の仕方は事実上 $1$ 通りに決定される。途中で挿入できなければ負けで、そうでなければ勝ち。

ポイント

A にしては難しいとのことであった。

B - Balanced Neighbors

解答

まず完全グラフを考える。すると全体の合計に自分自身を除いた数になる。これから削る方針でする。

$N$ が奇数の場合

($i$ と $N - i$) たちを削ったものが正解。

$N$ が偶数の場合

($i$ と $N + 1 - i$) たちを削ったものが正解。

ポイント

気づけばすぐ。

C - Three Circuits

解答

まず全部の頂点の次数が偶数でないとアウトである。この時点でオイラーグラフであることは確定である。一本道がある。

次数 $6$ 以上の頂点が存在する場合は、答えは “Yes” である。その点でオイラー路を分割すればサーキットが 3 つ得られる。以下そうでない場合を考える。

次数 $4$ の頂点が存在しない場合は、交わりのない閉路であるから、分割しようがない。これは “No” である。次数 $4$ の頂点が $1$ 個の場合も、サーキットは $2$ つまでしかできない。次数 $4$ の頂点が $3$ 個の場合は必ずできる(解説放送下図の場合分け参照)。次数 $4$ の頂点が $2$ 個の場合は場合分けが必要である。その頂点を $s, t$ とし、 $s \to t$ へ DFS をする。この時 $s$ から $t$ にたどり着かずに $s$ に戻って来る場合は答えは “No” である。

解説放送の図

ポイント

実験、考察、一般論を導くしかないだろう。

D - Rotation Sort

問題文の言い換え

$1$-indexed とする。まず問題文の状況と $2$ つの操作を言い換える。次の問題と同値である。

$p _ 1, p _ 2, \dots, p _ N$ が数直線上にこの順序で並んでいる。ただしその絶対的な位置は問わないとする。以下の操作が好きな順序で何度でも可能である。

  • コスト $A$ を支払う。好きな数字を数直線上から取り出し、その座標を大きくして、配置し直す。
  • コスト $B$ を支払う。好きな数字を数直線上から取り出し、その座標を小さくして、配置し直す。

相対的な数字の順序が $1, 2, \dots, N$ になるまでの最小コストを求めよ。

これを DP で解くために、最初の数直線の状態 $X$ と、最後の数直線の状態 $Y$ を縦に並べる。そしてこれに布を被せて、左から順番に reveal していくと考える。すると以下のことが言える。まず reveal すると $X$ は $p _ 1, p _ 2, \dots, p _ N$ の順番で数字が登場するし、 $Y$ は $1, 2, \dots, N$ の順番で登場する。上に新しく $p _ i$ が登場するとき、コストの計算をすることを考える。まず $p _ i$ が $Y$ ですでに登場していた場合は、それは座標を小さくして配置し直したということだから、コスト $B$ が支払われる。同様に、 $Y$ に登場していなかった場合は、コスト $A$ が支払われる。同時に登場していた場合は、コスト $0$ が支払われて、先に進む。

DP で問題を解く

$DP[i][j] = X$ 上で $p _ i$ まで reveal されていて、 $Y$ 上で $j$ まで reveal されている段階で支払われている最小コスト

と定義する。初期状態: $DP[0][0] = 0$, otherwise $DP[i][j] = \infty$. 答え: $DP[N][N]$. 遷移: $i = 0, \dots, N$ に対し、 $j = 0, \dots, N$ に対し、 \[ \begin{align} DP[i][j + 1] &\gets \min(DP[i][j + 1], DP[i][j]) & & j < N, \\\ DP[i + 1][j] &\gets \begin{cases} \min(DP[i + 1][j], DP[i][j] + B) & p _ {i + 1} \leq j, \\\ \min(DP[i + 1][j], DP[i][j] + A) & p _ {i + 1} > j, \end{cases} & & i < N, \\\ DP[i + 1][j + 1] &\gets \min(DP[i + 1][j + 1], DP[i][j]) & & i < N \land j < N \land p _ {i + 1} = j + 1. \end{align} \]

ポイント

ローテーションの言い換えは思いつかなかった。記憶しておきたい。

E - Modulo Pairing

問題の解析

$a _ i$ たちは昇順で sort されているとして良い。 $a, b < M$ および $\mathbb{Z}/M\mathbb{Z}$ 上で加法を考察しているから、ペアの作り方によりコストは結局、 \[ \mathop{cost}(a, b) = \begin{cases} a + b & a + b < M, \\\ a + b - M & a + b \geq M \end{cases} \] であることに注意されたい。上の場合を青のペア、下の場合を赤のペアと呼ぶことにする。

まず補題を示す。

補題: $(a, b)$ が赤のペアであり、かつ、 $(c, d)$ が青のペアであると仮定する。このとき、 $a, b \geq c, d$ を仮定しても、最小値が達成される。

証明:最小値が達成され、かつ、 $a < c$ であると仮定する。このとき、 $a + d < c + d < M$ が成立する。よって $\mathop{cost}(a, d) < \mathop{cost}(c, d)$ である。また、 $b + c > a + b \geq M$ より、 $\mathop{cost}(b, c) = b + c - M$ である。そして $b - M < 0 \leq d$ より、次式が成立する。 \[ \mathop{cost}(b, c) = b + c - M < c + d = \mathop{cost}(c, d). \] 以上より、 $\mathop{cost}(a, d), \mathop{cost}(b, c) < \mathop{cost}(c, d)$ であるから、 $a, c$ を swap しても最小値を達成することがわかる。これが示すことであった。

実装

補題より、ある $0 \leq t \leq N$ が存在し、 $0 \leq i < 2t$ に関しては青のペア、 $2t \leq i < 2N$ に関しては赤のペアを作るとして最小値を探索すればよろしい。それぞれの区間では最大値の最小値を達成するためには、大きいものと小さいものを順に組み合わせれば良いのはさすがに自明であろう。そしてそれに気づけば、 $t$ が小さければ小さいほど、最大値が小さくなるのも明らかであろう。ただし「赤のペア」は、前提として和が $M$ 以上である必要がある。だから $t$ が小さすぎると正しい分け方ができない。よってめぐる式二分探索で書けばよろしい。 $ok = N + 1$, $ng = -1$ としてやればよろしい。

ポイント

実装は信じられないくらい簡単なのだが、着想が難しい。しかし 1200 点だから絶対手が出ないレベルではない。

F - One Third

ポイント

その他