概要を書くのが面倒なので、まとめることにした。
yukicoder 095 Alice and Graph
頂点$i$でのコストが$2^{i-1}-1$なので、より大きいindexの頂点から取るのが最善。 ($2^i>\sum_{k=0}^{i-1} 2^k$)
大きい方から選択した頂点集合に対して、巡回セールスマン問題を解いてこの集合が解に含まれるかを判定していけばよい。
計算量:$O(N^3+K*K^2*2^K)$
https://yukicoder.me/submissions/253071
yukicoder 096 圏外です。
愚直$O(N^2)$が間に合わないので、まず適当に分割をする。ここでは10mの制約を活かして10*10領域に点を入れる。
まず10m以内でつながっているグループに分けないことには、最長距離が求められないため、
隣接8マスをマージの対称にして、UnionFindで集合をまとめる。
まとめ終わったものについてもグループが大きい場合があるので、凸包で頂点数を減らす。
その後はO(V^2)をしてもいいけれど、練習のためキャリパー法を使ってみる。
凸多角形の最遠点対を$O(V)$ぐらいで求められるので、勉強して書く。
分割サイズを$B$,幅を$W$として、
計算量:$O(W^2/B^2+NlogN)$
https://yukicoder.me/submissions/253125
yukicoder 097 最大の値を求めるくえり
乱数列Aがあり、最大値を求めたい。$N$が小さいときは探しても良い。
当然、Nが大きいときは$O(QN)$となり不可能になる。
求める答えをXとしたとき$X = q*A[i]$であり、変形して$A[i] = X*q^{-1}$である。答え$X$が存在するとき、この様な$A[i]$が存在すれば良いので、これを高速に判定すれば良さそう。
qは毎回変わることを考えるとこれは不可能で、最大値の発見から愚直にやるだけで間に合う。(乱数列なので、$\sqrt N$回以内にだいたい発見できる。)
よって$\sqrt N$で解法を分ければ良い。
計算量:$O(Q\sqrt N)$
最悪ケースばかり考えてしまうので、学びのある問題
https://yukicoder.me/submissions/253147
yukicoder 098 円を描こう
点を通る直径について、切り上げなり、切り捨てなりすれば良い。
計算量:$O(1)$
https://yukicoder.me/submissions/253156
yukicoder 099 ジャンピング駒
偶奇の1pairで消滅するため、偶奇の差分は消滅させることはできない。
計算量:$O(N)$
https://yukicoder.me/submissions/253159
yukicoder 100 直列あみだくじ
適当なあみだくじの連続を考えると、循環ができる。
これは奇数長の循環と、偶数長の循環に分かれる。
同じ形のあみだくじを2回使って移動できるのは、まず奇数長のとき。
偶数長は単体ではできず、実験すると(全部試す)同じ長さの循環が2つあると目標の置換を作ることができる。
したがって偶数長の置換が、同じ長さについて全部偶数個あれば存在する。
計算量:$O(N)$
https://yukicoder.me/submissions/253163