Codeforces Round #499 (Div. 1): D. Mars rover

http://codeforces.com/contest/1010/problem/D

問題概要

N頂点の根付き木が与えられる。すべての葉にはあらかじめ1か0の入力が与えられており、葉以外の頂点はすべて「子から来たビットを入力として論理演算をし、その出力を親に送る」機能を持っている。演算の種類はNOT, AND, OR, XORであり、NOTの頂点はひとつの子、それ以外は2つの子を持つ。すべての葉について、その葉の入力のみ反転させたとき、最終的に根が出力するビットが何になるかを求めよ。

N <= 106

解法

まずあらかじめ与えられた入力での計算結果がどうなるかは事前にO(N)で計算できる。その上でまた根から順に「もし子が送ってくる出力が反転したら、この頂点の出力も反転するか」を求めていく。例えばANDの頂点で両方の子がともに0ならば、どちらかの子が反転したところで結局出力は0になる(=その下の葉で入力が何になろうと最終的な答えは変わらない)。一方で左の子が1, 右の子が0だった場合、右の子が反転するとANDの出力も0から1に反転する。よって右の子の反転は最終的な結果も反転させうる(もちろんそれより上の頂点で反転が無意味になってたら駄目)。という感じで場合分けしてDFSしていくと最終的にそれぞれの葉で反転が有効か無効かがわかる。有効なら最初に求めた根の出力を反転させればいいし、そうでないならそのままの出力を使えばいい。

感想

まったく見当違いなことをしていた(NOTは縮約できるじゃん→そしたら2分木になるから高さlogNじゃん→は?)

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

void main() {
    enum OP {IN, NOT, AND, OR, XOR};
    auto N = readln.chomp.to!int;
    auto G = new int[][](N, 2);
    auto P = new int[](N);
    auto B = new bool[](N);
    auto V = new bool[](N);
    auto ops = new OP[](N);

    foreach (i; 0..N) {
        auto s = readln.split;
        string op = s[0];
        foreach (j; 1..s.length) {
            int a = s[j].to!int - 1;
            G[i][j-1] = a;
            if (op != "IN")
                P[a] = i;
        }
        
        if (op == "IN") {
            ops[i] = OP.IN;
            B[i] = s[1] == "1";
        } else if (op == "NOT") {
            ops[i] = OP.NOT;
        } else if (op == "AND") {
            ops[i] = OP.AND;
        } else if (op == "OR") {
            ops[i] = OP.OR;
        } else {
            ops[i] = OP.XOR;
        }
    }

    bool operate(int n) {
        bool a = G[n][0] >= 0 ? B[G[n][0]] : 0;
        bool b = G[n][1] >= 0 ? B[G[n][1]] : 0;
        if (ops[n] == OP.IN) {
            return B[n];
        } else if (ops[n] == OP.NOT) {
            return !a;
        } else if (ops[n] == OP.AND) {
            return a & b;
        } else if (ops[n] == OP.OR) {
            return a | b;
        } else if (ops[n] == OP.XOR) {
            return a ^ b;
        }
        return 0;
    }

    void init(int n) {
        if (ops[n] == OP.IN) {
            return;
        } else if (ops[n] == OP.NOT) {
            int a = G[n][0];
            init(a);
        } else {
            int a = G[n][0];
            int b = G[n][1];
            init(a);
            init(b);
        }
        B[n] = operate(n);
    }

    void dfs(int n, bool valid) {
        V[n] = valid;
        int a = G[n][0];
        int b = G[n][1];
        if (ops[n] == OP.NOT) {
            dfs(a, valid);
        } else if (ops[n] == OP.AND) {
            if (B[a] && B[b]) {
                dfs(a, valid);
                dfs(b, valid);
            } else if (B[a] && !B[b]) {
                dfs(a, false);
                dfs(b, valid);
            } else if (!B[a] && B[b]) {
                dfs(a, valid);
                dfs(b, false);
            } else {
                dfs(a, false);
                dfs(b, false);
            }
        } else if (ops[n] == OP.OR) {
            if (B[a] && B[b]) {
                dfs(a, false);
                dfs(b, false);
            } else if (B[a] && !B[b]) {
                dfs(a, valid);
                dfs(b, false);
            } else if (!B[a] && B[b]) {
                dfs(a, false);
                dfs(b, valid);
            } else {
                dfs(a, valid);
                dfs(b, valid);
            }
        } else if (ops[n] == OP.XOR) {
            dfs(a, valid);
            dfs(b, valid);
        }
    }

    init(0);
    dfs(0, true);
    N.iota.filter!(i => ops[i] == OP.IN).map!(i => V[i] ? !B[0] : B[0]).map!(i => i.to!int.to!string).join("").writeln;
}