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
実際に、を試し、その結果で場合分けを行えば良いです。
B - Acrostic
言語によりますが、文字列の番目を取り出す方法が用意されていると思います。
今回の問題の場合、番目、番目、番目…という値を繋げた結果を返せば良いので、
for (int i = 0;i < S.length;i += w)として番目を順次出力すれば良いです。
C - Ordinary Beauty
こういう問題はまず小さいケースで実験を行います。
最小のケースはの時で、まずこれを並べてみましょう。
(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の要素は個、差が個の要素は個あることが分かります。
次に、の時を考えます。仮にとしましょうか。
(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個目の個数で等しい (共にが4つ、が4つ)
これは期待値の和は和の期待値という性質に基づくもので、この性質より次のことが分かります。
個の種類の要素を持つ数列の美しさがと分かっているとき、個の種類の要素を持つ数列の美しさはである。
平均を出す必要があるので、答えはです。
ただしはの時、それ以外の時を返すものとします。
D - Saving Snuuk
典型的なDijkstra法の問題です。
結局、問題としてはからある両替所まで最短で移動し、そこで両替を行ってからへ最短で向かうということになります。
両替する都市をとして考えます。
まず、Dijkstra法ではある都市から他の全ての都市への最短経路をで導出します。
この方法を用いて、から他の都市への円での最短経路、から他の都市へのスヌークでの最短経路を導出します。
後は、を全探索すると、あるについて既にとへの最短経路は導出済みなのでで求めることができ、結局をで導出できます。
これをソートしておき、出力したいですが……ここまで来て計算量で出力したくないですよね?
そこで、次のような方法で出力していきます。ただし、ソート済みの都市順はキューなどのデータ構造で管理しているものとします。
- とします
- データ構造の先頭にある都市を取り出します
- その都市が以下の番号ならば捨てて、2に戻ります
- 料金を出力します
- を行い、結果が未満なら2に戻ります
この方法ではで答えを出力できるので、最終的に計算量はで導出できますね。
もし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法はのアルゴリズムで、任意の頂点間の最短経路が求められる非常に簡潔なアルゴリズムです。
Bellman-Ford法はのアルゴリズムで、ある頂点から他の任意の頂点への最短経路が求められるアルゴリズムです。
Dijkstra法はのアルゴリズムで、負の経路が存在しないグラフである頂点から他の任意の頂点への最短経路が求められるアルゴリズムです。
それぞれ使う場面が異なるので、是非覚えておきましょう!