AtCoder Beginner Contest 337 C - Lining Up 2 備忘録 PHP

PHPで解いています。

問題はこちら。

https://atcoder.jp/contests/abc337/tasks/abc337_c

解のポイント

C問題ではよくあるパターンなのですが、

• 通所の数字や文字の位置がキーポイントになっている
• 値と位置をトリガーに順番を入れ替える
  という感じの問題です。

この問題は最終的には、例えば-1の場合は先頭、という風に「ある数字を検索できたら位置が決まる」というものです。

それならば、「ある数字を検索すればすぐに位置がわかる」配列を作るのが適当だと考えます。

検索をする値はkeyに入れておくのがポイントです。
なぜなら、一意であるため、先頭から検索していく必要がなく検索でき、検索スピードが圧倒的に早いためです。

という事で以下の手順で作っていきます。

1. 数字を配列に入れる（この時、検索する値をkeyにするのがポイント）
2. 配列からサーチして、結果の配列に入れる
3. 結果の配列をechoでだす

全体コード

実行時間 94ms

<?php
$N = trim(fgets(STDIN));
$s = fgets(STDIN);

$s_array = explode(' ', trim($s));

// 位置用配列
$s_map = [];
// 値でサーチしやすいように値をkeyに入れ位置をvalueに入れる
foreach ($s_array as $key => $value) {
  $s_map[$value] = $key + 1;
}

// print_r($s_map);
// Array
// (
//     [4] => 1
//     [1] => 2
//     [-1] => 3
//     [5] => 4
//     [3] => 5
//     [2] => 6
// )

$result = array(); 
$j = $s_map[-1];
$result[] = $j;
for ($i = 1; $i < $N; $i++) {
  $j = $s_map[$j];
  $result[] = $j;
}

echo implode(' ', $result) . PHP_EOL;