Zenn
👌

AtCoder Beginner Contest 350 C - Sort 覚書き

2024/04/27に公開
AtCoder
tech

PHPで解答を作成しています。

問題のリンク
https://atcoder.jp/contests/abc350/tasks/abc350_c

解のポイント

解法のポイントはけんちょんさんの解説がわかりやすかった。
AtCoder ABC 350 C - Sort (灰色, 300 点)

  1. 計算量を気にせず考える
  2. 最後に高速化を試みる

高速化
「どこに値 i の要素があるのかを管理するテク」 を使う
↓
高難易度の問題では頻出するので覚えること！

今回は検索する値の方をkeyにした配列を作っていくのがキーポイントなのですが、なぜわざわざ値をkeyにするのか不思議じゃありませんか？
（私は不思議でした）
それは…以下の理由があるのです。

numbers[i]--;の意義
これは数字の配列の値をすべてマイナス1にしています。
はっきりいってこれがわかりにくかった。
（なので自分用に書いていく）

indexは0からはじまります。
数列は1からはじまります。

後からの処理でわかりますが、今回の場合は、indexの0に合わせて、数列も0から始まる方が処理が簡単になります。

そこで各値からマイナス1の処理を行います。
チューニング的な処理です。
というのは後からこういう事をしないといけないからです。
↓
↓
↓
// $i 番目がすでに値 $i なら何もしない
if (numbers[i] == $i) continue;

for文の中の$iを活用しての条件文であり、すでに収まるべき所にある数字の場合は続く処理をしないようになっています。

数列Aは1からはじまる数列です。
これを１からスタートする順番に並んだ配列にしていくわけです。
最終的にですが、例えば数字の1ならば、indexの0が収まるべき所です。

という訳でこの条件文は
if (numbers[i] == $i-1) continue;
という形にもできるのですが

以下のコードを見ればわかるように後からも順番を多用するため最初にindexとindexの番号と値を同じ$iで処理できるようにしておいた方が便利なのです。

  // $whereの順番を入れ替える
  list($where[$numbers[$i]], $where[$numbers[$j]]) = array($where[$numbers[$j]], $where[$numbers[$i]]);
  // $numbersの順番を入れ替える
  list($numbers[$i], $numbers[$j]) = array($numbers[$j], $numbers[$i]);
  // 入れ替えた位置を保存
  $res[] = array($i, $j);

最後に
echo ($pair[0] + 1)
にあるように1をプラスし値を調整しています。

使用する関数/演算子

全体コード

<?php

// 数字の個数
$n = trim(fgets(STDIN));

// 数字の配列
$numbers = explode(' ', trim(fgets(STDIN)));

// 値が存在する位置を保存する配列
$where = array();

for ($i = 0; $i < $n; ++$i) {
  $numbers[$i]--;
  // 値 $numbers[$i] があるのは $i 番目
  $where[$numbers[$i]] = $i;
}

// 左から $i 番目に、値 $i を持ってくる処理をする
$res = array();
for ($i = 0; $i <= $n - 2; ++$i) {
  // $i 番目がすでに値 $i なら何もしない
  if ($numbers[$i] == $i) continue;

  // 値 $i がある場所は$j番目
  $j = $where[$i];

  // $whereの順番を入れ替える
  list($where[$numbers[$i]], $where[$numbers[$j]]) = array($where[$numbers[$j]], $where[$numbers[$i]]);
  // $numbersの順番を入れ替える
  list($numbers[$i], $numbers[$j]) = array($numbers[$j], $numbers[$i]);
  // 入れ替えた位置を保存
  $res[] = array($i, $j);
}

// 出力
echo count($res) . "\n";
foreach ($res as $pair) {
  echo ($pair[0] + 1) . " " . ($pair[1] + 1) . "\n";
}

参考情報

Discussion