M-SOLUTIONS プロコンオープン 2020 D,E,F問題メモ

M-SOLUTIONS プロコンオープン 2020

ちょっと実装多めのABC相当。EはPython, PyPyでTLEが取れず。

D - Road to Millionaire

• 株取引をする。今、現金1000円持っていて株は持っていない
• 今日から $N$ 日間の株価が分かっている
• $i$ 日目には、1株 $A_i$ 円で好きなだけ株を売ったり買ったりできる
  • 取引しなくてもよい
  • 現物取引のみで、信用取引はできない
• $N$ 日後の所持現金を最大化せよ
• $2 \le N \le 80$
• $100 \le A_i \le 200$

自分が未来予知能力を得たらどのように行動するかを考えると、明日、株価が1円でも上がるなら、有り金全部使って買って、明日売ればよい。

逆に下がるなら、今日は全て現金化して、明日（以降）買えばよい。

すると、連続で株価が上がろうと下がろうと、毎日、以下の行動を繰り返せばよいことが分かる。

• 今日、とりあえず持ち株全て売る
• 明日の株価が上がるなら、現金の限り株を買う

最終日は現金を最大化したいので、買わないとする。

これをシミュレートすると通る。

意図的なテストケースでは、株価が 100, 200, 100, 200, … を繰り返したとき、2日で所持金を2倍にできる。 つまり、80日間で $2^{40} \times 1000 \simeq 10^{15}$ で1000兆円にもなる！（アメリカの国家予算の約2倍、ベゾスの約63倍）

逆に言うと、$DP[i日目][j株所持] = 所持現金の最大値$ というようなDPを作ってしまうと、爆発的に $j$ が増え、TLEする。（制約が小さいので騙されがち）

E - M's Solution

• 無限に広がる2次元グリッドの交点上に $N$ 個の街がある
• 街 $i$ は座標 $(X_i,Y_i)$ にあり、人口は $P_i$ 人
• 鉄道は、はじめ $x=0$ と $y=0$ の2直線だけ建設されている
• ここに、新たな鉄道路線を $K$ 本、以下の条件を満たすように敷設する
  • $x$ 軸または $y$ 軸に平行な整数座標に直線状に敷設する
  • 各街から、最寄りの鉄道路線までの距離を「歩行距離」とすると、市民の延べ歩行距離を最小にするように敷設する
• $K=0,1,...,N$ について、建設後の市民の延べ歩行距離を求めよ

公式pdfの解法1の途中までの $O(3^N N^2)$ 解法で、TLEになるはずなんだけど、通った。（計算量見積もり間違えてるかも？）

単純化して縦に敷く鉄道のみで考えると、鉄道を敷設する座標は街のどれかと一致させるのが最適となることが分かる。

たとえば、どの街のx座標でもない箇所に鉄道を敷いたとして

      |   200
300   |<-2-o     300 x 3 + 200 x 2 = 1300
 o-3->|

単純化のため各街の最寄りの路線が変化しないとして
左右のどちらかに1ずらす時のコスト変化を考えると、
どちらかは必ずコストを悪化させずにずらすことが出来る。
これを繰り返せば、左右適切な方の街のx座標までずらして、悪化することはない

 |        200
 |<---5----o     300 x 0 + 200 x 5 = 1000
 o
300

実際は途中で最寄りの路線が変化することもあるが、その場合

• ずらす前はこの路線が最寄りで、ずらしたことにより遠ざかり別の路線が最寄りとなった場合は、悪化するとしていたコストがそれ以上悪化しなくなる
• ずらす前は別の路線が最寄りで、ずらしたことにより近づきこの路線が最寄りとなった場合は、変化しないとしていたコストがより下がる

なので、どちらにしろ改善する。

横に敷く鉄道でも同じことが言えるので、敷設する意味のある候補は1つの街につき縦・横の2本で $2N$ 箇所に限られる。

問題では $K$ ごとに答えを求めよとあるが、実装上は $N$ 個の街に鉄道を敷設する・しないの $2^N$ パターンを全探索して、 敷設する街が $k$ 個なら $k$ 個の場合の答えを更新することにする。

ひょっとすると複数の街で敷設する路線がかぶり、通る街は $k$ 個でも実質的に敷設する路線は $k$ 本でないかも知れないが、最小値を求める上では特に気にしなくともよい。

敷設すると決め打った街が $k$ 個とすると、さらにそれぞれで縦・横の計 $2^k$ パターンがあるので、これもループ内で全探索する。

そこでやっと敷設すると決め打つ路線が確定するので、$O(Nk)$ 使って各街からの歩行距離を求め、人口を掛け合わせてコストを算出し、$K=k$ の場合の答えを更新する。

計算量は、$\displaystyle \sum_{k=0}^{N} {}_NC_{k}2^k Nk = 2 \times 3^{N - 1} N^2$ なので、$O(3^N N^2)$ となる。

各街からの歩行距離を求めるとき、$k$ 個の街については既に0であることが分かっているので飛ばすようにすると、

$\displaystyle \sum_{k=0}^{N} {}_NC_{k}2^k (N-k)k = 2 \times 3^{N - 2} (N-1)N$ となり、ざっくり $\frac{1}{3}$ くらいにはなる、はず。

また、Numbaを使わないと、この方法ではPyPyでもTLEだった。

