AtCoder Regular Contest #013

久しぶりのコンテスト。

結果

A,B,C+D部分点の320点、2WAで63:58の27位。
復帰戦にしてはよい成績だった。

A

next_permutationで全探索するだけ

B

ソートしてそれぞれの要素についてmax取って積取るだけ

C

問題読んでGrundy数かーと思う。
切断する->任意の1方向の長さを減らす、という操作なので
それを使ってGrundy数を計算していくには状態数が多すぎる。

加えてハバネロが2ヶ所以上の場合は終端状態をどう取るのか解らないので図を書いてみる。
と、全てのハバネロを含む最小の直方体を考えると、その直方体は切れないということに気づく。

次に、じゃあそのサイズ分を引いてxor取ればいいかなと思うものの合わないので考えてみると
1方向で見てooxという場合とoxoという場合は異なる状態であることに気づく。

なので、1つの豆腐について
3次元それぞれについて前述の直方体より負方向の数と正方向の数
の6個の山のNimとして考えればよい。

int main(){
    int n;
    int ans=0;
    cin >> n;

    for(int x=0;x<n;x++){
        int x,y,z,p,q,r;
        int x_min = 1 << 30, x_max = -1, y_min = 1 << 30, y_max = -1, z_min = 1 << 30, z_max = -1;
        int times[6] = {0};
        int m;
        cin >> x >> y >> z >> m;
        for(int i=0;i<m;i++){
            cin >> p >> q >> r;
            x_min = min(x_min ,p);
            y_min = min(y_min, q);
            z_min = min(z_min, r);
            x_max = max(x_max ,p);
            y_max = max(y_max, q);
            z_max = max(z_max, r);
        }
        times[0] = x_min;
        times[1] = x - x_max - 1;
        times[2] = y_min;
        times[3] = y - y_max - 1;
        times[4] = z_min;
        times[5] = z - z_max - 1;
        ans = ans ^ times[0] ^ times[1] ^ times[2] ^ times[3] ^ times[4] ^ times[5];
    }
    if(ans == 0){
        cout << "LOSE" << endl;
    }else{
        cout << "WIN" << endl;
    }
}

初め1<<29で初期化していた…1<<29　<　10^9なので死んだ。アホである。

D

解けなそうなのが解ったので部分点狙い。
全ての切り方を試してみて出来る重さのペアをsetに突っ込む。
(x,y)というペアについてx==yなら鉄塊は1個でよくて、
x!=yなら鉄塊が2個必要。

nが2以上の場合はグラフに落として解けるらしい。