今日解いた競プロの問題。

ARC154-D: 自力AC。なかなか気持ちよかった。

まず、1を特定すれば任意の2つの要素を比較できるのでソートできることが分かる。

異なる$P_i$と$P_j$を持ってきたとき、順列であることから$P_i<P_j$と$P_i>P_j$のどちらかが成り立つことが分かる。
$P_i+1>P_j$の判定が可能な場合、これが真ならば$P_i>P_j$であるし、偽なる場合は$P_i+1<P_j$もしくは$P_i+1=P_j$、つまり$P_i<P_j$であり、2要素の比較と一致する。

マージソートなら$N\log_2 N-N$回程度の比較で済むので最大ケース($N=2000$)でも20000回程度の比較で済む。あとは1を5000回程度でどう特定するかになる。

クエリの$i,j,k$は同じインデックスを指定しても良いので、$i=j=a$,$k=b$とすれば$P_a\leq P_b/2$が判定できる。これによって「ある要素の半分以下の値を持つ要素」を見つけることが出来る。要素の値が2以上ならば必ず1つは存在するし、要素の値が1ならば1つも存在しない。なのでこの比較を繰り返せばN回程度で1を特定できる。これでこの問題が解けた。クエリ数制限は25000回だが、実際には22000回程度で恐らく解ける。

なかなかに面白い問題だった。少ない比較回数で順列を特定しろと言われたらソートしかないし、最悪でも$O(N^2)$かけれないのならマージソートか、もしくはヒープソートくらいしか選択肢はないのでその辺に気付くハードルは低そう。それよりも「1さえ特定すれば任意の要素が比較できる」こと、さらに1を特定する具体的な手順を思いつくところがなかなかに厳しい。本番中には一応「1さえ特定すればよい」までは詰められたのだが、1を特定する方法までは無理だった。思いつけば一瞬なんだけどなあ。

---

筋トレをした。今日は背筋。辛いのは辛いが、今一つ上手く負荷をかけられているのか分からない。