敷設すると決め打つ街のbit集合ごとに、以下の2つのbit演算が必要になる。

• 敷設する街の個数 $k$ を数える
  • → '1' が立っている数(bit count)を数える
• 敷設する街それぞれに対して、縦に敷くか横に敷くかのパターンを全探索する
  • たとえば 1011 を 1001 と 0010 に分ける
  • → bit集合の部分集合を全探索する

'1' が立っている数のカウントは、素のPythonでは bin(x).count('1') が十分速いと言われているが、PyPyやNumbaでは文字列を介するので高速化の妨げとなる。

以下で示すようなアルゴリズムが使える。

• ビットを数える・探すアルゴリズム

また、bitの部分集合を全探索する方法は、以下のようなテクニックが使える。

• ビット演算
• bitによる部分集合の列挙 と 数学的理解 - Ark's Blog

以下の例では、$b$ を鉄道を敷設する街全体のbit集合、$v$ を縦に敷く街のbit集合、$h$ を横に敷く街のbit集合として、 $b$ で立っているbitの部分集合を $v$ が 全探索している。$v$ と $b$ のXORを取ることで、補集合 $h$ が得られる。

b = 0b001101101

v = b
while v:
    h = v ^ b
    print(f'{v:09b}')
    print(f'{h:09b}')
    v = (v - 1) & b  # ←この操作が鍵

ただし、この方法では $v = ∅$ だけは探索されないので、別途調べる必要がある。

F - Air Safety

• $N$ 機の飛行機が、全て同じ高度で飛んでいる
• 飛行機 $i$ は、現在、座標 $(X_i,Y_i)$ に位置し、方向 $U_i$ へ移動している
  • $U_i = \{$ 'U', 'D', 'L', 'R' $\}$ で、それぞれ $x$ 軸または $y$ 軸に平行な上、下、左、右を示す
• 飛行機の速度は全て1秒あたり $0.1$
• 飛行機が衝突するか判定し、衝突する場合は最も早いもので何秒後に衝突するか求めよ
• $1 \le N \le 2 \times 10^5$
• $0 \le X_i,Y_i \le 2 \times 10^5$
• 飛行機の初期位置は全て異なる

図入りの公式pdfがわかりやすい。

衝突する飛行機は、どういった向き・配置になっているか考えると、

• →と←、↓と↑の向かい合う機は、同じ直線上にあれば衝突しうる
• 縦横の軸が異なる組については、同じ45度線上にあれば衝突しうる

    ↓
  ・・・
→・・・←
  ・・・
    ↑

同じ45度線上に位置するかどうかは、$x+y$（＼）や $x-y$（／）が一致するかどうかで判定できる。

• ↑と↓: $x$ 座標が同じ
• →と←: $y$ 座標が同じ
• →と↑: $x+y$ が同じ
• →と↓: $x-y$ が同じ
• ←と↑: $x-y$ が同じ
• ←と↓: $x+y$ が同じ

なので、以下の情報を持っておく。

• $PLANES[u][0][v]=$ 方向が $u=\{U,D\}$ であり、$x$ 座標が $v$ である飛行機の $y$ 座標のリスト
• $PLANES[u][0][v]=$ 方向が $u=\{L,R\}$ であり、$y$ 座標が $v$ である飛行機の $x$ 座標のリスト
• $PLANES[u][1][v]=$ 方向が $u=\{U,D,L,R\}$ であり、$x+y$ が $v$ である飛行機の $x$ 座標のリスト
• $PLANES[u][2][v]=$ 方向が $u=\{U,D,L,R\}$ であり、$x-y$ が $v$ である飛行機の $x$ 座標のリスト

そして、方向の組み合わせ6組に対して、衝突しうる全ての飛行機の衝突までの時間を算出していく。
たとえば →と↓ の組なら、$x-y$ が同じになるものが衝突するので、$PLANES[R][2]$ と $PLANES[D][2]$ を使う。

両者に共通する $v$ があれば、そのリスト内の飛行機は衝突の可能性がある。

一方をソートし、もう一方を二分探索することで、衝突する飛行機の中で最も近いものと衝突するまでの時間が求められる。

軸が同じ（↑と↓、→と←）に関しては、距離の半分が衝突するまでの移動距離。なので距離x5が衝突までの時間。

軸が異なるもの（↑と→など）に関しては、$x$ 座標の差分がそのまま衝突までの移動距離。距離x10が衝突までの時間。

→
｜→
｜｜
｜｜  →
｜｜  ｜
｜｜  ｜  ↑
｜｜  ｜  ｜→
 1 2   4     7  : x+yが同じ→方向の飛行機のx座標リスト
           6    : x+yが同じ↑方向の飛行機の中の1つのx座標

[1 2 4 7] の中で 6 未満の座標である [1 2 4] は全て衝突するが、
その中でも最も大きいもの（4）が最も直近で衝突する。
これを二分探索なり尺取法で求める。

x座標の差が、そのまま衝突までの距離となる

計算量は、$N$ 機の飛行機の情報がPLANES内に分散するものの、

• ソートする必要のあるリストの要素数の総計…$O(N)$ → 計算量 $O(N \log{N})$
• 二分探索する要素数の総計…$O(N)$ → 計算量 $O(N \log{N})$

これは並列なので、まとめても $O(N \log{N})$ となる。