問題概要
アリが細いトンネルを歩いている。トンネルにはすれ違える場所とすれ違えない場所があって、すれ違えない場所でアリが出会ったらそれぞれ反対方向に進む。すれ違える場所ではそのまますれ違う。すべてのアリがトンネルから出るまでにかかる時間と、最後に出てきたアリを答えよ。最後に同時に2匹出てきた場合は、左から出てきたアリを答えよ。
方針
蟻本の問題っぽいが、違う。アリがすれ違える可能性がある。また、最後に出てきたアリがどれかを答える必要があるので、シミュレーションする必要がある。
右向きのアリを保持する配列と、左向きのアリを保持する配列を作って解いた。
ソースコード
- http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1375966
- 今まで気づいてなかったけど日本語文字化けしてる…?
class Main{ public static void main(String[] args) throws Exception{ Scanner sc = new Scanner(new InputStreamReader(System.in)); while(true){ // 入出力 int n = sc.nextInt(); int m = sc.nextInt(); if(n+m == 0) break; int[] lant = new int[m+1]; int[] rant = new int[m+1]; for(int i = 1; i <= n; i++){ char dir = sc.next().charAt(0); int x = sc.nextInt(); if(dir =='R'){ rant[x] = i; }else{ lant[x] = i; } } // シミュレーション開始 int last_ant = 0; int cnt = 0; while(check(rant, lant)){ cnt++; if(rant[m] != 0){ last_ant = rant[m]; rant[m] = 0; } for(int i = m-1; i >= 0; i--){ rant[i+1] = rant[i]; rant[i] = 0; } if(lant[0] != 0){ last_ant = lant[0]; lant[0] = 0; } for(int i = 1; i <= m; i++){ if(lant[i] == 0) continue; if(rant[i-1] != 0){ lant[i-1] = rant[i-1]; rant[i-1] = lant[i]; lant[i] = 0; }else{ lant[i-1] = lant[i]; lant[i] = 0; } } } cnt--; System.out.println(cnt + " " + last_ant); } sc.close(); } /** * トンネル内にアリが残っているかどうかを確認する関数 * ループの終了条件に使う。 */ static boolean check(int[] a, int[] b){ for(int i = 0; i < a.length; i++){ if(a[i] != 0) return true; if(b[i] != 0) return true; } return false; } }