ケアレスな実装ミスでタイムロスしちまうのはなおらないねえ。
「$d$ 桁の Neq Number は何個あるか?」は、簡単に求められる。
なので、まず「$d$ 桁以下のNeq Numberの個数」を事前計算しておくと、$K$ 番目のNeqNumberが何桁かは判明する。
同様に、大きい方から何個かの先頭桁を決めたときに「これに当てはまる Neq Number は何個あるか?」も求められる。
各桁、前の桁の数と違う数の選択肢があるので、$9^{未定桁数}$ ある。
1 2 3 4 ? ? ? ? それぞれの"?"に適当な数を置いてできるNeqNumberは、9^4=6561個ある
$i$ 桁目に置く数を順に試す。答えが 123?????
を満たす中で 20000 番目である場合、
i 1 2 3 0 ? ? ? ? 1~ 6561 1 2 3 1 ? ? ? ? 6562~13122 1 2 3 2 ? ? ? ? 13123~19683 1 2 3 3 ? ? ? ? ←×違反 1 2 3 4 ? ? ? ? 19684~26244 → 答えは、1234???? を満たす中で 20000 - 19683 = 317番目
なので、大きい方の桁から $0,1,2,...,9$ のうち前の桁と異なるものを置いていき、個数を数えていくと、順に決めていける。
1つにつき、進数を $B=10$、$K_{max}$ 番目のNeqNumberの桁数を $D$ として($D=14~15$ くらい)、$O(BD)$ で求められる。
基本的には、$\left \lfloor \dfrac{N}{3} \right \rfloor$ 個作れるはず。
しかし同一直線上にある3点は、三角形が作れないので選ぶことができない。(作れないのはこの条件のみ)
点同士を結ぶ直線のうち、最も多くの点が並んでいる直線を $L$、そこに乗っている点の数を $C$ とする。
$L$ 上の点をなるべく多く消費することを考えると、$L$ 上から2点と、それ以外から1点を選ぶことで三角形が作れる。
よって、そうやって作っていっても $L$ 上に点が残る場合、作れる個数は $N-C$ 個となる。
答えは、$\min(\left \lfloor \dfrac{N}{3} \right \rfloor,N-C)$ となる。
「同一直線上に並ぶ点の個数」を求めるには、2点組ごとに「2点を結ぶ直線の方程式 $ax+by+c=0$ の係数 $a,b,c$」を計算し、それごとにカウントする。
$c$ 個の点が並ぶ直線は、$\dfrac{c(c-1)}{2}$ 回カウントされることになるので、
最も多くカウントされた直線の値を逆算すると個数が分かる。
$(x_1,y_1)$ と $(x_2,y_2)$ を通る直線の方程式を、「小数による誤差を排除して」「$x$ 軸や $y$ 軸に平行な場合にも対応して」求めるには、以下の式を使うのがよい。
ただし、係数に定数倍をかけたものは同一になるので、それらを統一する必要がある。
こうすると、定数倍の違いを吸収して、3つの整数値で直線を特定できる。
最小の区間は3である。特に、$i$ の左右が、$A_i$ より小さい同士/大きい同士で一致していれば、確実に3となる。
i 両隣が Ai より大きい同士なら、 A 8 5 6 [i-1, i+1] の区間にすれば確実に最小の3になる
それより長くなる場合というのは?
$A_i$ 自身より大きい数と小さい数が左右に交互に現れ、 1つずらしても「小さい数が出て小さい数が入る」「大きい数が出て大きい数が入る」ようにしかならない場合に、長くなる。
i j A 7 14 6 8 10 2 9 5 4 ... ^:8より大きい v ^ v ^ v ^ v v v:8より小さい ~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~ i を含む長さ5の区間は、 ~~~~~~~~~~~~~~ 全て8が中央値になる
上例 5 4
のように大きい数同士、小さい数同士が隣り合った箇所($j$)を含めた区間にすると、中央値を変えられる。
(※端の場合を除く。後述)
このように、$A_i$ より大きい同士/小さい同士が隣り合う箇所を単に「連続箇所」とする。
各 $i$ につき、左右で最も近い連続箇所のindexを高速に求めたい。
区間に連続箇所を含められればよいので、もう一方の端は、$i$ をギリギリ含めるか、もしくは1つだけ逆側を含めるかになる。
左右で近い方の連続箇所との距離を、奇数に調整したものが、答えとなる。
i v連続箇所 A 7 14 6 8 10 2 9 5 4 ... v ^ v ^ v ^ v v ~~~~~~~~~~~~~~~~~~~~ 連続箇所から i を挟んで逆側(6)を、1つだけ含めて調整した場合
端の場合、「逆側を1つだけ含める」ができない。
左端なら、区間を2個ずつ右に伸ばすしかない。
i A 8 10 2 9 5 4 12 ... ^ v ^ v v ^
その場合、小さい同士が連続(5 4
)していても、次が大きい(12
)なら、やはり中央値は8である。
左端・右端は、愚直に2個ずつ伸ばして確かめていくのがよい。
※端で無い場合は、「$A_i$ の左右の大小は異なる」前提から、この心配は無い。
例えば $i$ を左端、右側の連続箇所を右端とした区間が
複数の求め方がある。
$A_i$ の小さい方から順に答えを求めていく。
現在、答えを求めている $A_i$ を $k$ とする。
$B=(B_1,...,B_{N-1})$ を、「$A_i$ と $A_{i+1}$ が、ともに $k$ より小さい、またはともに $k$ より大きい場合に1、それ以外は0」を取る値とする。
A 7 14 6 8 10 2 9 5 4 12 11 3 13 1 B 1 1 1 1 1 1 1 1 1 1 1 1 1 k=1 のとき B 0 0 0 1 0 0 0 1 0 1 0 0 0 k=8 のとき
$B$ を区間Maxセグメント木に載せて、その上で二分探索することによって、 「$[l,r)$ の範囲のうち最も左にある1」「最も右にある1」の位置を取得できる。
これで、左右に最も近い連続箇所の位置が求められる。
$k=A_4=8$ の答えを求め終わったら、次の $k$ に向けて、$A_3,A_4,A_5$ の大小を調べて $B_3,B_4$ を更新する。
$i$ から左/右に1つずつ、連続箇所が出てくるまで調べる実装でも、間に合う。
ある $i$ で時間がかかる場合というのは、左右に $A_i$ より大/小が交互に出現する場合である。
このとき、通過した各要素は、その要素にとっては「両端が大きい同士/小さい同士」に該当するので、答えは3とすぐに求まる。
i x をつけた要素は、 A 7 14 6 8 10 2 9 5 4 ... 両端が大きい同士/小さい同士なので答えは3 v ^ v ^ v ^ v v ←←←←←|→→→→→→→→ ←iからの探索範囲 x x x x x
また、愚直に調べる対象となる $i$ は、小→中(i)→大 と並んでいるので、 他の要素から見れば、$i$(の周辺 $\pm1$)で大/小が連続し、そこで探索が終了することになる。
よって、$A$ の各要素が愚直に調べられる回数は、左方向・右方向に1回ずつとなり、$O(N)$ で間に合う。
小 中 大 大 中 小 A 7 14 6 8 10 2 9 5 4 ... v ^ v ^ v ^ v v |→→→→→→→→ ←←←←←←|
以下、単に「ウォーク」というと、始点と終点が同じ「閉じたウォーク」を指すとする。
まず、正しい括弧列というと以下の条件をともに満たすものだが、
このうち、後者は無視できる。
もし途中で ')' の個数が上回ってしまっても、開始位置を適切にずらすことで、必ず正しい括弧列にできる。
よって、「'(' と ')' が同数」で全辺を通るウォークを見つけさえすればよい。
同数とは、「'(' を $+1$、')' を $-1$ で置き換えて、ウォークのコストが0」と言い換えられる。
条件を満たすウォークがあったとして、存在を見つける上では頂点 $1$ を始点終点に固定して考えて問題ない。
$1$ を始点と終点とするウォークを $Walk_1$ とする。
$Walk_1$ を複数個並べたものもまた、$Walk_1$ である。
答えとなる「全辺を通りコストが0の $Walk_1$」を、
$Walk_1$ の結合で作ることを考える。
ウォークのコストは、当然ながら 正、0、負 のいずれかである。
グラフ中にコスト正の閉路があることと、コスト正の $Walk_1$ があることは、一致する。
コスト正・負のウォークがそれぞれあるとどうなるか考える。
条件を満たすウォークを実現できる。
意図的に作らない限り珍しいが、これもあり得る。
この場合も、当然コスト0を実現できる。
なんとなく「No」っぽいが、証明しようとすると悩ましい。公式Editorialでは背理法による証明がある。
正の閉路があり負の閉路が無いグラフでも、条件を満たすウォークがあったと仮定する。
あるウォーク $W$ と、そこに含まれる辺のみを使用した閉路 $C$ があるとする。
この時、以下のようにすることを、“$W$ から $C$ を取り除く”と表現するとする。
条件を満たすウォークを $W$ とし、そこから正の閉路 $C$ を取り除くと、残ったグラフの総コストは負になる。
つまり、どれかのウォークはコストが負にならざるを得ず、負の閉路が存在することになる。
矛盾するので、コスト正の閉路しか無ければ、正解ウォークは作れないことが分かる。
負閉路検出はBellman-Fordで、$O(NM)$ でおこなえる。
正閉路も、コストを逆転させれば同様に求められる。