SoundHound Inc. Programming Contest 2018 -Masters Tournament-

SoundHound Inc. Programming Contest 2018 -Masters Tournament- に参加しました！
SoundHound Inc. Programming Contest 2018 -Masters Tournament- 旧版
 SoundHound Inc. Programming Contest 2018 -Masters Tournament- beta版

解けた問題だけ解説をしていきますー

要項

SoundHound Inc. Programming Contest 2018 -Masters Tournament-
rated 2000
7/7(日) 21:00 ～ 23:00 (100分)
100-200-300-400-600 (5問)
ペナルティ: 5分

方針

企業コンテストである以上、典型アルゴリズム知識が多めになるはず
少なくとも4完はしたいところ

A - F

実際に $a+b$ 、 $a*b$ を試し、その結果で場合分けを行えば良いです。

B - Acrostic

言語によりますが、文字列の $n$ 番目を取り出す方法が用意されていると思います。
今回の問題の場合、 $0$ 番目、 $w$ 番目、 $2w$ 番目…という値を繋げた結果を返せば良いので、
for (int i = 0;i < S.length;i += w)として $i$ 番目を順次出力すれば良いです。

こういう問題はまず小さいケースで実験を行います。
最小のケースは $m=2$ の時で、まずこれを並べてみましょう。
(1, 1) (1, 2) (1, 3) ... (1, n)
(2, 1) (2, 2) (2, 3) ... (2, n)
⋮
(n, 1) (n, 2) (n, 3) ... (1, n)
これを考えると、差が0の要素は $n$ 個、差が $d$ 個の要素は $2(n-d)$ 個あることが分かります。
次に、 $m=3$ の時を考えます。仮に $n=2$ としましょうか。
(1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 2, 2)
(2, 1, 1)
(2, 1, 2)
(2, 2, 1)
(2, 2, 1)
…
ここで、全部を列挙する前に、何か特徴が無いか考えます。
すると、次のような事実に気が付くと思います。

差の出現数は1個目から2個目の個数と2個目から3個目の個数で等しい (共に $d=0$ が4つ、 $d=1$ が4つ)

これは期待値の和は和の期待値という性質に基づくもので、この性質より次のことが分かります。
$2$ 個の $n$ 種類の要素を持つ数列の美しさが $f(n, d)$ と分かっているとき、 $m$ 個の $n$ 種類の要素を持つ数列の美しさは $f(n, d) \cdot (m-1) \cdot n^{m-2}$ である。
平均を出す必要があるので、答えは $\frac{f(n, d) \cdot (m-1) \cdot n^{m-2}}{n^m} = \frac{f(n, d) \cdot (m - 1)}{n^2}$ です。
ただし $f(n, d)$ は $d=0$ の時 $n$ 、それ以外の時 $2(n-d)$ を返すものとします。

D - Saving Snuuk

典型的なDijkstra法の問題です。
結局、問題としては $s$ からある両替所まで最短で移動し、そこで両替を行ってから $t$ へ最短で向かうということになります。
両替する都市を $q$ として考えます。
まず、Dijkstra法ではある都市から他の全ての都市への最短経路を $O(m+n \log n)$ で導出します。
この方法を用いて、 $s$ から他の都市への円での最短経路、 $t$ から他の都市へのスヌークでの最短経路を導出します。
後は、 $q$ を全探索すると、ある $q$ について既に $s$ と $t$ への最短経路は導出済みなので $O(1)$ で求めることができ、結局 $i$ を $O(n)$ で導出できます。
これをソートしておき、出力したいですが……ここまで来て計算量 $O(n^2)$ で出力したくないですよね？
そこで、次のような方法で出力していきます。ただし、ソート済みの都市順はキューなどのデータ構造で管理しているものとします。

$i=0$ とします
データ構造の先頭にある都市を取り出します
その都市が $i$ 以下の番号ならば捨てて、2に戻ります
料金を出力します
$i++$ を行い、結果が $n$ 未満なら2に戻ります

この方法では $O(n)$ で答えを出力できるので、最終的に計算量は $O(m+n \log n)$ で導出できますね。
もしTLEやWAなら、次の点に注意してみましょう。

オーバーフローを起こしてないか？
計算量が間違えてないか？(例えばDijkstra法に優先度付キューを用いている場合、C++のデフォルトのpriority_queueは降順です！昇順ではないです！)
条件のミスをしていないか？(例えば両替できない都市の誤読とか)
誤読してないか(両替は1回しかできず、全額両替です！)

結果

ooox- 3完(600点) 24:20-26:10-51:20(4WA) : 71:20
663位パフォーマンス: 1377
レート: 1754→ 1721(-33)

感想

Dijkstra法、ここまでバグらせるとは思わず
皆さんは予め最短経路問題3点セットことWarshall-Floyd法、Bellman-Ford法及びDijkstra法はライブラリとして持っておきましょうね！
Warshall-Floyd法は $O(V^3)$ のアルゴリズムで、任意の頂点間の最短経路が求められる非常に簡潔なアルゴリズムです。
Bellman-Ford法は $O(VE)$ のアルゴリズムで、ある頂点から他の任意の頂点への最短経路が求められるアルゴリズムです。
Dijkstra法は $O(E+V \log V)$ のアルゴリズムで、負の経路が存在しないグラフである頂点から他の任意の頂点への最短経路が求められるアルゴリズムです。
それぞれ使う場面が異なるので、是非覚えておきましょう！