AtCoder Beginner Contest 180 D,E,Fメモ

AtCoder Beginner Contest 180

巡回セールスマンが水Diffとかすごい時代ですね。

D - Takahashi Unevolved

• 整数 $X$ に以下の2通りの操作を好きな順で繰り返す
  • $A$ 倍する
  • $B$ を足す
• $X$ が $Y$ 以上にならない範囲で、操作できる最大回数を求めよ
• $1 \le X \lt Y \le 10^{18}$
• $2 \le A \le 10^9$
• $1 \le B \le 10^9$

各操作、$X$ を小さく保てる方を貪欲に選べばよい。但しそのままシミュレーションするとTLE。

$A$ 倍は重ねる毎にすごい勢いで増え方が増すので、最初は $A$ 連打、どこかから $B$ 連打がよい。 $A$ 倍の回数は高々60回程度。ここまではシミュレートすれば良い。

$B$ を選択した方がよくなったところで、$Y-X$ を $B$ で割ると、残り $B$ を足す操作を行える回数が一発でわかる。

Python3

E - Traveling Salesman among Aerial Cities

• 3次元空間上に空中都市が $N$ 個ある
• $i$ 番目の都市は $(x_i,y_i,z_i)$ にある
• $(a,b,c)$ から $(d,e,f)$ に行くには、$|d-a|+|e-b|+\max(0, f-c)$ のコストがかかる
• 都市1から全ての都市を1度以上経由して都市1に戻る最小コストを求めよ
• $2 \le N \le 17$

移動は、$x,y$ 軸方向はマンハッタン距離、高さ方向は上りはマンハッタンだが、下りはコスト不要、という具合になっている。

コストが有向なことと、三角不等式を満たすかどうかに注意。

今回、都市 $1→2$ と $2→1$ のコストが異なる。 よって、どこから始めてもいいわけではなく、ちゃんと問題文の通りに都市1から始めて、都市1に戻るコストを求める必要がある。

また、三角不等式とは3つの都市 $i,j,k$ について $dist(i→k) \le dist(i→j)+dist(j→k)$ となる関係のことだが、 これが成り立たない場合「$i→k$ に行くなら、直接行くより $j$ を経由した方が近道」となってしまい、 都市 $i,k$ の座標から求めた距離が、必ずしも最短ではなくなってしまう。 その場合、Floyd-Warshallなどで全点間最短距離を事前に求めておかないと、2都市間の真の最短距離がわからなくなる。

今回の場合はそのようなことが無いので、2点間の座標から最短距離が求められる。

都市 $2～N$ の巡回セールスマンを解く。

初期値として、各都市、その1都市だけしか訪問していない場合のコストに都市 $1$ からの距離を入れておく。

各都市 $i$ について、全都市を経由しつつ $i$ を最後に訪れた場合の最小コストに、都市 $i→1$ のコストを加算したものを計算し、 その中の最小コストが答えとなる。

$O(2^NN^2)$

Python3

何かbit操作でややこしい書き方しちゃってる感。

F - Unbranched

• $N$ 頂点 $M$ 辺の単純とも連結とも限らない無向グラフで、以下の条件を満たすものの個数を $10^9+7$ で割ったあまりで求めよ
  • 自己ループはない
  • 全ての頂点の次数は2以下
  • 最大の連結成分のサイズはちょうど $L$
• 頂点は区別する
• 辺は区別しない
• $2 \le N \le 300$
• $1 \le M \le N$

2次元DP。遷移がこんがらがらがる。

まず、頂点の次数が2以下なので、連結成分は以下に分類できる。（孤立点もパスに含められるけど、数え上げの際に例外的なので分けて考える）

• 孤立点
• パス（○ー○ー○）
• サイクル

これに基づいて、以下のDPで連結成分の作り方を数えていく。

• $DP[i][j]=$ 頂点を $i$ 個、辺を $j$ 本使った場合のパターン数

ある状態から、次に1つ新しい連結成分を作る場合の数は、「頂点の選び方」×「選んだ頂点の繋ぎ方」となる。

頂点の選び方は連結成分のサイズによって、繋ぎ方は分類（パスかサイクルか）によって異なる。
また、消費する辺の個数も分類に依存し、パスなら（サイズ－1）、サイクルならサイズと同数となる。

選び方を数え上げるに当たっては、ダブりに注意。
たとえば連結成分を2個生成する場合、どちらを先に生成しても全体としての場合の数は1つなのに、ダブって数えられることがあってはならない。
解説pdfにあるように「まだ決まっていない頂点の中で最も番号の小さいものを含む成分について決める」と考えると、重複が防止できる。

もらうDPを考えると、ある $i,j$ について遷移元となるのは以下のようになる。

  j ..  7  8  9 10 ..
i                        ●: 計算中のi,j
..  □ △                ○: 孤立点を生成したときの遷移元
..     □ △             △: パスを生成したときの遷移元（サイズ上限 $L$ まで）
 9        □ △          □: サイクルを生成したときの遷移元（サイズ上限 $L$ まで）
10              ○
11              ●

孤立点の場合、その1点を確定させるだけなので1通りしかない。

• $DP[i][j]+=DP[i-1][j]$

パスの場合、各サイズ $S=2～L$ につき、

• 頂点の選び方が ${}_{N-i+S-1}C_{S-1}$（まだ決まっていない最小番号の頂点1点は確定で、残りの $S-1$ 個の選び方）
• 頂点の繋ぎ方が $\dfrac{S!}{2}$
• $DP[i][j]+=DP[i-S][j-S+1] \times {}_{N-i+S-1}C_{S-1} \times \dfrac{S!}{2}$

サイクルの場合、各サイズ $S=2～L$ につき、

• 頂点の選び方は同上
• 頂点の繋ぎ方が $\dfrac{(S-1)!}{2}$（ただし $S=2$ のとき $(S-1)!$）
• $DP[i][j]+=DP[i-S][j-S] \times {}_{N-i+S-1}C_{S-1} \times \dfrac{(S-1)!}{2}$

これを1個1個計算していけばよい。

最終的に $DP[N][M]$ を参照するが、これは「最大連結成分が $L$ 以下」のパターン数となる。 よって、$L$ を $L-1$ としたものについても同様に求めると、その差分で $L$ ちょうどのパターン数が求められる。

計算量は $O(NML)$ だが、$L$ にあたる部分は $DP[i][j]$ の更新では $\min(i,j,L)$ 個までしか参照されないので、だいたい3分の1くらい？になる。

Python3