naoya_t@hatenablog

いわゆるチラシノウラであります

LeetCode Weekly Contest 124

LeetCode Weekly Contest 124

全完50/3758位
調子いいね

Q1 全ノード先に調べてルックァップ
Q2 とりあえずこれは愚直にシミュレート
Q3 左からただの貪欲なんだけど、deque使って計算減らす
Q4 DPで重複含め数え上げ、重複数の階乗で割る

レートも2288→2299 (+11)
f:id:n4_t:20190223015439p:plain:w480

Q1 - Cousins in Binary Tree (4)

全ノード調べてからルックアップした
→ AC 04:45

class Solution {
    map<int,ii> mp;
    void sub(TreeNode* root, int p, int d){
        if (!root) return;
        mp[root->val] = ii(p, d);
        sub(root->left, root->val, d+1);
        sub(root->right, root->val, d+1);
    }
public:
    bool isCousins(TreeNode* root, int x, int y) {
        sub(root, -1, 0);
        ii p1=mp[x], p2=mp[y];
        return (p1.second == p2.second) && (p1.first != p2.first);
    }
};

Q2 - Rotting Oranges (5)

シミュレーション
visitedチェックしてないから効率悪いけどこの制約ならいいかと思って投げた
→ AC 17:05

int dx[4] = { 1, 0, -1, 0 },
    dy[4] = { 0, 1, 0, -1 };

class Solution {
    vvi G;
    int H, W, C;
    // set<ii> visited;
    int sub(){
        queue<ii> q;                
        rep(r,H) rep(c,W){ if (G[r][c] == 2) q.emplace(r,c); }
        int decr = 0;
        while (!q.empty()) {
            ii f = q.front(); q.pop();
            // if (found(visited, f)) continue;
            rep(i,4) {
                int r=f.first+dx[i], c=f.second+dy[i];
                if (IN(r,0,H-1) && IN(c,0,W-1)) {
                    if (G[r][c] == 1) {
                        G[r][c] = 2; C--;
                        decr++;
                    }
                }
            }
        }
        return decr;
    }
public:
    int orangesRotting(vector<vector<int>>& grid) {
        G=grid;
        H=G.size(); W=G[0].size();
        vi st(3, 0);
        rep(r,H) rep(c,W){ st[G[r][c]]++; }
        C = st[1];
        int turn = 0;
        while (true) {
            if (C == 0) return turn;
            ++turn;
            int decr = sub();
            if (decr == 0) break;
        }
        if (C != 0) return -1;
        return turn;
    }
};

Q3 - Minimum Number of K Consecutive Bit Flips (6)

左から貪欲なんだけど
O(N^2)は避けたいよなこれ
と思ってdequeで過去K-1回のフリップ回数を数えた
→ AC 24:24

class Solution {
public:
    int minKBitFlips(vector<int>& A, int K) {
        int L = A.size();
        int ans = 0;
        deque<int> tat;
        rep(i,L){
            while (!tat.empty() && tat.front() <= i-K) tat.pop_front();
            int flip = tat.size();
            if ((A[i] + flip) % 2 == 1) continue;
            if (i < L-K+1) {
                tat.push_back(i); ++ans;
            } else {
                return -1;
            }
        }
        return ans;
    }
};

Q4 - Number of Squareful Arrays (6)

DはDPのD

  • dp[i番目まで][最後がj番目][使用済集合] = 何通り

int dp[12][12][4096]だとMLEみたいで怒られたのでdp[2][12][4096]で
→ AC 44:32

bool sq(int x){
    int s = sqrt(x);
    if (s*s == x) return true;
    if ((s+1)*(s+1) == x) return true;
    return false;
}

int dp[2][12][4096];


// 12! = 479001600
class Solution {
public:
    int numSquarefulPerms(vector<int>& A) {
        int L = A.size();
        int P = 1<<L;

        vvi d(L, vi(L, 0));
        repC2(i,j,L){
            if (sq(A[i] + A[j])) d[i][j] = d[j][i] = 1;
        }
        
        mset(dp, 0);
        rep(i,L) {
            dp[1][i][1<<i] = 1;
        }
        for (int o=2; o<=L; ++o){
            rep(i,L){
                rep(m,P) {
                    int v = dp[(o-1)%2][i][m];
                    // if (v == -1) continue;
                    rep(j,L){
                        if (j==i) continue;
                        if (m & (1 << j)) continue;
                        if (!d[i][j]) continue;
                        dp[o%2][j][m | (1 << j)] += v;
                    }
                }
            }
        }

        int ans = 0;
        rep(i,L){
            ans += dp[L%2][i][P-1];
        }
        vi fact(L+1, 1);
        for (int i=2; i<=L; ++i) fact[i] = fact[i-1] * i;

        map<int,int> st;
        rep(i,L) st[ A[i] ]++;

        for(ii p: st){
            ans /= fact[p.second];
        }
        
        return ans;
    }
};