AtCoder Regular Contest 085
Updated:
Source codes
Solutions
C - HSI
$2^M(100(N-M) + 1900M)$。
ポイント
1% のガチャ当てるのにかかる期待値が 100 回であるというソシャゲで常識になっている確率過程の知識があれば楽勝であるし、そうでないと難しいだろう。
D - ABS
$N = 1$ の時は、答えは $\lvert a_N - W \rvert$ である。 以下は、 $N \geq 2$ として良い。
どちらかの人は $a_N$ を必ずとる。だからスコアは、ある $0 \leq k \leq N-1$ があって $\lvert a_k - a_N \rvert$ と表せられる。ただし $a_0 = W$ である。
問題はどの $a_k$ をとって最終スコアになるかということなのだが、仮に先手が $a_i$ ($1 \leq i \leq N-2$) をとったとすると、後手には $a_{N-1}$ を取ることでスコア $\lvert a_{N-1} - a_N \rvert$ を達成できる権利がある。 後手はできるだけスコアを小さくしようとするので、 先手はこれより小さなスコアしか取ることができない。 これは先手がいつ $a_i$ をとっても同じことである。 したがって、
先手が初手に $a_i$ ($1 \leq i \leq N-2$) をとると、スコアは $\lvert a_{N-1} - a_N \rvert$ 以下である
という結論になる。また
先手が初手に $a_{N-1}$ をとれば、スコア $\lvert a_{N-1} - a_N \rvert$ を達成できる。先手が初手に $a_{N}$ をとれば、スコア $\lvert W - a_N \rvert$ を達成できる。
というのも事実である。以上より答えは $\max(\lvert a_{N-1} - a_N \rvert, \lvert W - a_N \rvert)$ である。
ポイント
実戦ではこんなにスマートに考えられたわけではないが、答えは出せた。「どっちかは必ず $a_N$ を取らないといけない」をすぐ思い当たったのが大きい。
E - MUL
結論から言うとこれは最小カットの問題である。 $S$ 側を「割られる宝石」、 $T$ 側を「割られない宝石」とし、 最小カットが答えを与えるように グラフを作成する。 $u$ から $v$ への容量 $c$ の辺を $(u, v, c)$ と表す。
まず $j$ が $i$ の倍数であるとき、 $i$ が割られているのに $j$ が割られていないということはルール上ありえないので 辺 $(i, j, \infty)$ で表される。
次にルールを読み換える。このゲームの最大得点は $M = \sum_{1 \leq i \leq N, a_i > 0} a_i$ であるので、この得点から減点していくと考えよう。
$a_i < 0$ のとき、$i$ を「割らない側」につけると減点である。だから $S$ 側からカットしてはいけないので $(S, i, -a_i)$ で表される。
$a_i > 0$ のとき、$i$ を「割る側」につけると減点である。だから $T$ 側からカットしてはいけないので $(i, T, a_i)$ で表される。
あとは最大フローをプログラミングコンテストチャレンジブックの通りに実装して流せば良い。
ポイント
最小カット・最大フローの場合は、負の辺がないようにしないといけない。このため、最大の点数から減点するようにすると上手くいきやすい。
このゲームは貪欲法ではない。貪欲法では WA だった。かと言って、小さい問題に分割できるわけではない。倍数だから、小さい問題を解いたところで、解いた結果が大きい問題に影響してしまうのを避けることができない。こういうときはフローが正解だったのだ。
追記
解説放送で rng さんが greedy で WA する例を解説していた。
6
-1 -5 -5 0 5 6
上から greedy だと全部残るか全部消すかで 0 が答えだが、実際は $a_2, a_3, a_4$ を消して $a_6$ も消えた時に $a_1 + a_5 = 4$ とできこれが最大なので 4 が答え。
F - NRE
まず $Q$ 個の $[l_i, r_i]$ たちを標準的な順序で昇順で並べ換える。これを上から実行していくか否かを決めていくとする。すると、$a$ はどのタイミングでも必ず
($0, 1$ が合わさった確定した領域) + ($l$ が到達していないが $r$ は到達したため $1$ が並んでいる領域) + ($r$ すら到達していない $0$ が並んでいる領域)
の形をしていることになる。ここで「確定した領域」は、ハミング距離だけ覚えて、配列は忘れてよろしい。一方で、2 番目と 3 番目の境界点は覚えておく必要がある。そこでまず、 $DP[i][j]$ を「$l_k < i$ なるペアたちを検討し終えた結果 $a_0, \dots, a_{i-1}$ までが確定していて、その結果 $a_i, \dots, a_{j-1}$ までが $1$ になったようなもののハミング距離のうち、最小のもの」とする( この定義は後に修正する )。答えは $DP[N][N]$ である。
この遷移をどのように行うべきか。まず $i = l_k$ の時の $[i, r_k]$ の処理を考察しよう。このとき、 $a_i, \dots, a_{r_k}$ が塗られるが、影響を受けるのは $DP[i][i], \dots, DP[i][r_k+1]$ のみである。ここに書かれた最小値が $DP[i][r_k+1]$ に入る。つまり、
区間 $[l, r]$ の処理は $DP[i][r+1] \gets \min_{i \leq j \leq r+1} DP[i][r+1]$ に相当する。
とわかる。さらに検討している区間の左端を $l$ から $l+1$ へうつる際には、$DP[l][l]$ に $a_l = 0$ とした時の $b_i$ との距離を足す(つまり $b_i = 1$ の時 $1$ を足す)場合と、$DP[l][l+1]$ に $a_l = 1$ とした時の $b_l$ との距離を足す(つまり $b_i = 0$ の時 $1$ を足す)場合で小さい方を $DP[l+1][l+1]$ に入れることになる。残りの $DP[l+1][l+2], \dots, DP[l+1][N]$ の方は $a_l = 1$ とした時の $b_l$ との距離を足す。
ところがこれでは、検討するマスが多すぎてうまくいかない。そこで、前述の 連続な領域の $\min$ をとる操作を Segment Tree で処理する ことを考察する。つまり RMQ である。ここで問題になるのが、 $l \mapsto l+1$ への遷移である。「全部に $1$ を足す」を RMQ で効率よく行うことはできない。そこで、 最初に全部 $1$ を書いてある時のハミング距離を元に、ところどころ $0$ になったとき、調整をするというように考慮する。つまり $DP[i][j]$ の定義を、「$l_k < i$ なるペアたちを検討し終えた結果 $a_0, \dots, a_{i-1}$ までが確定していて、その結果 $a_i, \dots, a_{j-1}$ までが $1$ になったような数列 $a$ の、 仮に $a_i, \dots, a_{N-1}$ まで全て $1$ を書いたときのハミング距離 のうち、最小のもの」とする。こうすると何がいいかというと、コストの足し引きをするのは $0$ を書いた時だけで良い。すなわち、
検討している区間の左端を $l$ から $l+1$ へうつる際の処理は、 $DP[l+1][l+1] \gets \min(DP[l][l] + \mathrm{cost}(l), DP[l][l+1])$ かつ $k = l+2, \dots, N-1$ に対し $DP[l+1][k] \gets DP[l][k]$ に相当する。
とわかる。ここで $\mathrm{cost}(l)$ は $b_l = 0$ の時は $-1$, $b_l = 1$ の時は $1$ であると定義する。こうすると、 $DP$ の第 $1$ 成分は切って良いことになる。使い回せば良いだけだから。つまり Segment Tree を 1 個定義し、それを最後まで使い回せば十分である。
計算量は $O(Q \log N + N \log N)$ である。 $Q, N \leq 200000$ だと危なそうだが、 Segment Tree は大きさ $2N$ 程度の配列をいじるだけだから、 3 sec であることもあって十分間に合う。
ポイント
DP だが、 配列そのものを Segment Tree に落とし込む 問題は初めて見た。これは記憶しておこう。
コンテスト本番は問題文をちらっと見ただけで何も検討しなかった。検討しても答えにはたどり着けなかっただろう。こういう時は復習しないのだが、しかし綺麗な解答だったので、復習した。
Others
「最大フローを作る」問題はわかりやすいが、「最小カットを作る」のは初めて見た。「割る・割らない」を二部グラフで表すと思考していけばできるのだが…いやはや今回は無理でした。
D が難しかったようで、これをすぐ解けたのでレートは上がったようだった。