naoya_t@hatenablog

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


LeetCode Weekly Contest 115

12/16(日) 11:30-13:00(近所のスタバで)
3完 195/3055位...
レートちょっと落ちるのでは?

終わってからQ4を通そうと頑張ってて、気がついたら30分経ってた*1

昨日のAGCでもそうなんだけど、自分がこれと思って飛びついた解法に固執して時間を溶かすことがよくある。そのまま突き進めば解けるかもしれないけど、他にも解けるはずだった問題に時間を割けずに終わることになる。
別の言い方をすると「コンテスト中であることを忘れて問題に没頭してしまう」。
エレガントでなくてもオーバーキルでもいいからすぐに使える道具で殴るとか、デバッグにはまって時間を溶かすぐらいなら一旦手放すとか、そういう冷静さ?を取り戻す必要がある。もう少し考察に時間を取ってもよさそう。

Q1 - Check Completeness of a Binary Tree (5)

TreeNode…
問題の意味読み違えてて、というかリンクが張ってあった complete binary tree の定義(Wikipedia)が理解できずに、サンプル1の左右対称な 1-23-*567 でも良いと思って1WA
なんだ1からnまで埋まってるかどうかって話じゃないの?
ノードの番号ってこれ(2n,2n+1)みたいに振ってくれてるとは限らないよね?一応自分で振り直したりして
→AC

// いろいろ略

class Solution {
    map<int,vi> w;

    void sub(TreeNode *node, int depth, int id){
        if (!node) return;
        w[depth].pb(id);
        if (node->left)
            sub(node->left, depth+1, id*2);
        if (node->right)
            sub(node->right, depth+1, id*2+1); // 1 23 4567
    }
public:
    bool isCompleteTree(TreeNode* root) {
        if (root == NULL) return false;
        sub(root, 1, 1);
        for (int depth=1,fl=1; ;++depth,fl*=2) {
            if (w[depth].empty()) break;
            if (depth>1 && w[depth-1].size()!=fl/2) return false;
            sort(ALL(w[depth]));
            int L = w[depth].size();

            if (w[depth][0] == fl && w[depth].back() == fl+L-1) continue;
            else return false;
        }
        return true;
    }
};

Q2 - Prison Cells After N Days (6)

256パターン→256パターン
256x256の行列の累乗で行けるだろ
→TLE(1)

あれ
自分の行列累乗が遅い?

試しにnumpyで書き直してみたりして
あれ計算あわない
→WA(1)

飛ばして

戻って
別に行列使うまでもない
32段ぐらいのテーブルを用意して、f,f^2,f^4,f^8,...みたいなテーブルを作ってみたいにO(NlogN)で解けるよね
(ダブリングというやつね)
最初からそうしてれば
→AC

// いろいろ略

class Solution {
    int trans(int p){
        int q = 0;
        for (int b=1,m=2; b<7; ++b,m<<=1) {
            bool left = (p & (m*2)) ? true : false;
            bool right = (p & (m/2)) ? true : false;
            if ((left && right) || (!left && !right))
                q |= m;
        }
        return q;
    }
public:
    vector<int> prisonAfterNDays(vector<int>& cells, int N) {
        #define BITS 33

        vvi mp(BITS, vi(256, 0));
        rep(p, 256) {
            int q = trans(p);
            mp[0][p] = q;
        }
        for(int b=1; b<BITS; ++b) {
            rep(p,256)
                mp[b][p] = mp[b-1][ mp[b-1][p] ];
        }

        int p=0;
        for (int i=0,m=1; i<8; ++i,m<<=1) {
            if (cells[i]) p|=m;
        }

        int q = p;
        for (int b=0,m=1; b<31; ++b,m<<=1) {
            if (!(N&m)) continue;
            q = mp[b][q];
        }

        vi ans(8, 0);
        for (int i=0,m=1; i<8; ++i,m<<=1) {
            if (q & m) ans[i] = 1;
        }

        return ans;
    }
};

Q3 - Regions Cut By Slashes (7)

1マスを東西南北的な4区画に切って
UnionFindで
→AC
これが一番楽だった

// いろいろ略

#define IJ(i,j) ((i)*W+(j))*4

class Solution {
public:
    int regionsBySlashes(vector<string>& grid) {
        int H=grid.size();
        if (H==0) return 0;
        int W=grid[0].size();
        if (W==0) return 0;

        UnionFind uf(H*W*4);

        rep(i,H)rep(j,W){
            int b = IJ(i,j);
            switch ( grid[i][j]){
                case ' ':
                    uf.unionSet(b, b+1);
                    uf.unionSet(b, b+2);
                    uf.unionSet(b, b+3);
                    break;
                case '/':
                    uf.unionSet(b, b+1);
                    uf.unionSet(b+2, b+3);
                    break;
                case '\\':
                    uf.unionSet(b, b+2);
                    uf.unionSet(b+1, b+3);
                    break;
            }
            if (i<H-1)
                uf.unionSet(b+3, IJ(i+1,j));
            if (j<W-1)
                uf.unionSet(b+2, IJ(i,j+1)+1);
        }
        set<int> s;
        rep(i,H*W*4) s.insert(uf.root(i));

        return s.size();
    }
};

Q4 - Delete Columns to Make Sorted III (7)

縦読みの文字列を作ってLISを取って幅から引く?
LISライブラリに比較関数(すべての文字を比較)を用意すれば行ける?あれうまく行かない…半順序だから?
長さ最大100って書いてあるしO(N^2)のDPでよくね?
→AC

// いろいろ略

bool cmp(const vector<char>& a, const vector<char>& b){
    int L = a.size(); assert(b.size() == L);
    rep(i,L){
        if (a[i] > b[i]) return false;
    }
    return true;
}

class Solution {
public:
    int minDeletionSize(vector<string>& A) {
        int L=A[0].size(), H=A.size();
        int d=0;

        vector<vector<char>> B(L);
        rep(i,L){
            vector<char> w(H);
            rep(c,H) w[c] = A[c][i];
            B[i] = vector<char>(ALL(w));
        }

        vi dp(L, 1);
        for (int i=1; i<L; ++i) {
            for (int j=0; j<i; ++j) {
                if (cmp(B[j], B[i])) {
                    dp[i] = max(dp[i], dp[j]+1);
                }
            }
        }
        int lis_len = *max_element(ALL(dp));
        return L - lis_len;
    }
};

*1:競プロ忘年会の開始時刻が13:30だったのにまだスタバ