CODE FESTIVAL 2018 Final J

2018-11-19 | [Competitive programming]

コンテスト中は見向きもしなかったけどあとで考えたら普通に知識で解けることに気づいた…

概要

コンテストのページ をみてください

コード

AtCoder 上の提出 をみてください

解法

• この下に解法があります
• ネタバレ注意
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a
• a

まず「T に含まれる整数は必ず S0 にも 1 回以上含まれる」が必要条件なのは明らかである． 逆にこれが十分条件でもあることを，構成により示す．

以下 N = 2^d とおく． T が S0 の permutation の場合が解ければ，上の必要条件を満たす一般の T に対して解くことができる． 実際，T をソートした数列を T’ とおくと，T’ -> T に数列を変換するのは permutation の場合を用いれば可能である． さらに，T’ において各値のうち最も左の現れのみを残し，それ以外は S0 から未使用の値を適当に持ってきて埋めた数列を T’’ とおくと，S0 -> T’’ も同様に可能である． T’’ -> T’ は，ダブリングの要領で d 回でできる．

よって permutation の場合を解けばよい．一般性を失わずに，T は S0 をソートしたものと仮定してよい． ところで，次の変換は 2 回操作を行うと可能である：

• k 個のペア (x[0], y[0]), …, (x[k-1], y[k-1]) は，それらに含まれる 2k 個の要素いずれも異なり，y[i] - x[i] がいずれの i に対しても等しいものとする．
• このとき，各 i に対して，S[x[i]] > S[y[i]] ならこの 2 つを入れ替え，S[x[i]] < S[y[i]] なら何もしない．

Batcher’s odd–even mergesort というソーティングネットワークの各段は，上の変換に相当する．Batcher’s odd–even mergesort の段数は，N = 2^d として d(d+1)/2 回であるから，1 回の permutation を d(d+1) 回で実現できる．

一般の場合は，permutation 2 回（それぞれ操作 d(d+1) 回）とダブリング（操作 d 回）が必要であるから，全部で 2d^2 + 3d 回の操作で目的が達成可能である． この問題の制約では d <= 13 であるから，最大で 377 回で解くことができ，十分小さい．