naoya_t@hatenablog

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

LeetCode Weekly Contest 112

11/25(日) 11:30-13:00
leetcode.com

3回目の参加。
全完(1-2-4-3の順で解いた)170/3195位
(※13時から予定があるのを失念して全完に浮かれていた)

レーティング チョット アガリマシタ (2122→2175)
f:id:n4_t:20181127130119p:plain:w480

Q1 (5)

  • ソートして
  • 小さい方から少なくとも1ずつインクリメントした坂道にしていく
    • 11223 なら 12345
    • 11288 なら 12389

→RE
あ、長さ0のケースを考慮してなかった。1ペナ><
直して
→AC 11:10

// マクロ略
class Solution {
public:
    int minIncrementForUnique(vector<int>& A) {
        int ans = 0;
        int L = A.size();
        if (L == 0) return 0;
        sort(ALL(A));
        int tobe = A[0];
        rep(i,L){
            if (A[i] >= tobe) {
                tobe = A[i]+1;
            } else {
                ans += tobe - A[i];
                ++tobe;
            }
        }
        return ans;
    }
};

Q2 (6)

スタックの先頭にお目当ての数があればpopする、さもなければpushする
それでお目当て全部取れればtrue
→AC 23:21

// マクロ略
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int L = pushed.size();
        if (L == 0) return true;

        stack<int> s;
        for (int i=0,j=0; j<L; ) {
            if (!s.empty() && s.top() == popped[j]) {
                s.pop();
                ++j;
                continue;
            }
            if (i < L) {
                s.push(pushed[i++]);
            } else {
                return false;
            }
        }
        return true;
    }
};

Q3 (6)

なんか問題の(入力の)意味わからない。2次元空間なのになんで2xWみたいな入力なの?
あと、誤植があった的なアナウンスがあって、リロードしたら数字が書き換わった。
パス

Q4を終えて戻ってきて(残り15分…行けるか?)

あ、x-y座標が点の個数分並んでるだけか
ノートにプロットしてみて把握

  • UnionFindして、グループごとに考えればよさそう
  • 島ごとの全域木の葉から取っていけばよいのでは?
    • 1つの島につき1つどうしても取れない(最後まで残る)やつが出来るよね
  • てことは、点の個数 - 島の数、が答えなんじゃないかな

(時間ないし)ローカルでテストせずWeb UIでRun codeして(サンプルケースも2つ試しただけで)submit
→AC 1:24:02
間に合った!(8分で解けた!)

// マクロとかUnionFindとか略
class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        int L=stones.size();
        UnionFind uf(L);
        vvi xs(10001), ys(10001);
        rep(i,L){
            int x=stones[i][0], y=stones[i][1];
            xs[x].pb(i);
            ys[y].pb(i);
        }
        rep(x,10000){
            if(xs[x].size()==0)continue;
            int i0=xs[x][0];
            for(int i:xs[x]){
                if(i==i0) continue;
                uf.unionSet(i0, i);
            }
        }
        rep(y,10000){
            if(ys[y].size()==0)continue;
            int i0=ys[y][0];
            for(int i:ys[y]){
                if(i==i0) continue;
                uf.unionSet(i0, i);
            }
        }
        set<int> rs;
        rep(i,L) {
            rs.insert(uf.root(i));
        }
        return L - rs.size();
    }
};

Q4 (6)

  • 一番小さいのでポイントをゲットして、一番大きいのでポイントを犠牲にパワーを増やして、みたいなのを貪欲に繰り返す
  • 一番大きいのでパワーを増やす代わりに、残りパワーで取れるだけポイントを取ったらどうなるかも見る

みたいなことをするだけのコードがすんなり書けなくて焦りながら50分ぐらいデバッグしてた…(10分で解けるはずの問題)
upper_bound()の終点が1つ手前になっていて、見つけてほしいやつを見つけてもらえていなかった。累積和に対してlower_bound/upper_boundをするときには適当にコードいじるんじゃなくてちゃんとノートで考察したほうがいいかも。
→AC 1:15:50
まだ2問しか解いてないのにもう終わりか…(と思ったらあと30分あった;そこから全完まで持って行けたのは奇跡)

// マクロ略
class Solution {
public:
    int bagOfTokensScore(vector<int>& tokens, int P) {
        sort(ALL(tokens));
        int L = tokens.size();
        vi acc(L+1, 0);
        rep(i,L) acc[i+1] = acc[i] + tokens[i];

        int pts = 0, best = 0;
        for (int i=0,j=L; i<j; ) {
            best = max(best, pts);
            if (P < tokens[i]) {
                // もう使えない
                break;
            }
            // use token
            P -= tokens[i++];
            pts++;
            best = max(best, pts);

            int ix = (int)(lower_bound(acc.begin(), acc.begin()+j+1, acc[i]+P+1) - acc.begin()); /// ここでずっとトラブってた
            if (ix-1 > i) {
                int u = ix-1 - i;
                best = max(best, pts + u);
            }
            // use point to gain power
            assert(pts>0);
            P += tokens[--j];
            pts--;
        }
        return best;
    }
};