Search on the blog

2011年3月7日月曜日

ショートコーディング: 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行目です!

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

0 件のコメント:

コメントを投稿