naoya_t@hatenablog

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

LeetCode Weekly Contest 133

4/21(日) 11:30-13:00

4完2ペナで232/4860位
2ペナきついけど勉強になった

Q1.マンハッタン距離で昇順ソートする
Q2.なんだこれEasyなのにDPか
Q3.全区間重ならせずに試すだけ 先に累積和を取っておく
Q4.Trie木に逆に登録しておいてクエリ履歴をあてはめてみる

レートは微減(2331→2330)
f:id:n4_t:20190423110530p:plain:w320
Rankingは109(/93401)位のままだった

Q1 - 1030. Matrix Cells in Distance Order (4)

マンハッタン距離で昇順ソートする
→AC 03:54

class Solution {
public:
    vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {
        vector<pair<int,vi>> tmp;
        rep(r,R) rep(c,C){
            int d = abs(r0-r) + abs(c0-c);
            tmp.emplace_back(d, vi{r,c});
        }
        sort(ALL(tmp));
        vvi ans;
        for(auto& p: tmp) {
            ans.pb(p.second);
        }
        return ans;
    }
};

Q2 - 1029. Two City Scheduling (4)

???
なにこれEasyなの?
前に見たa+bだかa-bだかでソートしてやるやつっぽくも見えるけど
一旦パス

戻って
DPを書いて

  • dp[どこまで][cityBの人数]=最小コスト

の dp[2N][N] が答え
→AC 18:01

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        int L=costs.size(), N=L/2;
        vvi dp(L+1, vi(L+1, INT_MAX));
        dp[0][0] = 0;
        rep(i,L){
            rep(j,L){
                if (dp[i][j] == INT_MAX) continue;
                amin(dp[i+1][j], dp[i][j] + costs[i][0]);
                amin(dp[i+1][j+1], dp[i][j] + costs[i][1]);
            }
        }
        return dp[L][N];
    }
};
後で(a-bでソートする方式)

入力を (a_i, b_i), i=[0,2N) 、A市に行く集合をS、B市に行く集合をT(|S|=|T|=N)とするとき

  • \displaystyle X=\sum_{i\in S} a_i + \sum_{i\in T} b_i

を最小化する問題なのだけれど

  • \displaystyle X=\sum_{i\in S} a_i + \sum_{i\in T} b_i = \sum_{i\in S,T}a_i - \sum_{i\in T}(a_i-b_i)

で、\displaystyle\sum_{i\in S,T}a_i の部分はS/Tの選び方によらず一定なので、Xを最小化するには第2項 \displaystyle\sum_{i\in T}(a_i-b_i)を最大化すればよい。
従って、a_i-b_iを降順に並べて大きい方からN個の和を、\displaystyle\sum_{i\in S,T}a_i から引いたのが答え。
(第2項を\displaystyle ... + \sum_{i\in T}(b_i-a_i) にして小さい方からN個の和を足す、でも同様)
→AC

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        int L=costs.size(), N=L/2;

        ll asum = 0;
        vi diffs(L);

        rep(i,L) {
            asum += costs[i][0];
            diffs[i] = costs[i][0] - costs[i][1];
        }
        sort(ALL(diffs), greater<int>());

        rep(i,N){
            asum -= diffs[i];
        }
        return asum;
    }
};

Q3 - 1031. Maximum Sum of Two Non-Overlapping Subarrays (6)

(あ、さっきのQ2ってDPで解けるじゃん)

  • 全箇所試す(区間が重複するやつは排除)
  • あらかじめ累積和をとっておく

→AC 14:15

template <typename T1, typename T2>
vector<T2> accum(vector<T1>& a, T2 init) {
    int L = a.size();
    vector<T2> acc(L + 1);
    acc[0] = init;
    for (int i=0; i<L; ++i) acc[i+1] = acc[i] + a[i];
    // partial_sum(ALL(a), acc.begin()+1);
    return move(acc);
}

template <typename T>
T accumed(vector<T>& acc, int from, int to) {
    // [from, to)
    int M = acc.size() - 1;
    return acc[min(M, to)] - acc[max(0, from)];
}

class Solution {
public:
    int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {
        int N=A.size();
        vi b=accum(A, 0);
        
        int best=0;
        for(int i0=0,i1=L; i0<=N-L; ++i0,++i1){ // [i0,i1)
            for(int j0=0,j1=M; j0<=N-M; ++j0,++j1){ // [j0,j1)
                if (i0<j0){
                    if (i1 > j0) continue;
                } else if (i0==j0) {
                    continue;
                } else {//j0<i0
                    if (j1 > i0) continue;
                }
                int sc = accumed(b,i0,i1) + accumed(b,j0,j1);
                amax(best, sc);
            }
        }
        return best;
    }
};

Q4 - 1032. Stream of Characters (7)

全単語を逆さにtrieに突っ込んでおいて
クエリ履歴を逆さにtrieにあてはめる
→TLE(1)
(この時点でまだ50位台。すぐに直して通せれば100位に入れる可能性あるかも)

