ショートコーディング: Not演算

チルダみたいな記号「~」ってC/C++にあるけど、いつ使うのだろう。。

ショートコーダーは日常茶飯事に使う。

例えば、EOF。

EOFは多くのコンパイラでは-1である。そして整数の中で優一ビットをすべて反転した場合に0になるのが-1である。

while (scanf("%d", &n) != EOF)

を

while (~scanf("%d", &n))

と書いたりする。

最近、私がよく使うのは、bool値を配列に格納したい場合である。普通なら0で初期化して、0でなければ値が設定されているとすればいいが、boolの場合はFalseを設定すると0とみなされる。

なので、char型にboolをぶちこむ。そして、char配列は-1で初期化しておく。

すると、not値が0の場合は、値が未設定となるので、スマートなコーディングが可能となる。

boolをcharに入れるなんてメモリの無駄と思う人もいるかもしれないが、実は、C/C++ではboolはほとんどの環境では1byteである。。なので実は無駄じゃない。

で、boolをchar配列に入れて、not演算を使ってエレガントに値の設定を判別したコードがこちら。。

Nimという数取りゲームの一般形において先手に必勝手が存在するかどうかをゲーム木で判定しています。注目すべきは、solveの3行目です！

view plainprint?

1. int n;  
2. VI nums;  
3. char memo[1<<15][22];  
4.   
5. bool solve(int turn, int s) {  
6.    if (!s) return true;  
7.    if (~memo[s][turn])  
8.        return memo[s][turn];  
9.   
10.    turn %= (2*n);  
11.    int ret = false;  
12.    FOR (x, 1, nums[turn]+1)  
13.        if (s-x >= 0)  
14.            ret |= !solve(turn+1,s-x);  
15.   
16.    return memo[s][turn] = ret;  
17. }  
18.   
19. int main() {  
20.    while (scanf("%d", &n), n) {  
21.        int s;  
22.        scanf("%d", &s);  
23.        nums.clear();  
24.        memset(memo, 0xFF, sizeof(memo));  
25.        int x;  
26.        REP(i, 2*n) {  
27.            scanf("%d", &x);  
28.            nums.push_back(x);  
29.        }  
30.        printf("%d\n", (int)solve(0, s));  
31.    }  
32.   
33.    return 0;  
34. }  

int n;
VI nums;
char memo[1<<15][22];

bool solve(int turn, int s) {
   if (!s) return true;
   if (~memo[s][turn])
       return memo[s][turn];

   turn %= (2*n);
   int ret = false;
   FOR (x, 1, nums[turn]+1)
       if (s-x >= 0)
           ret |= !solve(turn+1,s-x);

   return memo[s][turn] = ret;
}

int main() {
   while (scanf("%d", &n), n) {
       int s;
       scanf("%d", &s);
       nums.clear();
       memset(memo, 0xFF, sizeof(memo));
       int x;
       REP(i, 2*n) {
           scanf("%d", &x);
           nums.push_back(x);
       }
       printf("%d\n", (int)solve(0, s));
   }

   return 0;
}