SoundHound Programming Contest 2018 Masters Tournament 本戦 参加記録
SoundHound Programming Contest 2018 Masters Tournament 本戦 - AtCoder
3週間ほど前に行われた予選では、残り2分で全完という快挙（？）を成し遂げ…なんと本戦に参加することができました！
当初の予定より参加枠が増えたようで…かなりギリギリで通ってた*1と思うので、とてもありがたいです。
そして結果は…1完の40人中37位。うーん…参加者のレベルがとても高いので順位はそこまで気にしないですが、せめて2問は解きたかった。悔しいです。
5問のうち、コンテスト後に通せたものを含むA, B, Dを振り返っていきます。
A - Feel the Beat
曲のBPMのほうを2で割っていくと、小数が出たり範囲内の曲数を把握しにくかったりして計算しづらいです。逆に140～170のほうを2倍していくと楽です。
- スマートなACコード：Submission #2923471 - SoundHound Programming Contest 2018 Masters Tournament 本戦
- 本番コード（場合分けが細かい）：Submission #2912893 - SoundHound Programming Contest 2018 Masters Tournament 本戦
B - Neutralize
本番中はSegTreeを使った貪欲ができないか考えたり、 のDP*2を考えていましたが…正しいDPが見えず。解けそうなものがないかとB～Dを行ったりきたりするだけで1時間ほど費やしてしまいました…
「薬品列（ ）の
番目までだけを考える部分問題においての、効用の最大値」を
dp[i] とするDPを考えます*3。このとき、実際の問題においては 番目が薬品列の途中だったとしても、部分問題においては
番目が薬品列の端だとして考えます。つまり効用を0にする長さ
の区間が
番目より右にはみ出ることを許しません。
このようなDPを考えると、 dp[N] が答えとなります。そしてこのDPの遷移は、 番目の薬品を使うか使わないかを場合分けして次のように考えられます。
dp[i] = max(dp[i-1] + b[i], dp[0], dp[1], ..., dp[i-K]) *4 という遷移ができます。 max(dp[0], dp[1], ..., dp[i-K]) が必要ですが、左端は dp[0] で動かないので、DPを進めるごとに逐次maxを取れば大丈夫です。
ACコード：Submission #2915356 - SoundHound Programming Contest 2018 Masters Tournament 本戦
余談ですが、公式解説のDPがよく分かりません…
C - Not Too Close
解説読んだけど遷移が全然頭に浮かばず…頭が元気なときに考えます。
D - Propagating Edges
本番中は順位表を見たところCより多く解かれていたので挑戦してみました。まあまあ惜しいところまで行ったような、そうでもないような…。
公式解説の繰り返しになってしまいますが、「addクエリで直接追加された辺」と「completeクエリによる完全グラフ化で追加された辺」は分けて考えると良いです。checkクエリでは、どちらかで辺が追加されていれば Yes を出力します。
addクエリで追加された辺はset等を使って直接管理します。
completeクエリではグラフの一部が完全グラフ化するため、「完全グラフ化した頂点集合」を管理したくなります。Union-Findを用いれば良さそうです。
completeクエリの処理の際には、クエリで与えられた頂点 と連結な頂点を探す必要があり、これは隣接リストを使ったBFS/DFS等で最大
かかります。1クエリの中で
の処理をするのは非常に危険ですが、これは頂点の「縮約」によって回避することができます。完全グラフ化した頂点は縮約してしまうことで、BFS/DFSで探索したぶんだけ頂点数がどんどん減っていき、「問題中の全てのcompleteクエリの合計で」訪れる頂点数が高々
個になります。
以上の内容をまとめると、addクエリで直接追加された辺を管理し続ける「縮約しないグラフ」と、連結性およびcompleteクエリによる縮約状況を管理する「縮約するグラフ」の2つを考え、それぞれから別々の情報を得ていくことになります。それぞれに対する操作は以下の表の通りです。
| クエリ | 縮約しないグラフ | 縮約するグラフ |
|---|---|---|
| add | 元の頂点番号を使い、辺集合(set)に追加 | 縮約後の頂点番号を使い、隣接リスト等に追加 |
| complete | 何もしない | 隣接リストを用いて頂点 |
| check | 辺集合に存在すれば Yes |
Union-Findで併合されていれば Yes |
ここまで公式解説と同じですが…イメージが付きやすいように、図を描きます。
実装上は、縮約後の代表頂点番号としてUnion-Findにおける根ノードの番号を使い、縮約直後に代表頂点番号の隣接リストを空にしてしまうとよいです*5。連結な頂点を全て縮約してしまった直後は、その頂点はどことも繋がっていないはずなので。
ACコード：Submission #2915854 - SoundHound Programming Contest 2018 Masters Tournament 本戦
を見た瞬間にRubyだと厳しいことを悟るので、C++での実装です。
本番中は、「addクエリで連結になった」と「completeされた」という情報をともに1つのUnion-Findの中に持たせようとして失敗しました…。
E - Hash Swapping
本番中は全く手をつけなかった問題。
平衡木の知識がないのですが、解説の最後にあるSegTreeを用いた解法はなるほどと思いました。そのうち、これで実装してみたいです。
おまけ
せっかくのオンサイトコンテストだったので、当日会場での話も少しだけ。
台風が来ていたのでどうなることかと思いましたが、奇跡的に行きも帰りも全く雨に降られずに済みました。
当日いただいた、Tシャツとボールペン（写真だと見えないですがSoundHound Inc.と印字されています）。初めての競プロTシャツゲット！
こちらはちょくだいさんから頂いたAtCoderステッカー。Twitterで見かけたときから欲しかった一品。
写真はないですが、コンテスト前にはお菓子を頂き（おいしかったです）、コンテスト終了後には懇親会もありました。参加者には社会人しかいないということで、私は飲んでないですがお酒もありました。
懇親会では全ての人が初めまして状態だったのでどうしようかと思っていましたが、京都からいらっしゃった橙コーダーの方とずっとお話させていただきました。ありがとうございました…！
SoundHound社の紹介もしていただきました。何年前か忘れましたが、たまたま鼻歌検索のアプリを知って「スゴイ！」と思った記憶があります。こんな形で関わりが持てるとは…。
という感じで、非常に楽しいオンサイトコンテストでした。また何かの機会で参加できるように、実力を付けていきたいです。
