naoya_t@hatenablog

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

TCO18 Algorithm Round 3B

Round 3Aはれじったけど寝倒したし今度こそ
iwashi31たんとかcafelierたんとか同室

Easy : SquareCutout (500)

"#"が出てくる行数 x 出てくる列数、が"#"の個数に等しければ…みたいなコードを投げた。
甘かった(甘すぎた)
・"#.#","...","#.#' みたいな隙間のあるやつで死ぬ
・".#.",".#." みたいにくっきり長方形なやつで死ぬ

Medium : TestProctoring (500)

  • proctorって何?→試験監督
  • 1人の場合、終わる率がpだったら終わるまでの回数の期待値は1/p
  • 2人の場合…1人ずつ独立に計算したらいい?いや違う
    • 2人(a,b)いた場合、a終b終 / aまだb終 / a終bまだ / aまだbまだ、という状況がある。
    • aの終わる率をp, bの終わる率をqとすると、2人が終わるまでの回数の期待値 f(11) = f(a終わる=1,b終わる=1) は
  • f(00) : a終b終: pq×(1+0) = pq
  • f(10) : aまだb終:(1-p)q×(1+f(1):bが1人続いた場合の期待値) = (1-p)q×(1+1/q) = (1-p)(1+q)
  • f(01) : a終bまだ:p(1-q)×(1+f(1):aが1人続いた場合の期待値) = p(1-q)×(1+1/p) = (1+p)(1-q)
  • f(11) : aまだbまだ:(1-p)(1-q)×(1+x)

の和で、x = pq + (1-p)(1+q) + (1+p)(1-q) + (1-p)(1-q)(1+x) = (3-p-q) + (1-p)(1-q)x
x = (3-p-q)/(1-(1-p)(1-q))
p=q=1/2のとき 2/0.75 = 8/3
これをbitDP的にうまいこと計算したら行けるんだろうか?

とりあえず計算が合う実装は出来たんだけど、N=20のとき終わらないし
(Nが1増えると3倍前後の時間がかかってる。O(3^N)の項がある駄目なやつだ)
誰かに撃墜ポイントを取られるだけで意味ないんだけど、残り1分で記念投稿。

Challenge Phase

f:id:n4_t:20180721183800p:plain
これはひどい

System Test

f:id:n4_t:20180721183556p:plain
さらにひどい

Result

f:id:n4_t:20180721183633p:plain
cc- 0pt 162pl 1611→1523 (-88)
かろうじて黄色にとどまった

after

まさにこういう時こそがO(3^N)をO(N2^N)に減らす高速ゼータ変換の出番、なのね
(と思って書き直してみたけど数が合わない…あとで再考)

参考


あと同室だったcafelierさんのやつも解読したい
https://community.topcoder.com/stat?c=problem_solution&rm=331505&rd=17205&pm=14766&cr=22758647

Must read: