Codeforces Round #514 (Div. 2)
-
masashinakata
- 942
- 2
- 0
- 0
-
- いいね！0
satanic@研究💪
@satanic0258
こどふぉ A:Σ{x=各与えられた区間を含まない区間の長さ}x/a B:NxMの空の盤Xを用意し,入力に書いても変わらない所があればそのような所全てについてXの同じ所に書く.最後に入力とX一致判定 C:t=1として,n>=4ならceil(n/2)個tを追加しn/=2,t*=2する.n<=3ならサンプルにtを掛けたものを追加して終了 (→)
2018-10-06 01:38:29
(nは自然数)
@n_vip
D問題 接点の座標xを決めたとき、点Aが円に含まれるためには、Aと接点の垂直二等分線を引いて、接点からたてた垂線との交点Pよりも円の中心が上にないといけない。このPの高さはxについての二次式になっているんだけど、計算が苦手なので確かめながらやった geogebra.org/graphing/gqhms…
2018-10-06 01:38:54
satanic@研究💪
@satanic0258
(→) D:円の中心のx座標pに対して半径はpに関する二次関数になる,max{下に凸な関数たち}は下に凸なので三分探索 E:dp[v] := v部分木で(最小パス数，その時の上に伸ばせる最大長) で木DP
2018-10-06 01:40:07
kuuso
@kuuso1
Dは中心のX座標をきめると最小半径がO(N)で決まるので三分探索した． pretest通らねぇデバッグでイテレーション600回にしたやつを最後投げてしまって怯えてる． （通らなかったのはYが全部負の座標のやつの符号の問題だったので誤差関係なかった）
2018-10-06 01:40:53
アルメリア
@armeria_betrue
A: 計算する B: 塗れるところ全部塗って結果が一致するか見る C: 基本的に2冪の倍数を残すのがよいので、奇数番目を落とすのを繰り返すんだけど、残りが3つのときだけ注意 D: にぶたんする 半径を固定すると各点ごとに中心が存在すべきx座標の範囲が出るので、共通部分があるか判定する
2018-10-06 01:41:26
iwashi31
@iwashi31
B hack しようと思って見てたけど、自分と同じロジックの人がいなくて不安になってた（あるセルが # ならばそれを含む輪が存在するかをチェックするみたいな方法でやった）
2018-10-06 01:41:28
(nは自然数)
@n_vip
こういう考察をすると、Dは、「上に凸な 2次式 f1..fnが与えられるので、max(f1(x), .. , fn(x)) の最小値を答えてください」みたいな問題になるんだけど、厳密に解けそうな形をしているような気がしなくもない
2018-10-06 01:41:37
kmjp
@kmjp_pc
なんかDみんなX座標の探索してるのか。自分は半径を二分探索した（各点に対し、中心が存在可能なX座標の区間を求めて、共通部分の有無を判定した）。半径の最大値を10^9にしてしまいWAを重ねてしまった。
2018-10-06 01:43:14
iwashi31
@iwashi31
D は円の半径と中心の x 座標のそれぞれでにぶたんした。円の半径を固定して適当に円を置いて、含んでない点がある方向に円を寄せていく。左右両方に含んでない点があると NG
2018-10-06 01:43:23
hogeover30
@hogeover30
A: Σ(t[i+1]-(t[i]+l[i]))/a B: 塗れるところは全部塗る C: f(1)={1}, f(2)={1, 2}, f(3)={1, 2, 3}, f(n)={1が(n+1)/2個} + 2*f(n/2)
2018-10-06 01:44:09
satanic@研究💪
@satanic0258
円の中心を(p,q)とすると半径もqで (x[i]-p)^2+(y[i]-q)^2=q^2 ↓ q={(x[i]-p)^2+y[i]^2}/{2*y[i]} とか求まるのでmax{q}がpでの最小半径
2018-10-06 01:45:07