Lyft Level 5 Challenge 2018 - Final Round
-
masashinakata
- 650
- 1
- 0
- 0
-
- いいね！0
こうきやまぐち
@Ymgch_K
C (A): 縦棒をどこまで取り除くかを決めて横棒の二分探索 D (B): 任意の相手の頂点uでB uをしてそれを根として自分の部分木内の頂点が初めて現れるところのみで試す E (C): n >= 4のときは自明、n == 3のときはなんかうまく選ぶ（？）
2018-11-05 05:45:24
nmnmnmnmnmnmnm
@enuemuenuemuenu
div2Dは解法はすぐ浮かんだけどAとBのノードを1箇所入れ替えてるバグに気づくのが遅すぎた。（サンプルだとたまたまノード番号が一致する。）
2018-11-05 05:48:01
kimiyuki@うさぎ🐇
@kimiyuki_u
@Ymgch_K 1点固定すると残りの2点はx,yが最大,最小なとこから選ぶとしてよい(はず)なのでO(n)でやりました
2018-11-05 05:49:13
satanic@研究💪
@satanic0258
こどふぉdiv1 A:x1[j]==1なるjにおけるx2[j]だけ見れば良い.この{x2[j]}をソートしておいて,x[i]未満に位置する縦棒を消すときlower_bound(x[i])の位置を元に消す本数を求め各iについてminを取る (→)
2018-11-05 05:51:18
satanic@研究💪
@satanic0258
(→) B:質問は2回だけ.第1回は相手の部分木に含まれる適当な頂点sについて"A s"とする.もし返答tが自身の部分木に含まれていたらtが答え.そうでなければtからBFSして部分木に含まれる最も近い頂点uについて"B u"とする.返答vが相手の部分木に含まれていたらuが答え.そうでなければ-1 (→)
2018-11-05 05:51:29
satanic@研究💪
@satanic0258
(→) C:周長は凸多角形をちょうど含む軸に平行な長方形の周長に一致する.k>=4では2(max{x}-min{x}+max{y}-min{y})が答え.k==3では三角形だが,必ずある角が長方形の角と一致するため,(x,y)でソートしておき[1,i)と(i,n]でyのmax/minをO(N)で求めておく.後は各点を[左/右][上/下]の角と固定してmaxを取る
2018-11-05 05:52:51
satanic@研究💪
@satanic0258
div1C，最初C(N,k)通りの頂点の選び方で和を求める問題を解いていた…(途中で「余り求める記述ないけど答えやたら大きくならないか？」と思い誤読に気づく)
2018-11-05 05:54:46
satanic@研究💪
@satanic0258
C読む(誤読する) →D読む(実装が険しそう) →C考察(まだ誤読中) →C誤読に気づく(C読み始めてから1時間浪費) →CAC みたいなムーブをした
2018-11-05 06:00:25
こうきやまぐち
@Ymgch_K
今回見掛け倒しの問題が多かった印象（長文インタラクティブじゃんと思ったら3回クエリ投げるだけだったし幾何じゃんと思って飛ばしたらほとんど幾何要素なかった）
2018-11-05 06:05:48
satanic@研究💪
@satanic0258
div1Cで三角形のある角が必ず長方形の角に一致することの確認にはGeoGebraを使ってた pic.twitter.com/R2QkKnABd6
2018-11-05 06:10:38
satanic@研究💪
@satanic0258
少し考えると6個の値(x1,y1),(x2,y2),(x3,y3)から4個の値を取るとき鳩ノ巣原理的に必ずあるペアのx,y両方の値が取られてしまうことが分かる
2018-11-05 06:18:43
agw
@masashinakata
Lyft Level 5 Challenge 2018 - Final Round - Togetter: togetter.com/li/1285010
2018-11-05 06:21:02