7/8記録

昨日参加したSoundHound Inc. Programming Contest 2018 -Masters Tournament-のC,D問題の復習をしました.
soundhound2018-summer-qual.contest.atcoder.jp

C問題
C: Ordinary Beauty - SoundHound Inc. Programming Contest 2018 -Masters Tournament- | AtCoder
まず$m = 2$のときを考えます.
$d = 0$のとき, 数列内の数字がすべて同じの時のみ美しさが1となり, すべての組み合わせは$n^2$通りであるため, 美しさの期待値は$\frac{1}{n}$となります.
$d \neq 0$のとき美しさが1となる2項組には$(1,d+1),(2,d+2) ... (n-d,n)$, また $(d+1,1), (d+2,2) ... (n , n-d)$の$2(n-d)$個の組み合わせがあります. ２項組のすべての組み合わせは$n^2$であるため, $m = 2$のときの美しさの期待値は$\frac{2(n-d)}{n^2}$となります. $ m $が2より大きいとき $m - 1$個の2項組に対しても同じ式が成り立つことがわかります. 期待値の線形性により, これらを足し合わせたものが答えとなるので$m = 2$の場合の式を$m - 1$倍すればよいです.
提出したもの
Submission #2811890 - SoundHound Inc. Programming Contest 2018 -Masters Tournament- | AtCoder

$O(1)$の数学問題はなかなか思いつけないです.

D問題
D: Saving Snuuk - SoundHound Inc. Programming Contest 2018 -Masters Tournament- | AtCoder
2都市間を移動する電車のコストは向きに関わらず等しいので, 無向グラフとみなせます. 一度両替をするともう両替はできないので, 両替をする都市を探索します. そのために, ①スタート地点から両替する都市への最短コスト経路と②両替する都市からゴール地点での最短コスト経路 を求める必要がありますが, これは無向グラフとみなせるのでゴールから両替する都市への最短コスト経路を求めても同じです. よってダイクストラ法を2回用いることで各々を求められます. また, $i$年後に$i$番目の両替所が使えなくなるので, 解を作るときは$n-1$年後の自明な解($n-1$年後は両替できる都市がひとつしかない)から年数を巻き戻していき, 最小値を年ごとに更新していくと$O(n)$で解を生成できます.
提出したもの
Submission #2813641 - SoundHound Inc. Programming Contest 2018 -Masters Tournament- | AtCoder

競プロはじめてはじめてのダイクストラ法です.