乐胖代购免代理版

SoundHound Programming Contest 2018 Masters Tournament 本戦 - AtCoder

3週間ほど前に行われた予選では、残り2分で全完という快挙（？）を成し遂げ…なんと本戦に参加することができました！

当初の予定より参加枠が増えたようで…かなりギリギリで通ってた*1と思うので、とてもありがたいです。

そして結果は…1完の40人中37位。うーん…参加者のレベルがとても高いので順位はそこまで気にしないですが、せめて2問は解きたかった。悔しいです。

f:id:betrue12:20180730211302p:plain

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を使った貪欲ができないか考えたり、 $O(N^{2})$ のDP*2を考えていましたが…正しいDPが見えず。解けそうなものがないかとB～Dを行ったりきたりするだけで1時間ほど費やしてしまいました…

「薬品列（ $1, 2, ..., N$ ）の $i$ 番目までだけを考える部分問題においての、効用の最大値」を dp[i] とするDPを考えます*3。このとき、実際の問題においては $i$ 番目が薬品列の途中だったとしても、部分問題においては $i$ 番目が薬品列の端だとして考えます。つまり効用を0にする長さ $K$ の区間が $i$ 番目より右にはみ出ることを許しません。

このようなDPを考えると、 dp[N] が答えとなります。そしてこのDPの遷移は、 $i$ 番目の薬品を使うか使わないかを場合分けして次のように考えられます。

f:id:betrue12:20180730221354p:plain

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クエリの処理の際には、クエリで与えられた頂点 $u$ と連結な頂点を探す必要があり、これは隣接リストを使ったBFS/DFS等で最大 $O(N)$ かかります。1クエリの中で $O(N)$ の処理をするのは非常に危険ですが、これは頂点の「縮約」によって回避することができます。完全グラフ化した頂点は縮約してしまうことで、BFS/DFSで探索したぶんだけ頂点数がどんどん減っていき、「問題中の全てのcompleteクエリの合計で」訪れる頂点数が高々 $O(N+Q)$ 個になります。

以上の内容をまとめると、addクエリで直接追加された辺を管理し続ける「縮約しないグラフ」と、連結性およびcompleteクエリによる縮約状況を管理する「縮約するグラフ」の2つを考え、それぞれから別々の情報を得ていくことになります。それぞれに対する操作は以下の表の通りです。

クエリ	縮約しないグラフ	縮約するグラフ
add	元の頂点番号を使い、辺集合(set)に追加	縮約後の頂点番号を使い、隣接リスト等に追加
complete	何もしない	隣接リストを用いて頂点 $u$ と連結な頂点番号を探索し、Union-Findで併合し、頂点を縮約
check	辺集合に存在すれば `Yes`	Union-Findで併合されていれば `Yes`