mapじゃなくてunordered_mapにした方がいい?(→ローカルで大差なし)
TLEケース、1000msもかかってないんだけど
制約きついなこれ

あるいはvectorにしたらどうだ?
→TLE(2)

ロリハで書いてみるか
→書けたけどheapメモリが足りないとか言われる(なんで?)

元の実装に戻って
もしかして、クエリ履歴を逆さにした配列の準備(コピー)にかかってるO(NQ)が重い?
(2000字コピー × 40000回で8\cdot 10^7だもんね)
クエリ履歴そのものを(コピーせずに)trieに渡そう
→200ms台になった><
→AC 1:04:04
2ペナきつい

class TrieNode {
    unordered_map<char, TrieNode*> children;
    bool has_end;
 public:
    TrieNode() {
        has_end = false;
    }
    ~TrieNode() {
        for (auto p : children) {
            if (p.second != NULL) delete p.second;
        }
    }
 public:
    void add(string& s, int ofs=0) {
        if (ofs == s.size()) {
            has_end = true;
            return;
        }
        if (!goes(s[ofs]))
            children[s[ofs]] = new TrieNode();
        children[s[ofs]]->add(s, ofs+1);
    }
    TrieNode* go(char c) {
        return goes(c) ? children[c] : NULL;
    }
    bool goes(char c) {
        return children.find(c) != children.end();
    }
    bool ends() {
        return has_end;
    }
    bool has(vector<char>& s, int ofs, bool perfect) {
        if (has_end) return true;
        if (ofs == 0) {
            return has_end;
        }
        return goes(s[ofs-1]) ? children[s[ofs-1]]->has(s, ofs-1, perfect) : false;
    }
};

class Trie {
 public:
    TrieNode* root;
 public:
    Trie(set<string>& s_set) {
        root = new TrieNode();
        for (string s : s_set) root->add(s, 0);
    }
    Trie(vector<string>& s_set) {
        root = new TrieNode();
        for (string s : s_set) root->add(s, 0);
    }
    ~Trie() {
        delete root;
    }
 public:
    bool has(vector<char>& h, int ofs, bool perfect=false) {
        return root->has(h, ofs, perfect);
    }
};

class StreamChecker {
    Trie* trie;
    vector<char> history;
public:
    StreamChecker(vector<string>& words) {
        int W= words.size();
        rep(i,W) reverse(ALL(words[i]));

        trie = new Trie(words);
        history.clear();
    }
    ~StreamChecker() {
        delete trie;
    }
    
    bool query(char letter) {
        history.pb(letter);
        return trie->has(history, (int)history.size());
    }
};
後で

逆さにしなくても、Trie探索のカーソルを高々2000個持っておいて、1字ずつ進めていけば済むのでは
→AC

struct Trie {
    bool end;
    Trie* nxt[26];
    Trie() {
        end = false;
        fill(nxt, nxt+26, (Trie*)NULL);
    };
    ~Trie() {
        rep(i,26) if (nxt[i]) delete nxt[i];
    }
};

Trie *buildTrie(vector<string>& words) {
    Trie *root = new Trie();
    for (string &word: words) {
        Trie *cur = root;
        for (char &ci: word) {
            int id = ci - 'a';
            if (!cur->nxt[id]) cur->nxt[id] = new Trie();
            cur = cur->nxt[id];
        }
        cur->end = true;
    }
    return root;
}

class StreamChecker {
    Trie* root;
    vector<Trie*> cursors;
public:
    StreamChecker(vector<string>& words) {
        int W = words.size();
        root = buildTrie(words);
        cursors.push_back(root);
    }
    ~StreamChecker() {
        delete root;
    }

    bool query(char letter) {
        int id = letter - 'a';
        vector<Trie*> tmp;
        // cerr << cursors << letter << endl;
        bool accepted = false;
        for (Trie* v : cursors) {
            v = v->nxt[id];
            if (!v) continue;
            tmp.push_back(v);
            if (v->end) accepted = true;
        }
        cursors.assign(ALL(tmp));
        cursors.push_back(root);
        return accepted;
    }
};
あるいは、Aho-Corasick法で解ける?

失敗した時の行き先 = 最長suffix を用意しておくやつね
Spaghetti SourceのAho-Corasickをペタッと貼ってこねてみる)
一見うまく行きそうなんだけど

  • 辞書が { ab, ba, aaab, abab, baa }
  • aaaaabab

のとき、6文字目で "aaab" が発見された後の入力 a に対し、aaab+a は無い → aab+a は無い → ab+a はある!ので aba に行ってしまって "ba" が拾えない。
かといって ba に行くようにしてしまうとその次の abab が拾えないのでは?(たまたまabもあるからそちらで引っかかるけど)
(複数カーソルを持たせるなら Aho-Corasickでなくてもよさそう?)

beet先生のAho-Corasickコードを見てる


パターンマッチングautomatonを作る時にあらかじめ、そこからrootまでfailureしていった先のどこかでendがあるかを見ておけば良いのか...
node->acceptable みたいな bool 値を持たせて、node->failure->acceptable == true の時に node->acceptable を true で上書きするようにすればよさそう
→AC

