naoya_t@hatenablog

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

LeetCode Weekly Contest 114

12/9(日) 11:30 - 13:00
3完 114/3198位
(全完が86人いる)

【12/11追記】レート上がってた
f:id:n4_t:20181212065042p:plain:w380
f:id:n4_t:20181212065126p:plain:w450

Q1 - Verifying an Alien Dictionary (4)

ペコポンのアルファベットにマッピングして、隣接するもの同士を比較して
→AC 7:24

// いろいろ略
class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        map<char,char> m;
        rep(i,26) {
            m[order[i]] = (char)('a' + i);
        }
        int L = words.size();
        vector<string> x(L);
        rep(i,L) {
            int W = words[i].size();
            vector<char> tmp(W);
            rep(j,W) tmp[j] = m[ words[i][j] ];
            x[i] = string(ALL(tmp));
            if (i == 0) continue;
            if (x[i-1] > x[i]) return false;
        }
        return true;
    }
};

Q2 - Array of Doubled Pairs (5)

小さい方からgreedyに取っていけばよさそう?
正負(とゼロと)分けたほうがいいな
デバッグ手間取ったけど
→AC 21:05

// いろいろ略
class Solution {
public:
    bool canReorderDoubled(vector<int>& A) {
        int L = A.size();

        map<int,int> pos, neg;
        int posc=0, negc=0, zeroc=0;

        rep(i,L) {
            if (A[i] == 0) { zeroc++; }
            else if (A[i] > 0) { pos[A[i]]++; posc++; }
            else { neg[-A[i]]++; negc++; }
        }
        if (zeroc % 2) return false;

        for (ii p: pos) {
            int n=p.first, ct=p.second;
            if (ct == 0) continue;
            if (!found(pos, n*2)) return false;
            if (pos[n*2] < ct) return false;
            pos[n] -= ct;
            pos[n*2] -= ct;
            posc -= ct*2;
        }

        if (posc) return false;

        for (ii p: neg) {
            int n=p.first, ct=p.second;
            if (ct == 0) continue;
            if (!found(neg, n*2)) return false;
            if (neg[n*2] < ct) return false;
            neg[n] -= ct;
            neg[n*2] -= ct;
            negc -= ct*2;
        }

        if (negc) return false;

        return true;
    }
};

Q3 - Delete Columns to Make Sorted II (6)

1文字目から順に、消してもいいか調べていくんだけど
残す場合に、隣り(上下)同士が=なのか<なのかを記録しておく。<の箇所はそれより右の比較が不要。
→AC 31:38

// いろいろ略
class Solution {
public:
    int minDeletionSize(vector<string>& A) {
        int L = A.size(), W = A[0].size();
        vi med(L-1, 0);
        int D = 0;
        rep(c,W) {
            bool bad = false;
            rep(i,L-1) {
                if (med[i] == 1) continue;
                if (A[i][c] > A[i+1][c]) { bad = true; break; }
            }
            if (bad) {
                ++D;
                continue;
            }
            rep(i,L-1) {
                if (med[i] == 1) continue;
                if (A[i][c] < A[i+1][c]) { med[i] = 1; continue; }
            }
        }
        return D;
    }
};

Q4 - Tallest Billboard (8)

  • 全パターン(P=2^20通り)について長さを計算し、長さごとにパターンを束ねておく
  • ある長さについて、ペアリングできるパターンが1つでもあればtrue
    • 論理andが0になればいいんだけど
    • いやこれだと全部比較してO(P^2)で死ねるのでは
  • ある長さについて、それの2倍の長さのパターン群に「含まれている」ものがあればいいのか
    • 含まれているっていっても同じパターンではなくパターンの部分集合として含まれているわけで単純には比較できない(2倍のほうと等倍のほうの論理andが等倍のほうになればいい)
    • それでも最悪O(P^2)のオーダーかかるか?
  • 最悪ケースって合計が同じになるパターン数が多いやつだと思うけどどういうの?[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]みたいな?
    • ローカルでは大丈夫そうなんだけど
    • judgeでTLE
// 提出したTLE解。いろいろ略
class Solution {
    bool contains(vi& s2, vi& s1) {
        if (s2.empty() || s1.empty()) return false;
        for (int x2: s2) {
            int L=s1.size();
            rep(i,L/2){
                int x1 = s1[i];
                if ((x2 & x1) == x1) return true;
            }
        }
        return false;
    }

public:
    int tallestBillboard(vector<int>& rods) {
        int L = rods.size();
        int P = 1 << L;

        vvi sums(5001);
        for (int p=1; p<P; ++p) { // 1e6
            int s = 0;
            for (int b=0,m=1; b<L; ++b,m<<=1) {
                if (p&m) s += rods[b];
            }
            sums[s].pb(p);
        }

        for (int s=2500; s>0; --s) {
            if (contains(sums[s*2], sums[s])) return s;
        }

        return 0;
    }
};

解説読んだ

Tallest Billboard - LeetCode Articles
なるほどDP
±a_iが使える(あるいは使わなくても良い)として合計が0になるパターンがあるか(あるとしたら正負それぞれ最大いくつずつか)、を2次元DP(位置:たかだか20、和:たかだか2500?)で求めている。それは速そうだ。
→WA(1)
なるほど、ジグザグに進んで0にたどり着くこともあるので正だけ見ていればいいわけじゃない。
和の範囲は±5000まで行く(有効なのは±2500の範囲だと思うけれど)のでそれだけの幅があれば余計な条件分岐もしなくて済む。

// AC解。いろいろ略
class Solution {
public:
    int tallestBillboard(vector<int>& rods) {
        int L = rods.size();
        int H = 5000;
        vi dp(H+1+H, INT_MIN);
        dp[H] = 0;

        for (int i=L-1; i>=0; --i) {
            int R = rods[i];
            vi dp2 = dp;
            rep(j,H+1+H) {
                dp2[j] = max(dp2[j], dp[j-R]);
                // dp2[j] = max(dp2[j], dp[j]);
                dp2[j] = max(dp2[j], R+dp[j+R]);
            }
            dp = dp2;
        }
        return dp[H];
    }
};