ABC212 参加記録 - geam1113’s diary

Aの各要素について、差の絶対値が最小となるのは、Bの要素のうち、値の近い2つまたは1つです。これはBを予めソートしておくことで、二分探索によって求められます。

Bに予め $-\infty,+\infty$ を入れておくと、実装が楽になります。

差の絶対値は数直線上の距離で考えるとわかりやすいです。

操作1や3は優先度付きキューで高速に対応できます。しかし、操作2を袋の中の全ての数に毎回行うのは制約的に厳しいです。そこで、これを効率的に行えないか考えます。

操作2で袋内全体にXを足す代わりに「袋内全体に足されている数」Yを用意し、YにXを足すことにしてみます。操作3では取り出した数にYを加算すれば操作後の数を復元できます。

問題は操作1ですが、Xを袋に入れるときにYを減算しておけば、矛盾なく操作が行えます。

よって、操作2がO(1)で行えるようになり、実行時間制限に間に合います。

解けなかったため、解説見ました。

dp[i][j] := 都市iにj日目で訪れる時の移動方法が何通りあるか

とします。

まず、橋が全て通れる時を考えます。すなわち完全グラフです。

この時、例えばN = 5で、都市5に4日目に移動する方法を考えてみます。

都市5以外の全ての都市から都市5に移動できるので、以下のようになります。

dp[5][4] = dp[4][3] + dp[3][3] + dp[2][3] + dp[1][3]

次に、都市5と3を繋ぐ道路が壊れていたとします。この場合、

dp[5][4] = dp[4][3] + + dp[2][3] + dp[1][3]

というように、dp[3][3]を省いた形で計算することになります。

ここからがこの問題の重要部分で、上記の式を以下のように考えます。

dp[5][4] = dp[4][3] + dp[3][3] + dp[2][3] + dp[1][3] - dp[3][3]

さらに自己ループを追加します。

dp[5][4] = dp[5][3] + dp[4][3] + dp[3][3] + dp[2][3] + dp[1][3] - dp[3][3] - dp[5][3]

S_k = dp[1][k] + ... + dp[N][k]とおくと、

dp[5][4] = S_3 - dp[3][3] - dp[5][3]
となります。

S_kは都市によらず一定になるため、毎回の計算は不要です。更に、壊れた道路が繋いでいた都市の分を引く処理は、各日にちにおいて、合計でM回しか計算が発生しません。

よって、計算量はO(K(N+M))となり、制限時間に間に合う、ということになります。

Mが最大でも5000というところに着目し、計算量の減らし方を考えられればよかったのかもしれません。