class PMA {
 public:
    vector<PMA*> _next;
    PMA* failure;
    vector<int> accept;
    bool acceptable;
    int lo, hi;
    int node_id;
 public:
    PMA(int lo='a', int hi='z') // [lo, hi]
        : lo(lo), hi(hi), _next(hi-lo+1, NULL), failure(NULL), acceptable(false) {}

    PMA* next(int ch) {
        return _next[ch - lo];
    }
};

PMA *buildPMA(vector<string>& patterns) {
    int lo='a', hi='z';

    PMA *root = new PMA(lo,hi);
    // make trie
    for (int i=0; i<patterns.size(); ++i) {
        PMA *t = root;
        for (char& c: patterns[i]) {
            if (t->next(c) == NULL)
                t->_next[c - lo] = new PMA(lo,hi);
            t = t->next(c);
        }
        t->accept.push_back(i);
        t->acceptable = true;
    }

    queue<PMA*> Q; // make failure link using bfs
    for (int c='a'; c<='z'; ++c) {
        if (root->next(c)) {
            root->next(c)->failure = root;
            Q.push(root->next(c));
        }
        else root->_next[c - lo] = root;
    }

    while (!Q.empty()) {
        PMA *t = Q.front(); Q.pop();
        for (int c='a'; c<='z'; ++c) {
            // t->accept.insert(t->accept.end(), ALL(t->failure->accept));
            if (t->failure->acceptable) t->acceptable = true;
            if (t->next(c)) {
                Q.push(t->next(c));
                PMA *r = t->failure;
                while (!r->next(c)) r = r->failure;
                t->next(c)->failure = r->next(c);
            }
        }
    }
    return root;
}

int match(string& t, PMA *v, int *result) {
    int count = 0;
    for (char& c: t){
        while (!v->next(c)) v = v->failure;
        v = v->next(c);
        for (int j=0; j<v->accept.size(); ++j)
            result[v->accept[j]]++;
    }
    return count;
}

class StreamChecker {
    PMA *pma, *v;
public:
    StreamChecker(vector<string>& words) {
        v = pma = buildPMA(words);
    }
    ~StreamChecker() {
        delete pma;
    }

    bool query(char letter) {
        while (!v->next(letter)) v = v->failure;
        v = v->next(letter);
        // return (v->accept.size() > 0);
        return v->acceptable;
    }
};
ロリハでも書いてみたけど…

ローリングハッシュで解けそうな気がすると思って
コンテスト中に書きかけたやつを完成させてみたけど
最悪ケースでTLEが止まらない

typedef pair<ll,ll> SIGNATURE;

struct RollingHash {
    int base1, base2;
    ll mod1, mod2;
    vector<ll> hash1, hash2;
    vector<ll> pow1, pow2;
    int length;

    RollingHash() : base1(500009), base2(500029), mod1(1000000007), mod2(1000000009) {
        hash1.reserve(40001);
        hash2.reserve(40001);
        pow1.reserve(40001);
        pow2.reserve(40001);
    }

    void init(const string &s) {
        length = s.size();

        hash1.assign(length+1, 0);
        hash2.assign(length+1, 0);
        pow1.assign(length+1, 1);
        pow2.assign(length+1, 1);

        for (int i=0; i<length; ++i) {
            hash1[i+1] = (hash1[i] + s[i]) * base1 % mod1;
            hash2[i+1] = (hash2[i] + s[i]) * base2 % mod2;
            pow1[i+1] = pow1[i] * base1 % mod1;
            pow2[i+1] = pow2[i] * base2 % mod2;
        }
    }

    void append(int ch){
        hash1.pb( (hash1[length] + ch) * base1 % mod1 );
        hash2.pb( (hash2[length] + ch) * base2 % mod2 );
        pow1.pb( pow1[length] * base1 % mod1 );
        pow2.pb( pow2[length] * base2 % mod2 );
        ++length;
    }

    SIGNATURE get(int l,int r) {
        ll t1 = ((hash1[r] - hash1[l] * pow1[r-l]) % mod1 + mod1) % mod1;
        ll t2 = ((hash2[r] - hash2[l] * pow2[r-l]) % mod2 + mod2) % mod2;
        return SIGNATURE(t1, t2);
    }
};

class StreamChecker {
    RollingHash rh;
    unordered_map<int, set<SIGNATURE>> words_rh;
public:
    StreamChecker(vector<string>& words) {
        for (string& word: words) {
            rh.init(word);
            int word_len = word.size();
            SIGNATURE p = rh.get(0, word_len);
            words_rh[word_len].insert(p);
        }
        rh.init("");
    }

    bool query(char letter) {
        rh.append(letter);

        for (auto& p: words_rh) {
            int word_len = p.first;
            if (word_len <= rh.length) {
                SIGNATURE g = rh.get(rh.length-word_len, rh.length);
                if (found(p.second, g)) return true;
            }
        }
        return false;
    }
};