yukicoder No.359 門松行列

問題

No.359 門松行列 - yukicoder

解法

門松列は結局数同士の大小関係で定義されますが, 大小関係が逆転する可能性があるのは, この後並べようとしている竹の高さが既に配置されている竹より大きくなる時か, 小さくなる時だけと考えられます。実はあと x > L-x となるところも境界線です。

これらの高さだけが 門松行列になる/ならないの境界線なので, 後は区間で管理しながら一気に数え上げれば大きい L に対しても高速に計算することが出来ます。

bool isKadomatsu(int a0, int a1, int a2) {
    if (a0 == a1 || a0 == a2 || a1 == a2) return false;
    if (a0 > a1 && a1 < a2) return true;
    if (a0 < a1 && a1 > a2) return true;
    return false;
}

int A[3][3];

bool isOK() {
    for (int i = 0; i < 3; i++) {
        if (!isKadomatsu(A[i][0], A[i][1], A[i][2])) return false;
        if (!isKadomatsu(A[0][i], A[1][i], A[2][i])) return false;
    }
    if (!isKadomatsu(A[0][0], A[1][1], A[2][2])) return false;
    if (!isKadomatsu(A[0][2], A[1][1], A[2][0])) return false;
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        int L;
        cin >> L;
        vi empty;
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) {
            cin >> A[i][j];
            if (A[i][j] == 0) empty.push_back(i*3+j);
        }
        vi vs;
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) {
            if (A[i][j] != 0) {
                if (L-A[i][j] > 0) {
                    vs.push_back(A[i][j]);
                    vs.push_back(L-A[i][j]);
                }
            }
        }
        for (int i = -1; i <= 1; i++) {
            if (L/2+i > 0) vs.push_back(L/2+i);
        }
        vs.push_back(L/2);
        sort(vs.begin(), vs.end());
        vs.erase(unique(vs.begin(), vs.end()), vs.end());
        vector<pii> ps;
        int n = vs.size();
        if (vs[0] > 1) ps.emplace_back(1, vs[0]-1);
        for (int i = 0; i < n; i++) {
            ps.emplace_back(vs[i], vs[i]);
            if (i < n-1) {
                if (vs[i]+1 < vs[i+1]) ps.emplace_back(vs[i]+1, vs[i+1]-1);
            }
        }
        if (vs.back() < L-1) ps.emplace_back(vs.back()+1, L-1);
        int ans = 0;
        for (pii p : ps) {
            A[empty[0]/3][empty[0]%3] = p.first;
            A[empty[1]/3][empty[1]%3] = L-p.first;
            if (isOK()) {
                ans += p.second-p.first+1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}