ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

SoundHoundコンテスト予選 参加記録

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

既卒者(社会人etc.)限定オンサイトコンテストの予選。また、レート2000未満の参加者にとってはratedなコンテストでもありました。ABCとARCの中間くらいですね。

結果は133分台全完で121位!最後2分でEが通りました…前回といい今回といい、ギリギリの時間で1問通ることが最近多くて心臓に悪いです。

f:id:betrue12:20180708093336p:plain

パフォーマンスは2200超えで申し分ないのですが、オンサイト枠に入れているかどうかは…うーん。無理かなあ。

全問振り返っていきます。

A - F

A - F

書いてあるとおりにif文で分岐すればOK。久々にratedで100点問題を解きました。問題名のFは16進数で15という意図だと思います。

ACコード:Submission #2801575 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-

B - Acrostic

B - Acrostic

先頭を0文字目として  0, w, 2w, 3w, ... 文字目を順番に出力すればOK。文字数が  \frac{|S|}{w} の切り上げになるので、整数割り算の切り上げは書けるようになっておきましょう。

ACコード:Submission #2803017 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-

問題名のAcrosticの意味については以下参照。「縦読み」みたいなものですね。

折句 - Wikipedia

C - Ordinary Beauty

C - Ordinary Beauty

取りうる数列の数が  n^{m} と非常に多いので、簡単な計算方法を考えなければいけません。

素数 m なので、隣り合う2項の間は  m-1 個あります。実はこの  m-1 個を、独立に考えることができます。

試しに  n = 3, m = 3 の時の場合を全列挙してみましょう。

f:id:betrue12:20180708095511p:plain

このとき、  (a_{1}, a_{2}) に着目すると、これらの値が  (1, 1) となるのは3通り。同じように  (1, 2) も3通りであり、全てのペアが3通りという等しい数で登場します。

そしてこれは、 (a_{2}, a_{3}) にも同じことが言えます。上の表だと位置がバラけていますが、全てのペアが3通りずつ登場していることが分かります。

これは  n, m が一般の場合でも同じことが言えます。そのため、

  1. 隣り合う2項だけを考え、その全ての場合(  n^{2} 通り)に対して、差が  d となる場合を数える。差が  d となった場合美しさは+1、そうでない場合+0されるので、平均は(差が  d となる場合の数)/(全ての場合の数)となる。*1
  2. それを「隣り合う2項の間」の数、つまり、  (m-1) 倍する。

と、問題を単純化することができます。あとは、「2つの数の差が  d となる場合の数」を求めれば解けます。  d = 0 のときだけ特殊なので注意しましょう。

f:id:betrue12:20180708101119p:plain

ACコード:Submission #2804184 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-

D - Saving Snuuk

D - Saving Snuuk

問題文が長いので頑張って整理しましょう。

  • 頂点  s からスタートし、円を使って両替所のある点のどこかに移動する。
  • ここで両替をして、スヌークを使って頂点  t に移動する。
  • 使った金額の合計を最小化したい。

こうなります。そして、両替所は年々減っていくので、それぞれの年について金額合計の最小値(正確にはそれを  10^{15} から引いた値)を求めたい、という問題です。

この  s \rightarrow (どこか) \rightarrow t という感覚を持つことが大事で、 s からどこかまでの円での移動と、どこかから  t までのスヌークでの移動についてそれぞれ最小金額が求められれば、それを組み合わせることで合計金額を最小化できそうです。

そこで最短路問題を解くダイクストラ法の出番です。ただし、ナイーブなダイクストラ法は  O(n^{2}) で通りそうにないので、プライオリテイキューを用いた  O(m \log n) のほうを使いましょう。始点を  s とする円でのダイクストラと、終点を  t とするスヌークでのダイクストラ…なのですが、今回は無向グラフなので  t を始点として考えても問題ないです。

めでたく両方の最短路問題が解けたら、次は「どこの両替所を使うか?」を考えます。最初は  1, 2, ..., n 全ての両替所が使えますが、どんどん減っていって最後は都市  n でしか両替できなくなります。毎回全ての候補を試していると  O(n^{2}) になってしまいます。

こういう時はどんどん候補が増えていく順番で考えると効率的です。今回は時間順に考えると候補が減っていくので、時間を逆回しすると良いです。

都市  n でしか両替できない状態では、候補が1通りなので自動的に決まります。次に都市  n-1, n が使える場合、候補が1つ増えたので、さっきの値と  n-1 を使ったときの値を比べて良いほうをとります。このようにして、「それまでの最適値」と「新しく使えるようになった都市を使ったときの値」を比較することで、効率的に計算できます。

