読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #348 B. Little Artem and Dance

http://codeforces.com/contest/668/problem/B

問題概要

1..n が順に並んだ数列 A が与えられる。この数列に対して以下の 2 種類の操作を行う。

  1. 数列を x だけ回転シフトする。
  2. 隣り合う要素同士を交換する。つまり i:0→n/2-1 に対して swap( A[ 2i ], A[ 2i+1 ] ) を行う。

最終的な数列 A を求めよ。

解法

数列を偶数番目と奇数番目で分離して考えてみる。

回転操作は以下のようになる。

f:id:pekempey:20160425185357p:plain

偶奇の交換は以下のようになる。

f:id:pekempey:20160425185403p:plain

どちらの操作も回転を無視すれば順序を維持している。


自分が考えた方法は「回転量の合計」を偶奇それぞれに対して求めておき、最後にまとめて回転するというもの。

結局 1 と 2 の位置の情報があれば最終的な数列が求まるので、1 と 2 だけシミュレートするという方法もある。

本番中提出したコード
http://codeforces.com/contest/668/submission/17491259

1,2だけシミュレート
http://codeforces.com/contest/668/submission/17501912

Codeforces Round #348 B. Little Artem and Dance 賢い

問題を理解するのにかなり時間を掛けてしまった。