ことさら−古都プログラマーの更級日記

京都でお寺を回りながら御朱印集めをしていたエンジニアのブログ。おもに技術的なはなしとか日常的なはなし

AOJ 1336: The Last Ant

問題概要

アリが細いトンネルを歩いている。トンネルにはすれ違える場所とすれ違えない場所があって、すれ違えない場所でアリが出会ったらそれぞれ反対方向に進む。すれ違える場所ではそのまますれ違う。すべてのアリがトンネルから出るまでにかかる時間と、最後に出てきたアリを答えよ。最後に同時に2匹出てきた場合は、左から出てきたアリを答えよ。

方針

蟻本の問題っぽいが、違う。アリがすれ違える可能性がある。また、最後に出てきたアリがどれかを答える必要があるので、シミュレーションする必要がある。

右向きのアリを保持する配列と、左向きのアリを保持する配列を作って解いた。

ソースコード

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;
    }
}