KEYENCE Programming Contest 2019 E,F問題メモ
E - Connecting Cities
問題
- $N$ 個の都市が一直線に並ぶ
- それぞれの規模は、$a_1,a_2,...,a_N$
- 都市間を結ぶ $N-1$ 本の道路を建設して、どの都市からどの都市へも行けるようにしたい
- つまり、グラフ理論でいう全域木を作りたい
- $i$ 番目の都市と $j$ 番目の都市を結ぶ道路の建設コストは、定数 $D$ を使って、以下の通り
- $(j-i)\times D+a_i+a_j$
- 最小コストを求めよ
- $2 \le N \le 2 \times 10^5$
解法
いろいろ解き方があるらしい。
最小全域木（Minimum Spanning Tree）問題なのだが、どの頂点とどの頂点を結んでもよいので、辺が$N(N-1)/2$本と見なせる。 MSTの基礎的な解法であるクラスカル法では、$O(E \log{V})$ で、とても間に合わない。
コストが定式で表されているので、その特徴を利用して、無駄な辺を除外する。
解説の解法
解説の解法の図化は、このサイトが詳しい。
- 各都市につき、自分から繋ぎにいく候補道路は、多くとも左右それぞれ1本ずつでよい
- あくまで「自分より規模の小さい都市」の中の話で、他の規模の大きい都市から自分が繋がれる対象になることはある
- その道路とは、「自分より左にある自分より規模の小さい都市の中で、建設コスト最小のもの」と「自分より右にある（以下同）」
- 理由は以下
- 次の2つを念頭に置く
- 全域木を作るのに、任意の3頂点を結ぶ3辺の全てを使うことはありえない。少なくとも、3辺の中で最長の辺は使われない
- 建設コストは、「距離が遠く」「規模が大きい」ほど高くなる
- 都市 $w$ に着目する
- 自分の左にある自分より規模の小さい2都市$(u<v)$を選ぶ
- $(u,v)$を結ぶ道路は、$(u,w)$ を結ぶ道路より、距離も近いし規模も小さいので、最長ではあり得ない
- なので、最長は、$w$ から出る2本の内のどちらか。この2本の比較で長い方は使われない
- これを任意の2都市でやっていくと、結局はその中でコスト最小の辺しか使われない
- 右も同様
で、規模の小さい都市から更新しつつ区間の最小値を求めるにはセグメント木を使えば良いのだが、Pythonではそれでも遅い。
高速な解法
証明がよくわかっていない。
サンプル4などを、実際にどの都市とどの都市が結ばれるのかやってみると、特徴的な結果になる。
,-------------------,-----------, 43 94 27 3 69 99 56 25 8 15 46 8 | | `--'|'--' | | `--' `--' `--' | `------'|`------' | `----------' `----------'
3,8,8をハブとして、周辺都市が全てそこと結ばれた上で、隣接するハブ同士が結ばれる構造となっている。
これが、都市の数が大きくなっても成り立つのでは？
- ハブ都市を検出する
- ハブ都市間の都市は、左右直近のハブ都市のコストが低い方と結ぶ
- 隣接するハブ都市を結ぶ
ハブ都市の検出は、（自分より規模が小さいという条件無しで）各都市から見た左右それぞれのコスト最小都市を計算し、「左からも右からも対象とされている」都市のみを抜き出すと、なんか知らんが上手くいった。
F - Paper Cutting
問題
- 長方形の紙がある
- 水平方向に $H$ 本、垂直方向に $W$ 本、点線が入っている
- この内、点線に従って一直線に $K$ 回切る
- 切るときに、「切った直後の紙の枚数」のコストがかかる
- さて、$K$ 回の切り方として考えられる順序の全てを試したとき、コストの合計を $\mod{10^9+7}$ で求めよ
- $1 \le H,W \le 10^7$
解法
数学問題? 理屈さえわかれば数式で表現できるので、それを求めるだけ。階乗を求める必要があるので計算量は$O(K)$ではあるが、本当に$K$回、数をかけるだけで、他は$O(1)$で実装できる。
解説の解法は、読めば簡単に理解出来るくらい単純ですごい！綺麗！となるんだけど、思いつかんわ……。
$H,W$ が大きいので、1マス毎に数えるのは、動的計画法などを使っても無理。
横に切った回数 $h$ と縦に切った回数 $w$ で、$h+w$ 回目のコストは$(h+1)(w+1)$として求められる。そこに、そのように切る瞬間を含む切り方の数をかける。これを、全ての$h,w$について求める、というのがまず思いつく方法だが、これも計算量が$O(HW)$となり無理。
以下では、さらに$k=h+w$として$k$が同じ$h,w$をまとめて式変形を重ねることで、計算量を$O(K)$としている。
解説では「紙片の数と一対一に対応するもの」として、「マス(i,j)が紙片の左下になっているものの数」としている。
そうすると、「$i$ 番目の横線と $j$ 番目の縦線がともに切られた瞬間から、以降その紙片については毎回1コストずつかかる」と言い換えることができる。
これは多くのマスで期待値が等しくなるので、たった3通りのパターンさえ考えればよくなる。
- 最も左下 (0, 0)
- 最も左または最も下 (i, 0), (0, j)
- それ以外 (i, j)
($t$ 回目にはじめて$(i,j)$が紙片の左下になる切り方の数)×(以降の操作回数 $K-t+1$) を、$t=1..K$ まで合計すればよい。$\sum{k}$ や $\sum{k^2}$ の公式を利用すると簡単になる。
def solve(h, w, k):
n = h + w
MOD = 10 ** 9 + 7
if k == 1:
return 2 * n
ans = 0
# (0, 0) ... k * nPk * 1
ans += k * n * (n - 1) % MOD
# (i, 0) (0, j) ... sum(t for t=1..k) * (n-1)P(k-1) * (h+w)
tmp = k * (k + 1) // 2 * (n - 1) % MOD
ans += tmp * n % MOD
# (i, j) ... sum((t-1)(k-t+1) for t=1..k) * (n-2)P(k-2) * 2 * h*w
# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ = (k-1)k(k+1)/6
tmp = (k - 1) * k * (k + 1) // 3 % MOD
ans += tmp * h * w % MOD
for m in range(n - 2, n - k, -1):
ans = ans * m % MOD
return ans % MOD
h, w, k = map(int, input().split())
print(solve(h, w, k))
