[AtCoder 参加感想] 2020/07/25:M-SOLUTIONS プロコンオープン 2020

	A	B	C	D	E	F
問題文	■	■	■	■	■	■
自分の提出	■	■	■	■	■	■
結果	AC	AC	AC	AC	MLE	AC

E コンテスト後 AC → https://atcoder.jp/contests/m-solutions2020/submissions/15454058

全体感想
問題E – M’s Solution
問題F – Air Safety

全体感想

44分5完で、97位でした。

Eでやられてしまいました。MLE は古い過去問で経験がありますが、メモリ制限が 64～256MB などの小さい場合のことが多く。

最近のコンテストでは通常 1024MB 制限となっていますが、1024MB 制限で MLE した経験は全くなかったですし、リアルタイム参加したコンテストで MLE のせいで AC できなかったのは今回が初めてです。勉強になりました。

問題E – M’s Solution

本番 $Θ (N \cdot 3^{N})$ 解法(MLE)：■
$Θ (N \cdot 3^{N})$ 解法：■
$Θ (N^{3} \cdot 2^{N})$ 解法：■

$3^{N}$ の計算量ですが、よくある $\sum_{k = 0}^{N} (\binom{N}{k}) 2^{k} = 3^{N}$ という思考から導く（例：EDPC-U）ものではなく、 $3$ 択を $N$ 回繰り返す形で導きました。そのまま $N \cdot 3^{N}$ の配列を作ったため、MLE。再帰で実装すればメモリを使わないので良いけど、実行時間もわりとシビアだったので、しんどい解法になっていたようです。

改めて、 $3^{N} = \sum_{k = 0}^{N} (\binom{N}{k}) 2^{k}$ へと $3^{N}$ 通りの探索を分解することで、計算量 $Θ (N \cdot 3^{N})$ のまま空間計算量を、 $Θ (N \cdot 2^{N})$ にすることができました。この思考手順は初めてだったので、良い勉強になりました。

コンテスト翌日ですが、 $Θ (N^{3} \cdot 2^{N})$ 解法も実装しました。 $N \cdot 3^{N}$ のものについては公式の解説が非常に丁寧なため、ここでは $Θ (N^{3} \cdot 2^{N})$ について触れます。

各人が最適に動くなかでの最小値ですが、まずは「縦の距離、横の距離のうち好きなほうを選べる」とした上での最小値と言い換えます。ありがち。

そこで、各人が横の移動、縦の移動のどちらを受け持つのかを決め打ってしまった上で、になるのかを割り振る（ $2^{N}$ 通り）と、部分問題は $1$ 次元の場合ふたつです。計算量 $Θ (N^{3} \cdot 2^{N})$ を達成するには、次が $Θ (M^{3})$ で解ければよいです：

座標 $x_{1}, \dots, x_{M}$ に $p_{1}, \dots, p_{M}$ 人済んでいる。 $0, 1, \dots, M$ 件の駅をつくって、 $x$ 方向の移動の総和を最小化せよ。

ソートしておきます。最適解は、 ${x_{1}, x_{2}, \dots, x_{M}}$ を区間に分割する形になります。そこで、 $dp [i, n] = 人 1, 2, \dots, i を n 個の駅に収納するときの最小コスト}$ を計算することを考えます。

人 ${1, 2, \dots, i}$ の最適解は、ある $j$ に対して、 ${1, 2, \dots, j}$ の最適解に、 ${j, \dots, i}$ を1点に集めるときのコストを加えたものとして得ることができます。したがって、 $dp [i, n] = min_{j} (d p [j, n - 1] + f [i, j]), f [i, j] = 人 i, \dots, j を 1 点に集めるコスト$ という感じの計算をきちんとやれば、 dp を計算することができます。

各 $f [i, j]$ の計算は、先に中央値を求めることでも計算できますが、単純に集合場所を $x_{k}$ としたときのコストの $min$ として計算しました。これは各 $(i, j)$ に対して一からやると $Θ (N^{4})$ になってしまいますが、区間和の計算のために累積和を事前計算しておくことで、 $Θ (N^{3})$ になります。

以上を実装しようとすると、 $x = 0$ に最初から鉄道が置かれていることの対処が面倒です。 $x < 0$ となる人、 $x ≧ 0$ となる人に分けて解くことで対応しました。

問題F – Air Safety

発想はほとんど必要なく、いかにバグらせにくく手早く実装できるかが問われる問題だと思います。それを含めても、問題Eよりも簡単に感じました。AC人数もこちらの方が多かったようです。

UとDの衝突の場合

$(x, y)$ でソート
各 U 方向の $(x 1, y 1)$ に対して、1. の意味で最寄りの $(x 2, y 2)$ を探す
$x 1 = x 2$ ならば衝突。その場合の衝突時間は $5 (y 2 - y 1)$

という要領で計算できます。 $| x |$ が十分小さいことから、 $x$ 座標ごとに振り分けてもよいでしょう（バケットソートしているともいえる）

LとRの衝突も同様です。

UとRの衝突について考えましょう。 $(x 1, y 1)$ と $(x 2, y 2)$ を出発した人が時刻 $10 t$ に衝突するのは

$x 1 = x 2 + t$
$y 1 + t = y 2$

が成り立つときです。この連立方程式を解くと、 $t = x 2 - x 1 = y 2 - y 1$ となります。この条件は、 $x 1 - y 2 = x 2 - y 2$ かつ $t = x 2 - x 1$ と変形できます。

(U,D)の場合： $(a, b) = (x, y)$
(U,R)の場合： $(a, b) = (x - y, x)$

などとすれば、「 $a_{1} = a_{2}$ かつ $b_{1} < b_{2}$ のときに衝突」「 $b_{2} - b_{1}$ の最小値を求める」の形になっているため、 $(U, R)$ の場合の計算は、 $(U, D)$ と同じ形になることが分かります。

6種とも同様のロジックで、衝突の有無・最短時間が計算できることが分かったので、あとはその計算をする関数を用意して、6 回呼び出す形で実装すると、多かれ少なかれ十分に簡潔に済むと思います。