はじめに

問題訳

（誤訳していたりしたら教えて下さい）

ネイサン・O・デービスは、集積システム専攻の学生である。

今日の授業は音声信号処理である。ネイサンは多くの宿題を与えられた。そのうちの一つは、音声信号処理のプログラムを書くことである。彼は音声信号をUSBメモリに入れて、家に持ち帰った。

宿題を始める時、ネイサンはUSBメモリを落としてしまった。 USBメモリの中身をチェックすると、音声信号が壊れてしまっていた。

彼がコピーした音声信号にはいくつかの特徴があった。

音声信号は連続したN個のサンプルからなるものであった
それぞれのサンプルは1以上N以下の整数値を持つ
奇数番目のサンプルは、その隣のサンプルよりも値が小さい
偶数番目のサンプルは、その隣のサンプルよりも値が大きい

彼はパニックになってあなたに助けを求めてきた。あなたは壊れた音声データから元の音声データを復元しようとしたが、一部復元できないものもあった。

あなたには、壊れた音声信号を入力として、元の信号を一意に復元できるかどうかを出力するプログラムを書いて欲しい。

入力

入力は複数のデータセットからなる。それぞれのデータセットは以下の形式で与えられる

N
a1 a2 ... aN

最初の行にはN (2 <= N <= 1000) が与えられる。 Nは音声信号に含まれるサンプルの数である。 2行目にはN個の値がスペース区切りで与えられる。 aiはi番目のサンプルの値である。 aは'x'または -10⁹ <= ai <= 10⁹ の値である。 i番目のサンプルが壊れている場合、ai = 'x' となる。

入力の終わりは一文字の0で与えられる。

データセットの数は100以下である。

出力

それぞれのデータセットに対して、xの値が一意に復元できるのであればその値を、複数の値が考えられる場合は "ambiguous"、当てはまる可能性のある値がない場合は "none" を出力せよ。（※ xにはすべて同じ値が入る）

解法

基本的にはxを求める問題であるが、xの値を求める以外にも様々な点に注意しなければならない。

xの求め方については、xの左右の値を確認し、xの取りうる最大値と最小値を保持していけば良い。
- 最大値 = 最小値となればその値がxの値である
- 最小値 < 最大値であれば ambigious
- 最小値 > 最大値であれば none
xが連続して出現している場合、信号の制約を満たさないので none である。（入力例2つめ）
そもそもxが出現しておらず、信号が制約を満たしている場合は ambigious である。（入力例3つめ）
ただし、そもそもx以外の部分で信号の制約を満たしていない場合もあるので、その場合は none になる。（入力例4つめ）
xが -10⁹から10⁹ 範囲に収まらない場合でも答えがnoneになったりはしない。（入力例5つめ）

以上のことをすべて考慮できた上で、「以上」「より小さい」などの条件や、最大値と最小値の取り違えなどに注意しつつ実装していけば解ける。

コード

正直このコードはかなり汚い。本当はもっとコードを関数なんかに分割するべきであった（時間があったらリファクタリングしたい）。

class Main extends MyUtil{
    // public static Graph g;
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        while(true){
            int n = Integer.parseInt(br.readLine());
            if(n == 0) break;
            
            String[] arr = br.readLine().split(" ");
            
            int min = -1000000002;
            int max = 1000000002;
            
            for(int i = 0; i < n; i++){
                if(arr[i].equals("x")){
                    // xが2つ並んでいた時点で、「xはxより大きい」となってしまい矛盾する
                    if(i != n-1 && arr[i+1].equals("x")){
                        min = 1000000002;
                        max = -1000000002;
                        break;
                    }
                    
                    // 注意: iは0始まりである
                    if(i % 2 == 0){
                        // iが偶数の場合、左右のどちらの値よりも小さい
                        if(i != 0)
                            max = Math.min(max, Integer.parseInt(arr[i-1]) - 1);
                        
                        if(i != n-1)
                            max = Math.min(max, Integer.parseInt(arr[i+1]) - 1);
                    }else{
                        // iが奇数の場合、左右のどちらの値よりも大きい
                        if(i != 0)
                            min = Math.max(min, Integer.parseInt(arr[i-1]) + 1);
                        
                        if(i != n-1)
                            min = Math.max(min, Integer.parseInt(arr[i+1]) + 1);
                    }
                }else{
                    // 左右の数字の大きさに矛盾がないことを確認しなければならない
                    int value = Integer.parseInt(arr[i]);
                    int left_value = 0, right_value = 0;
                    boolean left_flag = true, right_flag = true;
                    try{
                        left_value = Integer.parseInt(arr[i-1]);
                    }catch(Exception e){
                        left_flag = false;
                    }
                    try{
                        right_value = Integer.parseInt(arr[i+1]);
                    }catch(Exception e){
                        right_flag = false;
                    }
                    
                    if(i % 2 == 0){
                        // iが偶数の場合、左右のどちらの値よりもちいさくなければならない
                        if(left_flag && left_value < value){
                            // 矛盾がある場合
                            min = 1000000002;
                            max = -1000000002;
                            break;
                        }
                        
                        if(right_flag && right_value < value){
                            min = 1000000002;
                            max = -1000000002;
                            break;
                        }
                    }else{
                        // iが奇数の場合、左右のどちらの値よりも大くなければならない
                        if(left_flag && left_value > value){
                            min = 1000000002;
                            max = -1000000002;
                            break;
                        }
                        
                        if(right_flag && right_value > value){
                            min = 1000000002;
                            max = -1000000002;
                            break;
                        }
                    }
                }
            }
            
            if(max == min){
                System.out.println(max);
            }else if(min < max){
                System.out.println("ambiguous");
            }else{
                System.out.println("none");
            }
        }
    }
}

猫でもわかるWebプログラミングと副業

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

AOJ 2565: Broken Audio Signal

はじめに

問題訳

入力

出力

解法

コード