/ 最近 .rdf 追記 編集 設定 本棚

脳log[20211022] AtCoder Regular Contest 120/C 問題 Swaps 2



2021年10月22日 (金)

最終更新: 2021-11-23T22:07+0900

[AtCoder] AtCoder Regular Contest 120C 問題 Swaps 2

精進ですよ。水 diff だけど難しい(まるで水 diff が簡単かのような……)。考えがまとまるまで1日かかった。

 問題の操作

隣接2要素をスワップして +1/-1 するというけど、考えやすいように複数の操作をまとめるとこう。

  1. ある要素 Ai を右に(左に)いくつか移動する。
  2. たとえば右に5移動するなら、移動先の値は Ai-5 になる。
  3. たとえば右に5移動するなら、飛び越された5つの要素が、移動先に空きを作るためと移動元の空きを埋めるために、1つずつ左に移動している。
  4. 左に1移動した5つの要素は値を +1 する。

 ポテンシャル

Ai の値は移動に伴って変化しているように見えるけど、実のところ位置に応じて決まった値をとっているに過ぎない。どういう値をとるかは、最初に位置 i で値 Ai をとっていた、ということで決まる。

A 数列の各要素が位置1でとる値をその要素のポテンシャルと呼ぶことにする。ポテンシャルから要素の位置を逆引きできるようにインデックスを作成しておく。

 B 数列

B 数列をスキャンしながら、要求するポテンシャルを計算し、該当する要素を A 数列の先頭に近いところから貪欲に引っぱってくる。

引っぱってくるに際していくつの要素と位置を交換することになるかは BIT で転倒数を管理することで数える。というか、知る必要があって管理している数字が転倒数と呼ばれている、が順序として正しい。

 提出 #26732769 (AC / 561 Byte / 491 ms)

難しい。これが水 diff ってどうかしてる。ちなみに Swaps の1はこれ>「Swaps」。黄 diff です。解けるまで9か月寝かせました(20191111p0120200826p01)。2は1日寝かせただけで解けたんだから、妥当なのか?