SoundHound Inc. Programming Contest 2018 -Masters Tournament-

コンテスト開始2分前ぐらいまでアイスを食べていて、乗り遅れそうになりました。

A - F

提出コード
if文を使って、aとbの足し算、掛け算が15になるかどうかを調べます。どちらでもなければその時用の出力をして終わりです。

提出コード
入力用と出力用の二つのstring型の変数を用意します。入力用の変数sを頭から順番に、添え字を動かしつつ見ていったときに、0もしくはwの倍数（すなわち添え字をwで割ったときのあまりが0)だったらそれは行の先頭の文字なので、出力用の変数ansに1文字ずつ格納していきます。sを見終わったときには、ansが答えになっています。
ここらへんでいつもBGMをイヤホンから流しているのに今日は流していなかったことに気づき、慌てて準備しました…

C - Ordinary Beauty

提出コード
問題をみて、あー全探索だとこれ間に合わなさそうだなぁと思いました(それはそう)。
まず、2つの数字の差がdになるのは何通りあるか？を調べると、(n-d)通りであることがわかります。そして、2種類の数字であるので並べ方はさらに2倍して(n-d)×2です。
次に、長さmの数列のうち、隣接する2項の差がdになるように配置する場所を1つだけ固定します。すると、長さmの数列は残りm-2個の数字を確定させなければならないので、その決め方が $n^{(m-2)}$ 通りとなります。よって、ある1箇所だけ差がdとなるように固定したときの並べ方は全体で(n-d)×2× $n^{(m-2)}$ 通りとなります。
また、隣接する2箇所の選び方は(m-1)通りあり、全てのパターンについて上と同じ考え方ができるため、結局は(n-d)×2× $n^{(m-2)}$ ×(m-1)通りとなります。
最後に、平均値を求めたいので、全体のパターン数である $n^{m}$ で割ります。すると、答えとして

$\frac{\color{red}2(n-d)(m-1)}{n^{2}}$
という数式が完成します。
…とここでサンプルを通して通らないことが判明。答えのぴったり2倍が出力されていたので何かコーナーケースがあるのだろうと考えました。
結論から言うと、d=0であるとき、選ぶ2つの数字は等しい数字であるので、並べ方が1通りしかありません。よって、先ほどの赤い2の部分を1もしくは2というように置き換えて今度こそ完成です。
と言いたかったのですが、出力の方法の問題で悩み、Dの実装をしつつ考察終了から30分後ぐらいでようやくACしました。
最近pythonを触り始めたので、そちらで提出することも考えたのですが、スペース区切りの入力をやったことがないので断念しました。コンテスト終了後に調べて書いてみました。それがこちらになります。
pythonでの提出コード

D - Saving Snuuk

提出コード
ACの瞬間思わず叫びました。それぐらい4完が久々でした…
とりあえずlong longで書こうかなーと思いつつ問題を読んでくと、なんとなくダイクストラ法かなぁということに気づきました(ダイクストラ法自体を初めて学んだのが最近なので記憶に新しいため、気づくことができました)。しかし、自分が書いたことのあるダイクストラ法が、O(N²)のC言語でのコードのみだったので、これだと通らないだろうなぁと思いました(それはそう)。何かもっといいコードがあったなぁと思いながら蟻本を眺めてると、ビンゴでした！優先度キューを使うことがそもそも初めて(中身は知っていました)だったので、ほぼそのまんま写経になってしまいました…
基本的な考え方は次のようになります。
i番目で両替をすると仮定したときの最適解が、円を使ったときのsからiへの最適解とスヌークを使ったときのiからtへの最適解の和となります。そのため、とりあえずsから任意の都市へ円を使って行った場合の最適解と、tから任意の都市へスヌークを使って行った場合の最適解の2種類を、ダイクストラ法を用いてもとめます。
求め終わったら、i番目以降で両替をした場合の最適解を求めます。考察中に2重ループだと通らないよなぁと思っていたくせに、愚直に2重ループで提出してしまって1WAいただきました。きちんと考え直して、後ろから見ていってDPっぽく更新していけばいいということに気づき、書き直して無事ACしました。

E - + Graph

提出はまだしてません。
初めてのE問題でした。残り30分だったので、とりあえず何か書いてみるかなぁと思い、再帰で愚直に書いてみました。残り1分で完成したコードは、サンプルの1つめすら通りませんでした…悲しい。

