ABC250C
ABC250C の解説
解答コード
https://atcoder.jp/contests/abc250/submissions/31527138
問題
数列の数字を指定して右側の数字とswap する問題です.
解説
ゴールデンウィーク最終日にABC250へ参加した方,大変お疲れ様でした.
m(_ _)m
x のインデックスを計算量O(N) で参照すると間に合わないので,ある数字x がどのインデックスにいるのかを参照する配列を用意する必要があります.
概要図です.
計算量O(1)でインデックスを参照するために,配列(上図の窓口A)を用意する必要がありますが,そのせいで一回のswap 操作の処理が若干複雑になります.
その操作の流れを概要図で示しています.
配列をswap すると同時に,swap 後の新たな住所を窓口Aで住所変更する必要があります.
では,コードに移ります.プログラムはゼロインデックスで書いています.
標準入力と二つの窓口を用意します.
1回の操作について解説します.
変更したい数字x を読み取ります.
x の場所iを窓口Aに問い合わせます.
i の右隣j を定義します(i が右端の場合,j は左隣).
swap していませんが,転出届を窓口Aに提出します.
B[i] は 変数x そのものなので,xと書いても良いです.上下揃っているほうが見やすいので,B[i]で書いてます.
引っ越しをします.
上記の流れをfor 文で繰り返せば,OKです.
最後にゼロインデックスを解消して出力します.
以上,ABC250Cの解法でした.
<参考解説リンク>