0011-Drawing Lots
問題(外部リンク)
実装の概要
Sample Inputの場合、時刻0で(2,4)間に入れ替え発生、時刻1で(3,5)間に入れ替え発生…と解釈することができます。まずは入れ替えに関わるデータを配列に保存しておきます。このとき、a→bだけでなくb→aの移動も忘れてはいけません。
実際に横の移動が行われるのは、自分が今いるラインについて移動先が定義されている場合です。今回の実装では初期化の時点でデフォルトの移動先を今いるラインと同じところに設定しているので、あみだくじスタート後は特にチェックの必要はありません。
public class Main { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int lineNum = Integer.parseInt(br.readLine()); int changeNum = Integer.parseInt(br.readLine()); int[][] changer = new int[changeNum+1][lineNum+1]; //初期化 for(int i = 1; i <= changeNum ; i++){ for(int j = 1; j <= lineNum; j++){ changer[i][j] = j; } } //入力読み込み for(int i = 1;i <= changeNum; i++){ String[] tmpStr = br.readLine().split(","); changer[i][Integer.parseInt(tmpStr[0])] = Integer.parseInt(tmpStr[1]); changer[i][Integer.parseInt(tmpStr[1])] = Integer.parseInt(tmpStr[0]); } //あみだ処理 int[] answer = new int[lineNum + 1]; for(int i = 1; i <= lineNum ; i++){ int tmpAnswer = i; for(int j = 1; j <= changeNum ; j++){ tmpAnswer = changer[j][tmpAnswer]; } answer[tmpAnswer] = i; } for(int i = 1; i <= lineNum; i++){ System.out.println(answer[i]); } } }