naoya_t@hatenablog

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

〈過去問埋め〉技術室奥プログラミングコンテスト #3

技術室奥プログラミングコンテスト #3(出てないやつ)
https://beta.atcoder.jp/contests/tkppc3
の問題を見てみた

A - 時差 (100)

// Python2
東経はプラス、西経はマイナス
abs(差)/15
→AC
https://beta.atcoder.jp/contests/tkppc3/submissions/2865129

B - 鰻と忖度 (200)

// Python2
20万桁だけど
pythonで何も考えずに多倍長演算
とはいえ66で割った余りを求めておいて%6,%11
→AC
https://beta.atcoder.jp/contests/tkppc3/submissions/2865142

C - 新入生歓迎数列 (300)

// 以降C++14
logを取って累積和
ある場所から始めて累積和がlog(P)辺りになる所をlower_boundで探して
誤差に注意しつつ
O(NlogN)
→AC
https://beta.atcoder.jp/contests/tkppc3/submissions/2865188

D - 巨大チェスボード (400)

a,bにそれぞれ+-を交互に掛けた (+a0,-a1,+a2,...) (+b0,-b1,+b2,...) の累積和を用意しておいて、[px..qx)[py..qy) の範囲の和を得て掛けるだけ。O(H+W)
→AC
https://beta.atcoder.jp/contests/tkppc3/submissions/2865267

E - デフレゲーム (500)

期待値の線形性だ
個別に何が出てくるかはμ=(n+1)/2として
k+1回目で既出が出て停止する可能性はk/n、停止しない可能性は(n-k)/n
停止しない場合はμ(n-k)/n が期待値に追加される
停止しなくて次に既出が出て… みたいなのを足し込んでいくと、式
μ(1+(n-1)/n*(1+(n-2)/n*....+(1+1/n))))
が得られるのでこれを(右から)計算。
→AC
https://beta.atcoder.jp/contests/tkppc3/submissions/2865351

F - 天使とふすま (700)

ある2つのふすま(A1,B1)(A2,B2) の位置を決めることを考えると
A1・B2 と A2・B1 の比較になる
これは A1/B1 と A2/B2 の比較と等価なので
a/b を実数ないし分数で持っておいて小さい順にソート
置き順が決まったら実際の運動量を累積するだけ
→AC
https://beta.atcoder.jp/contests/tkppc3/submissions/2865864

とりあえずここまで

G - パソコンの買い替え (700)

H - 新入生歓迎数列 - Hard (1000)

I - 王国と M 種類の店 (1100)

J - 円の重なり ()

〜〜

雑感

筑駒の子たちの有志コンテストらしい。
tkppc=筑-駒-パ-プロ-コン、かな。ちくパ(ckp)っぽい。