B - おとぎの国の高橋君
時間制限 : 2sec / スタック制限 : 10MB / メモリ制限 : 64MB問題文
高橋君の住むAtCoder国では、私達が普段使用する数字と同様に 10 個のアラビア数字 (0−9) の 10 進数が使われています。
しかし、私達が普段使用する数字は大小関係が 0<1<2<3<4<5<6<7<8<9 の順になっているのに対して、
AtCoder国の数字ではその大小関係が異なっています。
例えば、AtCoder国の数字では 0<9<8<7<6<5<4<3<2<1 の順になっている場合、
AtCoder国では 9 よりも 8 の方が大きいことになります。また、97 よりも 72 の方が大きいことになります。
AtCoder国の数字の大小関係といくつかの数が与えられるので、
AtCoder国の数字の大小関係で昇順に並び替えてください。
なお、私達が普段使用する数字同様、AtCoder国で最も小さい数字は 0 であることは決まっています。
入力
入力は以下の形式で標準入力から与えられる。b0 b1 ‥‥ b9入力は N+2 行ある。
N
a0
a1
:
:
aN−1
1 行目には、AtCoder国での 1 桁の数字の大小関係が与えられる。
AtCoder国では b0<b1<…<b9 であることを表している。
b0 は必ず 0 である。
重複する数字は存在せず、0 から 9 までの数字が 1 度ずつ現れる。
2 行目には並び替える数の個数を表す整数 N(1≦N≦777) が与えられる。
3 行目からの N 行には、j+3 行目に並び替える数を表す整数 aj(1≦aj≦777,777,777) が与えられる。
出力
与えられた数をAtCoder国の数字の大小関係にあわせて昇順に並び替え、標準出力に 1 行に 1 つの数字ずつ出力せよ。
なお、最後には改行を出力せよ。
出典
B: おとぎの国の高橋君 - AtCoder Regular Contest #009 | AtCoder回答
AtCoder/arc009_2.php at master · wada811/AtCoder<?php
// デバッグ用関数
function echos($array, $line){
echo $line . '::k: ' . implode(' ', array_keys($array)) . PHP_EOL;
echo $line . '::v: ' . implode(' ', $array) . PHP_EOL;
}
// 変換処理はここから
$cardinalNumber = trim(fgets(STDIN));
$cardinalNumbers = explode(' ', $cardinalNumber);
fscanf(STDIN, '%d', $n);
for($i = 0; $i < $n; $i++){
fscanf(STDIN, '%d', $targetNumbers[]);
}
// echos($targetNumbers, __LINE__);
// 14::k: 0 1 2 3 4 5 6 7 8 9
// 14::v: 1 2 3 4 5 6 7 8 9 10
// targetNumbers の数字をアルファベットに置換
$alphabets = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j');
$numbers = array_keys($alphabets);
$targetAlphabets = str_replace($numbers, $alphabets, $targetNumbers);
// echos($targetAlphabets, __LINE__);
// 21::k: 0 1 2 3 4 5 6 7 8 9
// 21::v: b c d e f g h i j ba
// このアルファベットを cardinalNumbers の順になるようにソート
$cardinalAlphabets = array();
for($i = 0, $end = count($cardinalNumbers); $i < $end; $i++){
$cardinalAlphabets[$i] = $alphabets[$cardinalNumbers[$i]];
}
// echos($cardinalAlphabets, __LINE__);
// 29::k: 0 1 2 3 4 5 6 7 8 9
// 29::v: a i b d f e j h g c
// targetAlphabets を cardinalAlphabets の k に置換
$numbers = array_keys($cardinalAlphabets);
$atCoderNumbers = str_replace($cardinalAlphabets, $numbers, $targetAlphabets);
// echos($atCoderNumbers, __LINE__);
// 35::k: 0 1 2 3 4 5 6 7 8 9
// 35::v: 2 9 3 5 4 8 7 1 6 20
// この数値を昇順に並べ替える
asort($atCoderNumbers);
// echos($atCoderNumbers, __LINE__);
// 40::k: 7 0 2 4 3 8 6 5 1 9
// 40::v: 1 2 3 4 5 6 7 8 9 20
// この順の k で targetNumbers を得る
$results = array();
$orders = array_keys($atCoderNumbers);
foreach($orders as $order){
$results[] = $targetNumbers[$order];
}
// echos($results, __LINE__);
// 49::k: 0 1 2 3 4 5 6 7 8 9
// 49::v: 8 1 3 5 4 9 7 6 2 10
// 出力！
echo implode(PHP_EOL, $results) . PHP_EOL;
?>
数字をAtCoder国の大小関係の数字に変換しようとしたら
str_replaceで配列を渡すと多重変換されてしまうようだった。
仕方ないので適当にアルファベットを間に挟んで変換していったら混乱したので
デバッグ用関数を作ったら結構すんなり解けた。
間にアルファベットを挟む分だけわかりにくくなっているが、
変換してしまえばasortでソートするだけだし、
ソートすればインデックスがわかるので逆変換しなくても
元の数字をそのインデックスの順に出力するだけで良い。
普段よりB問題から面倒くさかったかも。C問題も難しかったし。
プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～![プログラミングコンテストチャレンジブック [第2版] ~問題解決のアルゴリズム活用力とコーディングテクニックを鍛える~](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tAx4oXy581PVJCbgTq19kimtCjCZvGUK2pxynyw0ufdqFZqsGzjEkU-K2OCd2FuWcVfDC5ONvAfgHqer_tpBDhSjTGlboQSdxxdF2M_C5oQKCXyNWHuuseMjaQIynt4zkuV-Ub_h4PKQ=s0-d)