ACコード:Submission #2807882 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-

RubyだとTLEしたのでC++に切り替えました…

E - + Graph

E - + Graph

木とは限らない連結グラフ、ということは閉路があるかもしれません。そのため、「どの辺  i についても、頂点  u_{i} v_{i} に書かれた正の整数の和は  s_{i} に等しい」という条件が結構厳しそうに思います。

状態数が多いので、なんとか仮決めして考えやすくしたいです。全ての辺について和の制約があるので、もし1点の値を固定すれば、DFSやBFSによって全ての値を決めることができます。

仮に頂点1の値を「0」とします。仮に固定しただけで、この時点では頂点1の値に制約は見つかっていません。またこの時点では、「正の整数」という制約は一旦考えないことにします。これから、「頂点1の値の取り方にはどんな制約があるか?」をグラフ探索によって見つけていきます。

f:id:betrue12:20180708110717p:plain

左端を頂点1だと思ってください。このように、隣り合う辺の値が順番に決まっていきます。マイナスがありますが、とりあえず気にしません。

このとき、固定した点を赤として、その隣を青、その隣を赤…とします。これは「固定する頂点1の値を増やした時、値が増えるか、減るか?」を示しています。実際に左端の値を1にしたのが下側の図で、赤の値は1増え、青の値は1減っているのが分かります。

探索途中で閉路が見つかったとします。このとき、隣り合った2点の色が同じかどうかで、判断が異なります。これは、閉路を構成する辺の数が偶数か奇数か、の言い換えです。

違う色(偶閉路)の場合

f:id:betrue12:20180708112417p:plain

2つの頂点が違う色の場合、最初に決めた頂点1の値をいくら増加させても、赤の値が増加し、同じだけ青の値が減少します。つまりこの和は一定です。

その値がたまたま辺に書かれた値と同じであれば、必ず整合性が取れるので探索を続けてよいです。もし異なる値だったときは、どうやってもこの矛盾を解消することはできないので、この時点で0を出力して即終了してよいです。

同じ色(奇閉路)の場合

f:id:betrue12:20180708113014p:plain

同じ色の場合は少し事情が違います。というのも、頂点1の値を変化させることで和を変化させられるからです。頂点1の値を1増加させると、赤・赤ペアの合計は2増加し、青・青ペアの値は2減少します。

もし頂点1の値を変えて、辺の条件を満たすようであれば、その時点で頂点1の値が確定します。(変えなくても条件を満たす場合は、頂点1の値は0で確定します)

ただし、整合性が取れないケースもいくつか存在します。1つは、条件を満たす頂点1の値が整数にならない場合。ずれが奇数の場合はこうなります。次に、奇閉路が2箇所以上見つかって、それぞれが要求する頂点1の値が異なっている場合。これもダメです。0を出力して即終了します。

f:id:betrue12:20180708113948p:plain

仕上げ

これでグラフを全て探索できたら、最後に残った「全頂点の値は正の整数」の条件を考慮して答えを出します。

前準備として、赤い点の数字の最小値  r_{\min} 、青い点の数字の最小値  b_{\min} を計算しておきます。これらは頂点1の値を0としたときのものです。

まずは、奇閉路があって頂点1の値が確定している場合。その値を  a_{1} とすると、赤い点の数字の最小値は  r_{\min} + a_{1} 、青い点の数字の最小値は  b_{\min} - a_{1} となります。これらが両方正の値であれば、全ての頂点の値が正となるのでOK。答えは1通りです。そうでないなら0通りです。

次に、奇閉路がない場合。その場合、 r_{\min} + a_{1} b_{\min} - a_{1} が両方正になる範囲で  a_{1} を自由に選ぶことができます。結局答えが0通りになる場合もあります。

ACコード:Submission #2812884 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-

本番のコードがあまりにぐちゃぐちゃだったので、書き直すついでにコメントマシマシにしてみました。

さいごに

今回の好成績でレートが+105も上がり、青に復帰できました!

f:id:betrue12:20180708120141p:plain

黄色になるにはこのパフォーマンスを出し続ける必要があるわけで…道程は長い。精進します。

脚注

*1:公式解説では「確率」「期待値」という言葉を使っていますが、不確定に変動する要素があるわけではないので、この記事ではなるべく使わずに解説しています。ただ、考え方としてはよくある確率の計算に非常に近いです。