SoundHound Inc. Programming Contest 2018 参加記

SoundHound Inc. Programming Contest 2018 -Masters Tournament- - AtCoder

reted企業コンに参加しました。みなさんおつかれさまでした。個人的には過去最高パフォーマンスが出てとてもうれしいです。

A,B問題(100,200)

100点、200点の中でもかなり易しい問題だったと思います。

C問題(300)

前の2問が簡単だったの比べてけっこう難しい見た目をしています。実際難しかったです。僕は問題文を見ているうちに旧ABCの期待値の問題(C - コイン)を思い出していました。この問題の教訓から、なにかを固定して考えるといいのではと思いつきました。少ない数で実験してから「条件を満たすペアの位置」を固定して考えるとよさそうだと気付きそこからはスムーズに解が求まりました。

D問題(400)

最短経路問題なので制約からダイクストラ法を念頭に置きながら考えます。円からスヌークへの両替が一方通行なので別々に考えたいと思い、円の世界とスヌークの世界にグラフを分離します。すると頂点iで両替するときの総コストは(円でsからiへ行く最小コスト)+(スヌークでtからiへ行く最小コスト)で求まります。あとは円でs始点、スヌークでt始点のダイクストラをして1~Nで両替した時の総コストをiとpairにしてソートすれば答えにたどり着きます。

E問題(600)

奇数頂点の閉路でかなり束縛されることまでは考察しました。距離の偶奇でそこを見つけても実際どうしたらいいのかうまく形にできなかったので断念。なにかひとつの解が求まれば二分探索できそうなのになあと思っていた。

感想

記事にまとめるのってかなり大変ですね。