B - 迷子のCDケース
時間制限 : 2sec / スタック制限 : 10MB / メモリ制限 : 64MB問題文
高橋君はCDで音楽を聴くことが好きです。CDプレイヤーには先日聴いたCDが入ったままになっているのですが、
そのCDに対応するCDケースが見当たらないことに気づきました。
前回に聴いた時にCDケースをどこに置いたのか、残念ながら高橋君は全く思い出せませんでした。
仕方がないので高橋君は今から聴こうとしているCDをケースから取り出し、
CDプレイヤーに入っていたCDをそのケースへと片付けることにしました。
さらに別のCDを新たにCDプレイヤーに入れる場合も、
CDプレイヤーに入っていたCDは空いたCDケースに片づけます。
例えば図 1(※省略)のように 3 枚のCDがある状態で、
黄緑色のCD、オレンジ色のCDの順でCDを聴くと、
それぞれのCDは最も下の図(※省略)のように片付けられることになります。
高橋君が音楽を聴き終わった後、今日聞いたCDのリストが与えられるので、
高橋君が所持するCDケースにはそれぞれどのCDが入っているかを答えなさい。
入力
入力は以下の形式で標準入力から与えられる。N M入力は M+1 行ある。
disk0
disk1
:
:
diskM−1
1 行目には、高橋君が所持するCDケースの個数を表す整数 N(1≦N≦100)と、
今日聴いたCDの枚数 M(0≦M≦100) が空白区切りで与えられる。
CDケースを 1 つ無くしているので、高橋君は計 N+1 枚のCDを所持している。
CDと対応するCDケースにはそれぞれ 0 から N までの数が番号付けられている。
現在CDプレイヤーに入ってるCDとそれに対応する見当たらないCDケースは 0 番である。
2 行目からの M 行には今日聴いたCDの番号のリストが与えられる。
i+2 行目の整数 disk i (0 ≦ i ≦ M−1, 0 ≦ disk i ≦ N) は i+1 番目に disk i 番のCDを聴いたことを表している。
出力
1 から N 番までのCDケースに入ってるCDの番号を順に標準出力に 1 行に 1 ケース分ずつ出力せよ。なお、最後には改行を出力せよ。
出典
B: 迷子のCDケース - AtCoder Regular Contest #007 | AtCoder回答
AtCoder/arc007_2.php at master · wada811/AtCoder · GitHub<?php
fscanf(STDIN, "%d %d", $n, $m);
for($i = 0; $i < $m; $i++){
fscanf(STDIN, "%d", $playlist[]);
}
$now = 0;
for($i = 1; $i <= $n; $i++){
$case[] = $i;
}
for($i = 0; $i < $m; $i++){
if($now !== $playlist[$i]){
$next = array_search($playlist[$i], $case);
list($case[$next], $now) = array($now, $case[$next]);
}
}
for($i = 0; $i < $n; $i++){
echo $case[$i].PHP_EOL;
}
?>
プレイリストが現在再生中の CD 以外だったら入れ替え。
コレをしないと array_search で false が返ってきてしまう。
13行目は list を使ったテクニカルな変数のスワップ(入れ替え)方法。
普通に $tmp = $a; $a = $b; $b = $tmp; の円環の順で書く方法でも良かったのだけど
PHP でスワップするのは初めてだったのでなんかあるかなと調べてみたらあった。
初見の人は何やってるかわからなくて戸惑いそうだから使いにくい感じはあるけど…。
ちなみに now playing を一緒に配列に入れても解ける。
Submission #44496 - AtCoder Regular Contest #007 | AtCoder
CD を主体にするか、ケースを主体にするかの違いなんだけど
あんまりセマンティックな感じがしないので不採用でした。まぁ好みの問題ですね。