はじめに

問題文簡易日本語訳

ICPCの本部ビルには、M個の電球とNこのスイッチがある。それぞれの電球はちょうど1つのスイッチによってオンオフされる。それぞれの電球は複数の電球を操作できる。あなたがスイッチを切り替えたとき、そのスイッチにつながっているすべての電球の状態が変化する。しかし、あなたは、どのスイッチがどの電球につながっているか書いてある図をなくしてしまったので、それを作り直したい。

あなたはそのために以下の手順を踏む。

まず、すべてのスイッチをオフにする。この時、すべての電球はオフになる。
あなたは、 $S_1$ で示されるようにスイッチを操作する
電球の状態 $B_1$ を確認する
$S_2$ で示されるようにスイッチを操作する
電球の状態 $B_2$ を確認する ...
$S_Q$ で示されるようにスイッチを操作する
電球の状態 $B_Q$ を確認する。

あなたは、スイッチを操作した後に電球の状態を確認する。その後、スイッチを元に戻したりせずに、次のスイッチ操作を行う。

あなたは、これらの操作からスイッチと電球のつながりが復元できるだろうか。

入力

入力はいくつかのデータセットを含む。データセットの数は50以下である。それぞれのデータセットは以下のようになっている。

$N M Q$
$S_1 B_1$
$\vdots$
$S_Q B_Q$

一行目は3つの数字 $N (1 \leq N \leq 36), M (1 \leq M \leq 1,000), Q (0 \leq Q \leq 1,000)$ が与えられる。それぞれ、電球の数、スイッチの数、操作の数である。続く $Q$ 行は操作とその結果の電球の状態である。i番目の操作は文字列 $S_i$ と $B_i$ が空白区切りで与えられる。 $S_i$ は0か1からなる文字列で、j番目の文字は、0ならそのスイッチは操作せず、1ならそのスイッチを操作することを表す。 $B_i$ についも同様に0または1の文字列であり、それぞれ、j番目のスイッチがオフであること、スイッチがオンであることを表す

入力の終わりは3つのゼロで表される

出力

それぞれのデータセットについて、1つの文字列を1行に出力せよ。この文字列のi文字目は、i番目の電球がどこのスイッチにつながっているかを36進数で1文字で表わす。36進数とは、0-9, 10-35 までの数字を、0-9, A-Z を使って表す。 i番目の電球がどのスイッチにつながっているかわからない場合は、i番目の文字は?とする。

方針

クエリごとに各電球と各スイッチの関連を確認していると、O(nmq) = O(3.6*10⁷) となってしまい、time limit 8 秒なので間に合うのかもしれないが、ぎりぎりに見える。そこで、入力の方式に合わせてビット操作を行うことで、O(mn) = 0(10⁶) で済む方法で実装した。

こんな解説pdfもあるので参考にしてほしい

http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2014%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9C%B0%E5%8C%BA%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=B.pdf

大まかな方針としては、上の解説pdfのように、各電球について、つながっている可能性のあるスイッチ番目のビットを1、繋がっていないことが確実なスイッチ番目のビットを0とする。

入力例のSは、「今のスイッチの状態」ではなくて「どのスイッチを切り替えたか」なので、注意して欲しい。まずは今のスイッチの状態を保持しておく必要がある。これは簡単で、XORをとればいい。110の状態から101の操作を行うと、XORをとった011が今のスイッチの状態である。

これに対して、今の電球の状態は 1111111100 である。各電球について、最初は「すべてのスイッチとつながっている可能性がある状態」で初期化する。この時に、すべて1埋めはしないで、スイッチの数だけ1を埋めるようにしないと、スイッチが1つしかないようなコーナーケースで落ちてしまう（スイッチが1つしかない場合、当然すべての電球はそのスイッチにつながっている）。

さて、今の状態は011である。この時、1となっている電球については、011をANDでかけてやる。0となっている電球については、011をビット反転した100をANDでかけてやる。このようにしてマスクをかけていく感じにすると、最終的につながっている可能性のあるスイッチ部分のビットに1が立つ。

ループが終わったら、あとは1が立っているビットが1つでないなら?、1が立っているビットが1つなら、それに応じた数字または英字を出力すればいい。

コード概要

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){
            String[] in = br.readLine().split(" ");
            int n = Integer.parseInt(in[0]);
            int m = Integer.parseInt(in[1]);
            int q = Integer.parseInt(in[2]);
            if(n == 0 && m == 0 && q == 0) break;
            
            // bit_fill0 は 0 埋めした2進数
            // bit_fill1 は n桁を1で埋めた2進数
            Long bit_fill0 = 0L;
            Long bit_fill1 = 0L;
            for(int i = 0; i< n; i++)
                bit_fill1 = (bit_fill1<<1) | 1L;
            
            // フラグの初期化
            long[] bit = new long[m];
            for(int i = 0; i < m; i++) 
                bit[i] = bit_fill1;
            
            long state = bit_fill0;
            for(int i = 0; i < q; i++){
                in = br.readLine().split(" ");
                String s = in[0];
                String b = in[1];
                long sb = Long.parseLong(s, 2);
                // 現在のスイッチの状態を state で表す
                state = state ^ sb;
                
                for(int j = 0; j < m; j++){
                    int flag = b.charAt(j) - '0';
                    if(flag == 1){
                        // 電気がついた場合は、今1になったスイッチのどれかとつながっている
                        bit[j] = bit[j] & state;
                    }else{
                        // 電気がついてない場合は、今0のスイッチのどれかとつながっている
                        bit[j] = bit[j] & ~state;
                    }
                }
            }
            
            StringBuffer ans = new StringBuffer("");
            for(int i = 0; i < m; i++){
                if(Long.bitCount(bit[i]) == 1){
                    // 立っているbitが1つの場合
                    // それが答えなので36進数に変換してやる
                    int snum = n - 1 - Long.numberOfTrailingZeros(bit[i]);
                    ans.append(toChar(snum));
                }else{
                    // そうでない場合はわからない
                    ans.append('?');
                }
            }
            System.out.println(ans.toString());
        }
    }

    static char toChar(int i){
        if(i < 10){
            return (char)('0' + i);
        }else{
            return (char)('A' + (i - 10));
        }
    }
}

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

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

AOJ 2590: Unknown Switches

はじめに

問題文簡易日本語訳

入力

出力

方針

コード概要