2018/7/11追記

昨日やっと解けました…問題文の誤読をしていてすごい時間をつかいました(話を聞いてくださった方々、ありがとうございました)
提出コード
解説にもほぼ同じものがのっていますが(解説を見たので当然ですが)、基本的な考え方はこうです。
頂点1の数字を $t$ とすると、別の頂点は全て何かしらの辺を通るので、その頂点の数字は一意にきまります。すなわち、頂点1における数字のパターンがそのまま答えとなります。
次に、頂点1から1個だけ辺を通りたどり着く頂点iの数字について考えます。頂点1と $i$ をつなぐ辺の重みを $a$ とすると、頂点1とiの数字の和が $a$ にならないといけないので、頂点1の数字が $t$ のとき、自動的に頂点iの数字は $a-t$ になります。
同様にして、頂点 $i$ から1個だけ辺を通りたどりつく頂点 $j$ について考えると、頂点 $i$ と $j$ の辺の重みを $b$ とするとき、頂点 $j$ の数字は $b-(a-t)$ より、 $(b-a)+t$ となります。
ここで、それぞれの頂点の数字は0より大きいので、
$a-t>0⇔a>t$
$(b-a)+t>0⇔t>a-b$
という条件式が成り立ちます。この条件式をすべての頂点について求め、全ての条件式を満たす $t$ の個数が答えとなります。
さらに、グラフが環状になっていてループをするパターンについては注意が必要です。
グラフが環状のとき、1つの頂点で2つ以上の条件式が成り立つ場合があります。条件式は $a>t$ および $t>b$ の二種類がありますが(さきほどの式の $a-b$ を、新しく $b$ と置きなおしています)、1つの頂点にある2つの条件式が、2つとも同じ種類だったパターンと、異なるパターンで、さらに場合分けが必要になります。

① 同じ場合

2つが同じだった場合、その頂点の数字は、例えば
$a-t$
$b-t$
の二つを同時に満たす数になります。この時、頂点の数字は1種類にしかならないので、
$a-t=b-t$ より、
$a = b$
を満たす必要があり、 $a \neq b$ だった場合、条件をみたすtは存在しないことになります。すなわち答えは0です。

➁ 異なる場合

同様に考えると、例えば
$a-t$
$b+t$
の二つが等しくなければなりません。したがって、
$a-t=b+t$ より、
$\frac{(a+b)}{2}$
という数しか条件を満たさないことがわかります。なので、

$a+b$ が負
$a+b$ が奇数

のとき、答えは0になります。加えて、ほかの頂点についても同様に条件が重複した場合、すべての $t$ の値が等しく、また最初に求めた条件の範囲に $t$ が含まれていないといけません。これらを満たさない場合も、同様に答えが0になります。
以上の複雑な条件をすべて満たした時、答えは1となります。

以上をまとめると以下のようになります。
頂点１をスタートとし、初期値0の変数を1つおき(このブログ内ではvとします)、そこから
・奇数回辺を通ってたどり着ける場合、その辺の重さをvに足す
・偶数回辺を通ってたどり着ける場合、その辺の重さをvから引く
を繰り返してメモをし、最終的に奇数回パターンのvの集合の最小値と、偶数回パターンのvの最大値の間の数の個数が答えとなります。例外的な条件が、
・ループしてある頂点に来たのが2回目のときに、
① 辺を通った回数の偶奇が1回目と2回目で同じ場合、違う数なら答えの個数は0になります。
➁ 辺を通った回数の偶奇が1回目と2回目で違う場合、頂点1の値は、２つの条件の和を２で割ったものになる（すべての頂点において、この値は等しくなります）。なので、和が負になったり、奇数になったり、ほかの頂点の値と異なる場合、答えは0になります。また、頂点1の値は、やはりすべての頂点における条件をみたします。これらが成り立つときに、答えの個数は1になります。
というものを、頂点1から、通れる全ての辺について再帰をしていけば答えが求まります。

ということで、久しぶりの4完でした！パフォーマンスも過去最高で、1600で頭打ちにならない嬉しさも知りました。ABC以外のratedコンテストに出場するのはこれが2回目だったので、ほぼベストが出せてすごい満足です。いよいよ水色も見えてきた(気がする)ので、続けて頑張ろうと思います。

ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。