猫でもわかるWeb開発・プログラミング

本業エンジニアリングマネージャー。副業Webエンジニア。Web開発のヒントや、副業、日常生活のことを書きます。

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