naoya_t@hatenablog

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

LeetCode Weekly Contest 137

5/19(日) 11:30-13:00

4完ノーペナで102/4091位
ノーペナは嬉しい(ちょっと慎重になりすぎて遅かったかも)

レート微増 (2309→2313)
f:id:n4_t:20190520200328p:plain:w320

Q1 - Last Stone Weight (3)

  • priority_queueを使ってシミュレーション

→AC 4:00

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        int L=stones.size();
        priority_queue<int> pq;
        rep(i,L) pq.push(stones[i]);
        while (L >= 2) {
            int a=pq.top(); pq.pop();
            int b=pq.top(); pq.pop();
            L -= 2;
            if (a==b) continue;
            pq.push(abs(a-b)); ++L;
        }
        if (pq.empty()) return 0;
        else return pq.top();
    }
};

Q2 - Remove All Adjacent Duplicates In String (4)

スタックに積んで、トップと同じなら食っていけばいい
(といいつつ最後に残りから復元したいのでdequeで書いた)
→AC 13:57

class Solution {
public:
    string removeDuplicates(string S) {
        int L=S.size();
        if (L < 2) return S;
        // L >= 2

        deque<char> st; int n=0;
        rep(i,L){
            char c = S[i];
            if (st.empty()) {
                st.push_back(c);
            } else {
                if (st.back() == c) st.pop_back();
                else st.push_back(c);
            }
        }

        vector<char> tmp;
        while (!st.empty()){
            tmp.pb(st.front()); st.pop_front();
        }
        return string(ALL(tmp));
        
    }
};

Q3 - Longest String Chain (6)

  • 単語のペアごとに predecessor 関係かを調べて有向グラフを構築
  • 最大の深さをDPなりメモ化再帰なりで

→AC 27:00

class Solution {
    vvi nxt;
    bool is_predecessor(string& s, string& t){
        int S=s.size(), T=t.size();
        if (S+1 != T) return false;

        int left=0, right=0;
        for (int i=0; i<S; ++i) {
            if (s[i] == t[i]) ++left;
            else break;
        }
        for (int i=S-1; i>=0; --i) {
            if (s[i] == t[1+i]) ++right;
            else break;
        }
        return (left + right >= S);
    }
    vi memo;
    int dfs(int u){
        if (memo[u] != INT_MAX) return memo[u];
        int best = 1;
        for (int v: nxt[u]){
            amax(best, 1+dfs(v));
        }
        return memo[u]=best;
    }
public:
    int longestStrChain(vector<string>& words) {
        int L=words.size();

        nxt.resize(L);
        memo.assign(L, INT_MAX);
        
        repC2(i,j,L){
            if (is_predecessor(words[i], words[j])){
                nxt[i].pb(j);
            }
            if (is_predecessor(words[j], words[i])){
                nxt[j].pb(i);
            }
        }
        
        int best = 0;
        rep(i,L){
            amax(best, dfs(i));
        }
        return best;
    }
};

Q4 - Last Stone Weight II (9)

  • priority_queueにつっこんで貪欲に上位2つを衝突させていくやつを書いた
    • 要するにQ1と同じ
  • naiveに全通り試すマシーンを作ってテスト
int naive(vi& stones){
    int L=stones.size();
    if (L==0) return 0;
    if (L==1) return stones[0];

    int best = INT_MAX;
    vi tmp; tmp.reserve(L);
    repC2(i,j,L){
        tmp.clear();
        rep(k,L){
            if (k==i || k==j) continue;
            tmp.pb(stones[k]);
        }
        if (stones[i]!=stones[j])
            tmp.pb(abs(stones[j] - stones[i]));
        amin(best, naive(tmp));
    }
    return best;
}
  • 答えが時々合わない。[10,7,1,7,7,2,9,1] とか 0 になってほしいのにならない。
  • うまくいくパターンってどうなってるんだろう、とノートで考察
  • 最後から逆に辿ってみよう
  • 例えば [9,6,5,3,1]→[6,4,3,1]→[3,4,1]→[1,1]→[0] の過程
  • 違う長さの棒を重ね合わせると、共通部分だけ消える感じで
  • 逆に辿って、消えた部分を復活させていくと
  • (9,3), (6,5,1) の2組に分かれて、それぞれの合計が12で等しい
  • 【ひらめいた】合計が同じにできれば0になるのでは?
  • というか、2組に分けたときのそれぞれの合計の差の最小値がこの問題の答えなのでは
  • naiveマシーンの結果と一致する!
  • 投げてみよう

→AC 1:04:47
わーい

template<class T> inline void amin(T & a, T const & b) { a = min(a, b); }

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int L=stones.size();
        int sm = accumulate(ALL(stones), 0);

        vector<bitset<3001>> dp(1+L, bitset<3001>());
        dp[0].set(0, true);

        int acc = 0;
        rep(i,L){
            int si = stones[i];
            for(int j=0; j<=acc; ++j) {
                if (!dp[i].test(j)) continue;
                dp[i+1].set(j, true);
                dp[i+1].set(j+si, true);
            }
            acc += si;
        }
        int best = sm;
        for (int j=0; j<=acc; ++j){
            if (!dp[L].test(j)) continue;
            int diff = abs(j - (sm-j));
            amin(best, diff);
        }
        return best;
    }
};