Codeforces - Lyft Level 5 Challenge 2018 - Final Round (Open Div. 2)
バーチャルコンテストをやって自分が解けたところまで解説します。
後で自分で書いて思ったのですが問題概要読むよりは問題をGoogle翻訳したほうが良いかも
A. The King's Race
http://codeforces.com/contest/1075/problem/A
問題概要
白と黒の2人の王がいる。
最初の王の座標は白が(1,1)で黒が(n,n)。
メダルが(x,y)にある。
それぞれの王は8近傍のいずれかに移動可能。
白の王から最適に行動した時、先にメダルを取るのは誰か？
解説
白の王がメダルにたどり着くターン数はW = max(x-1,y-1)である。 また、黒の王が目ダリにたどり着くターン数はB = max(n - x, n - y)である。 W <= Bのとき 白の王が勝ち、そうでないときは黒の王が勝つ
ソースコード
http://codeforces.com/contest/1075/submission/45375546
B. Taxi drivers and Lyft
http://codeforces.com/contest/1075/problem/B
問題概要
数直線上にタクシードライバーと住民がいる。 住民がタクシードライバーを呼ぶ時一番近いタクシードライバーが選ばれる(ただし、同じ距離のものがあるときはindexが小さい方が選ばれる) タクシードライバーそれぞれの住民に選ばれる人数を出力せよ
解説
それぞれの住民の左にいる一番近いタクシードライバーと右にいる一番近いタクシードライバーを比較すると実装が楽。 {右, 左}にいる一番近いタクシードライバーのindexは累積{max,min}を使えばいい。
ソースコード
http://codeforces.com/contest/1075/submission/45376803
C. The Tower is Going Home
http://codeforces.com/contest/1075/problem/C
問題概要
(この問題ではxの値が大きいほど上、yの値が大きければ右にいます) (10 ^ 9) * (10 ^ 9)サイズのチェスボード上にルークが(1,1)においてある。 また、以下のような線が何本か引かれている。
- y軸に平行でx[i]とx[i] + 1に引いてある直線(これがn本)
- x軸に平行でy[i]とy[i] + 1の間に始点がx1[i]で終点がx2[i]の線分(これがm本)
ルークは線の上を渡ることができない。 任意の回数ルークを移動させて(1,1)からy = 109を満たすいずれかの場所に到達可能になるためには最小で何本の線を取り除けばいいか
解説
x軸に並行な線は始点のx座標が1でなくてはいけない(そうじゃなければルークの進行に影響はない) y軸に並行な線を左からi(0 <= i <= n)個取り除いた場合、x軸に並行な取り除くべき線は何個あるかをカウントすればいい。 取り除くべきx軸に平行な線はx軸に並行な線分のうち始点のx座標が1であり、終点がx[i]のものである。 二分探索(lower_bound)を使えばこれはO(log m)で求められる。 これをy軸に平行な線を左から一つづつ消した場合のそれぞれの値を求めることになるで計算量はO(n log m)となる。
ソースコード
http://codeforces.com/contest/1075/submission/45377479
D. Intersecting Subtrees
http://codeforces.com/contest/1075/problem/D
問題概要
インタラクティブ問題。 あなたとLi君に木が与えられる。 与えられる木の形は同じだが頂点のラベルは異なる。 あなたの木とLi君の木の部分木に色が塗られている。 あなたは以下の5回以内の質問であなたとLi君の木の同じ位置(ラベルが同じとは限らない)で色が塗られている場所を答える(存在しない場合もある)。 質問 - 質問A あなたの木の頂点xと同じ位置のLi君の木の頂点の番号を答える - 質問B Li君の木の頂点xと同じ位置のあなたの木の頂点の番号を答える
解法
最初質問Bを行う。この時指定する頂点はLi君が持っている木の色が塗られている頂点を選ぶ。この時返ってきた答えをsとする。 あなたの木でsから任意の頂点の距離を求める。 次に色が塗られていて一番sから近い頂点をtとする。 木の特性上これは一つに定まる。 次に質問Bを行う。この時指定する頂点はtとする。 この時返ってきた答えをuとする。 uがLiくんの色が塗られている頂点ならそれが答えとなる。 そうでなければそのような頂点は存在しない。
