naoya_t@hatenablog

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

LeetCode Weekly Contest 120

1/20(日) 11:30-13:00

1問目が易しいせいか最初サーバが重く、問題開きづらい、Run Codeできない、Submitできない等あったので3問目までは気にせず先に問題を解いていった

4完1ペナで215/3852位
レート不動(2279→2279)

A 全要素自乗してから並べ替え
B 前回の上がり下がりを記憶して
C 葉から根へ差分を上げて足し合わせ
D 多分これ大した数にならないぞdfsで余裕なのでは

Q1 - 977. Squares of a Sorted Array (2)

全要素を自乗してからソート
フォーム上でコードを編集してRun Codeして一発
→AC 4:08

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int L=A.size();
        rep(i,L) A[i] *= A[i];
        sort(ALL(A));
        return A;
    }
};

Q2 - 978. Longest Turbulent Subarray (5)

前回上がったか下がったか覚えておいてカウント
フォーム上でコードを編集してRun Codeして一発で…全部-1した値が出てきたので+1して投げて
→AC 21:08

class Solution {
public:
    int maxTurbulenceSize(vector<int>& A) {
        int L=A.size();
        int cnt=0, maxc=0, last=0;
        rep(i,L-1) {
            if (A[i+1]==A[i]) { 
                cnt = 0; 
                last = 0;
            } else if (A[i+1] > A[i]) {
                if (last == -1) {
                    cnt ++;
                } else {
                    cnt = 1;
                }
                last = 1;
            } else {
                if (last == 1) {
                    cnt ++;
                } else {
                    cnt = 1;
                }
                last = -1;            
            }
            maxc = max(maxc, cnt);
        }
        return maxc+1;
    }
};

Q3 - 979. Distribute Coins in Binary Tree (6)

フォーム上でコードを編集してRun Codeして一発で通ったので投げた
→AC 22:03
ここまで解いて37位とかだった

class Solution {
    ii sub(TreeNode* root){
        int have = root->val;

        ii l = (root->left) ? sub(root->left) : ii(0,0);
        ii r = (root->right) ? sub(root->right) : ii(0,0);
        have += l.second + r.second;
        int diff = have - 1;
        int sc = abs(diff) + l.first + r.first;
        
        return ii(sc, diff);
    }
public:
    int distributeCoins(TreeNode* root) {
        ii al = sub(root);
        return al.first;
    }
};

Q4 - 980. Unique Paths III (7)

これはローカルでコード編集

思うほどパターン数なさそう
DFSでバックトラックで

実装中に足がつって一時中断したり(これは昨日の写真撮影のせいなのでは)
マウスカーソルが飛んで使い物にならなかったりと
トラブルはあったけど出来たので投げる

デバッグ印刷用にbitsetを12とかにしたまま投げちゃって1WA
→直してAC 59:15 + 1P
1ペナルティ5分で161位→215位まで落ちるとかきつい

終わってから気づいたけど(1\le R\le 20,1\le C\le 20ではなく)1\le R\cdot C\le 20なのね…

#define RC(r,c) ((r)*C+(c))

class Solution {
    int R, C;
    vector<vector<int>> g;
    int sr,sc, gr,gc;
    int pot;
    int ans;
    bitset<400> s;

    void dfs(int r,int c){
        if (r==gr && c==gc) {
            if (s.count()+1 == R*C) {
                ++ans;
            }
            return;
        } else {
            if (s.count()+1 == R*C) {
                return;
            }
        }

        int x=RC(r,c);
        if (s.test(x)) return; // visited
        s.set(x, true);
        {
            if (r-1 >= 0 && !s.test(RC(r-1,c)))
                dfs(r-1, c);
            if (r+1 < R && !s.test(RC(r+1,c)))
                dfs(r+1, c);
            if (c-1 >= 0 && !s.test(RC(r,c-1)))
                dfs(r, c-1);
            if (c+1 < C && !s.test(RC(r,c+1)))
                dfs(r, c+1);
        }
        s.set(x, false);
    }

public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        ans=0; pot=0;
        g=grid;
        R=g.size(),C=g[0].size();
        s.reset();
        rep(r,R)rep(c,C){
            switch (g[r][c]){
                case 0: pot++; break;
                case 1: sr=r; sc=c; pot++; break;
                case 2: gr=r; gc=c; pot++; break;
                default:
                    s.set(RC(r,c)); break;
            }
        }

        // s.set(RC(sr,sc));
        dfs(sr, sc);

        return ans;
    }
};