CF27 Div2
もっとまじめにやりましょう、って感じだった。
A
既に使った値を覚えておいて、使っていない最小の値を教えてくれるマシンがある。使った値のリストが与えられるとき、そのマシンに問い合わせた結果を答えよ、という問題。
やるだけ。
B
N人の人が総当たりで対戦をした結果の一つを除いたものが与えられる。全員には内部的に相異なる強さのパラメータが実は与えられていて、常に強い人が勝つことが保証されている。このとき、除かれた結果を答えよ、という問題。
その二人が勝った人の数が多い方がそれだけ強いということになる。同じ数のときは隣接する二人なので決定できない。(この場合はどっちを答えてもいいらしい。)
C
整数配列が与えられるので、広義単調増加ないし減少でない部分配列のうち最小の長さのものをいずれか答えよ、という問題。
最小の長さのものは常に3であることが保証されているので、適当に探せば良い。取り敢えず、全体が広義単調増加ないし減少なら答えはないので、狭義単調増加ないし減少の位置をそれぞれ探す。どちらかが見つからなければ答えはない。両方とも見つかった場合、それにでてくる3ないし4個の値から、求める配列が作れるので、後は適当に加工して答える。
O(N^2)だと通らない。Div2なので油断した...。
D
円周上に都市がN個並んでいる。二都市間に新たに道を作るとき、円弧とも他の道とも交差しないようにしたい。それぞれの道を円弧の内外どちらに作るべきか答えよ、という問題。
要は2SATなので、Greedyに割り当てをしていって、矛盾が発生しなければそれが答え。矛盾が発生する場合はどうやっても無理なのでそう答える。SATの条件としては、二つの道が円弧の同じ側にあったら交差すること。
