競プロチャレンジ供養会場: NOMURA プログラミングコンテスト 2021 (AtCoder Regular Contest 121) C - Odd Even Sort

コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

Difficulty: 1856 (記事作成時点)

供養

解法

• それまでの手順の列を $S$ とする
• $t = 1, \dots, N - 1$ の順に位置を決めていく
  • $t$ の現在の位置を $n$ とする
    • $n \ge t$ としてよい
  • $n = t$ となるまで以下の操作を繰り返す
    • $|S| \% 2 = n \% 2$ のとき、$S$ に $n - 1$ を追加し、$p_{n - 1}, p_{n}$ を入れ替え、$n = n - 1$ とする
      • $p_{n}$ を前に動かせるならば動かす
    • 上記以外で $|S| \% 2 \neq t \% 2$ のとき、$S$ に $t$ を追加し、$p_{t}, p_{t + 1}$ を入れ替える
      • $p_{n}$ を前に動かせないときに手番を消費して偶奇を合わせる
    • 上記以外で $t + 1 \lt N$ のとき、$S$ に $t + 1$ を追加し、$p_{t + 1}, p_{t + 2}$ を入れ替え、$n = t + 1$ ならば $n = n + 1$ とする
      • $p_{n}$ を前に動かせないときの手番の消費その2
      • $p_{n}$ を後退させる可能性があるのでチェック
    • 上記以外のとき、$S$ に $t - 1$ を追加し、$p_{t - 1}, p_{t}$ を入れ替え、$n = t ,t = t - 1$ とする
      • $P = [ 1, 3, 2 ]$ のようなケースに対応するために必要
• $|S|$ および $S$ をそれぞれ出力する

実装

計算量はケースあたり $O(N^{2})$

公式解説

躓いた点

• 時間内に4番目の操作が必要なケースを思いつかずに対応しきれなかった