競プロで出てもおかしくない！数オリの構築系問題　その1

そのいくつまで続くかはわかりませんが、いい感じの問題を見つけたら暇を見つけて書いていこうと思います！

趣旨

  • 各国の数オリで出た問題で競技プログラミングの問題にもなりそうな問題を集めて紹介
  • 原案はそのまま、場合によっては原文が証明問題のものも使用していい感じの問題文に改変して紹介 といった感じで行こうと思います。

例としては、「○○に対して□□を満たす△△が必ず存在することを示せ」という問題があったとしたら、「○○が与えられるので、□□を満たすような△△を出力せよ」に変える、って感じです。

今回の問題は韓国のジュニア数学オリンピックからです。
答えが載ってなかったので、多分大丈夫ですけど間違えてたらマジでごめんなさい！

問題概要

長さ N の整数列 \(A _ 1 , \cdots , A _ N \) が与えられる。
(訂正: \(A_i \) は相異なります、ごめんなさい)
並び替え \(B _ 1 , \cdots , B _ N \) であって以下の条件を満たすものを一つ求めよ。

  • \(1 \le i < j < k \le N \) を満たす任意の \( i , j ,k \) に対し、 \( 2 B_j \neq B _ i + B _ k \)

制約

\(N \le 10 ^ 5\)
\(A _ i \le 10 ^ 9\)

現問題url (KJMO 2018 p8)

AGC換算で 600～800 くらいだと思います(個人の感想)

サンプル

N=3
A={4,5,6}

この時の答えは \( 4 , 6 , 5 \) 等です。
\( 4 ,5 , 6\) や \(6,5,4\) は \( 2 B _ 2 = B _ 1 + B _ 3 \) を満たすので不適です。

ヒント1 \( A _ i \) たちを大きく二つに分けると、、、？

ヒント2 \( A _ i \) その分け方とは構築といえば50%くらいで見るやつ、ずばり偶奇です。

ヒント3 偶数は偶数、奇数は奇数で片側ずつにまとめると、、、？

解答 \( A _ i \)が奇数より右に偶数がない状態、つまり左側に偶数、右側に奇数がまとめられているとします。
この時、条件を満たさないような \( i,j,k \) の組は 必ず \(B _ i + B _ k \) が偶数になっていることに注意すると、 \(B _ i \) と \(B _ k \) の偶奇が異なるようなものは見なくていいことがわかります。
すると、例えば
\( 4 , 6 , 2 , 8 , 3 ,5,7,1\) のような数列は
\((4,6,2,8) \) と \((3,5,7,1)\) の部分を別々に並び替えた後につなげても条件は崩れません！

次に偶数部分と奇数部分をまた並び替えることを考えましょう。 \( 2 B _ j = B _ i + B _ j \) を満たすなら、
\( 2 ( \frac{B _ j} {2} ) = (\frac{B _ i}{2} ) + (\frac{B _ k}{2}) \)
を満たすことを考えると、全体を2で割っても条件は変わりません。 後は以上の操作を列の長さが1になるまで繰り返せばよいです。 計算量は適当に両端キューとか使えば O(N \log max A) です。 bit列を逆から見たのをソートすればlogはつくけど一発です。