naoya_t@hatenablog

いわゆるチラシノウラであります

SoundHound Inc. Programming Contest 2018 -Masters Tournament-(C,D,E問題解決編)

C,D,E問題解決編

C - Ordinary Beauty (300)

(一夜明けて)頭すっきりしたところで、もう一度最初から考えてみるよ

  • 数列を1つずつ長くしていく過程で、末尾n通り×次項n通り、のn^2通りの隣接ペアが見られるが、そのうち美しいのは 2(n-d) 通り(※d=0のケースは特殊でn通り)、というのは分かる。美しいペア率 r=\frac{2(n-d)}{n^2} である。
  • 長さ2(隣接項1)のとき:確率rで美しさ1、確率1-rで美しさ0
  • 長さ3(隣接項2)のとき:確率r^2で美しさ2、確率2r(1-r)で美しさ1、確率(1-r)^2で美しさ0
    • はい二項分布(とすると期待値はnpだから、この場合(m-1)rが答えになる)
    • でもそれって、m-1 回の独立な試行(=美しいペア率がそこまでの数列の内容に依らない)という仮定が入ってるよな。そこに引っかかって本番終わったわけだ
    • 数列の末尾の数によって美しいペア率は \frac{0}{n},\frac{1}{n},\frac{2}{n} とばらついているはずだ( r=\frac{2(n-d)}{n^2} というのはその合計であって)
  • 美しいペア率が \frac{0}{n} の末尾をグループα、\frac{1}{n} の末尾をグループβ、\frac{2}{n} の末尾をグループγ、として、それぞれa通り,b通り,c通りとする(a+b+c=n
  • a,b,cは nとdの大きさの比率によって変わる
    • (1) n\le 2dのとき: c=0, b=2(n-d), a=n-2(n-d)=2d-n
    • (2) n\gt 2dのとき: c=n-2d, b=2d, a=0
  • 条件付き確率 p(美|前=α)=0, p(美|前=β)=\frac{1}{n}, p(美|前=γ)=\frac{2}{n}
    • p(前=α)=\frac{a}{n}, p(前=β)=\frac{b}{n}, p(前=γ)=\frac{c}{n}

$$ p(美)=Σp(美|前=ι) = p(美|前=α)p(前=α) + p(美|前=β)p(前=β) + p(美|前=γ)p(前=γ) = 0\cdot\frac{a}{n}+\frac{1}{n}\cdot\frac{b}{n}+\frac{2}{n}\cdot\frac{c}{n}=\frac{b+2c}{n^2} $$
(1)(2)にかかわらず b+2c=2(n-d) なので
p(美) = \frac{2(n-d)}{n^2}

  • なるほど(?)
  • でも、p(前=α)の時の期待される美しさ率 q(前=α)、同様にq(前=β),q(前=γ) があったとして、それぞれ違う値じゃないかと思うんだけど、そこからp()を畳み込むなり何なりしてq(前=α),q(前=β),q(前=γ) が出たりするのか?

最終的な答えはその加重平均でいいと思うんだけど…

    • いや、この掘り下げ方は本番で悩んだ方向性と同じだ。この問題の解き方としてはおそらく筋が悪い。

そこで助け舟

項数2のn^m個数列の列Bの中には(1,1),(1,2),…,(1,n), (2,1),…,(2,n),...(n-1),…,(n-n) のn^2個の数列が均等に存在する

結局のところ、そこの均一性を使っていい根拠が腑に落ちていない(均一かもしれないけど、あるペアの後にはn通りのペアしか来られないわけで的な)のね。
(均一性については、n進数でm桁の数字(0-padding有り)と読み替えても同じだけど、任意の連続する2桁を取ってきたとき、その2桁にはn^2通りのペアが均等に存在するということ。)

  • 可能なすべての数列 n^m通り で(=全宇宙のサイズ)
  • 数列の長さはそれぞれm(ペア数はそれぞれm-1)なので
  • (m-1)n^m組のペアが存在し(=全宇宙に存在するペアの数)
  • ペアは全n^2組が均等に用いられていて
  • そのうちの美しい率r=2(n-d)/n^2 で
  • ということはr(m-1)n^m個の美しいペアが存在し(=全宇宙に存在する美しいペアの数)

どこかに存在していればよくて、局所的に並びの偏りがあったとしても宇宙全体では美しいペアの数は変わらない

とすると、美しさの期待値は(全宇宙に存在する美しいペアの数)÷(全宇宙のサイズ)
$$ \frac{r(m-1)n^m}{n^m}= r(m-1) $$

そう思ったら自明じゃないか?

→AC
https://beta.atcoder.jp/contests/soundhound2018-summer-qual/submissions/2814599

教訓

細部から数え上げる必要のまったくない(宇宙全体を見渡すだけでいい)問題ってのもある

あと

期待値の線形性は独立事象でなくても成立する

ということらしい。(https://twitter.com/_TTJR_/status/1015842823927521280)
(そこもうちょい詳しく、と思ったらtsutajさんが資料を上げてくれていた→http://compro.tsutajiro.com/archive/180220_probability_dp.pdf

→ちゃんと腑に落ちるまで掘り下げてみた

D - Saving Snuuk (400)

sから円でダイクストラ、tからスヌークでダイクストラ、で配列を二本 (costY,costS) を作っておいて、(costY[i] + costS[i], expiration=1+i) をpriority_queueに入れて、賞味期限が切れたものは捨てていきながらコスト最安な都市で両替する
→AC
https://beta.atcoder.jp/contests/soundhound2018-summer-qual/submissions/2833980
なんだCさっさと捨ててこれ解けばよかった、ってぐらいすんなり解けた。
解説解も同様

E - Graph (600)

1つ頂点を選んでそこの数をxとしておいて、グラフを辿りながら制約(ax+b)を伝播していって、

  • 辻褄が合わなくなったら0
    • aが同じ正負でかち合ったらbが異なるときは無理なので0
    • aが+1と-1でかち合ったらxが1つに定まるか割り切れなくて定まらないかなので、定まらなかったら0
  • そうやって伝播していくと、xは正の整数でなければならないのでxの上限と下限が定まる(のでその差+1を返す)

→WA
https://beta.atcoder.jp/contests/soundhound2018-summer-qual/submissions/2834587
割り切れてxが1つに定まった時にそのxで行けるのか確認して回るようにした
→WA
https://beta.atcoder.jp/contests/soundhound2018-summer-qual/submissions/2834624

解説解見たら同じ解き方をしているので多分実装にミスがある
(続く)
その後何度かWAを出して
「割り切れてxが1つに定まった時にそのxで行けるのか確認して回るようにした」部分をprintfデバッグしたら確認して回ってなかった(最初にvisited[0]=trueになってて何を入れてもtrueを返してる)
直して
→AC
https://beta.atcoder.jp/contests/soundhound2018-summer-qual/submissions/2836107

教訓

挙動がおかしかったら自分のBFSなりDFSなりが全ての頂点を巡回しているかどうか、枝刈り等で巡回を止めた場合に処理をしているかを確認する