naoya_t@hatenablog

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

LeetCode Weekly Contest 136

5/12(日) 11:30-13:00
とあるTully'sにて
Dを通せないまま途中離脱(3完1ペナ);
143/4109位
3完の割にひどい順位にならなかったのはQ4通した人数が少なかったから(全完92人)
それでもレートは微増:2306→2309
f:id:n4_t:20190514121829p:plain:w320
World Rankingは144 / 95530

D問題絡みでSuffix ArrayとLCPを線形時間で構築する方法を学んだ。

Q1: Robot Bounded In Circle (4)

Loading...
シミュレーション
4回やって原点に戻ってくるか
で書いたけど4回でいいのか(もっと長い周期のやつがあったりしないか)と不安になって
1024回やって原点に戻ってくるかでチェック
→AC

int dx[4] = { 1, 0, -1, 0 },
    dy[4] = { 0, 1, 0, -1 };

class Solution {
    int x,y,dir;
    
    void f(string& s){
        int L=s.size();
        rep(i,L){
            switch (s[i]){
                case 'G': x += dx[dir]; y += dy[dir]; break;
                case 'L': dir++; dir %= 4; break;
                case 'R': dir+=3; dir %= 4; break;
            }
        }
    }
public:
    bool isRobotBounded(string instructions) {
        x=y=dir=0;
        rep(i,1024) f(instructions);
        return (x == 0 && y == 0);
    }
};
他の人のコードを見る
  • 4回で終わりにしてる
    • 4回で良かったみたいだ
  • 長さ×1010回ぐらい回してる
    • わかりみ
  • 1回だけやって、原点に戻ってくるか、あるいは向きが最初と違うならtrue
    • 2回か4回で戻って来るってことか

なるほどー

Q2: Flower Planting With No Adjacent (5)

Loading...
地図の色分け。4つ以上と隣接することはないという条件で。
一旦飛ばしてQ3へ

戻って

隣りあう最大3箇所で使われてない色が必ずあるじゃん
適当にbfsして
(ガーデンが全部繋がってるとは限らないので塗っていないところから再スタート)
→AC

class Solution {
public:
    vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {
        vvi nxt(N);
        rep(i,paths.size()){
            int u=paths[i][0]-1, v=paths[i][1]-1;
            nxt[u].pb(v); nxt[v].pb(u);
        }
        vi color(N,0);
        for (int cnt=0; cnt<N; ) {
            queue<int> q;
            int first=-1;
            rep(i,N){
                if (color[i]==0) {first=i; break; }
            }
            if (first==-1) break;
            q.push(first);
            while (!q.empty()){
                int u=q.front(); q.pop();
                if (color[u]>0) continue;
                set<int> s;
                for (int v: nxt[u]){
                    if (color[v] > 0){
                        s.insert(color[v]);
                    } else {
                        q.push(v);
                    }
                }
                int c=-1;
                for(int i=1;i<=4; ++i){
                    if (!found(s,i)) { c=i; break; }
                }
                color[u] = c;
                ++cnt;
            }
        }
        return color;
    }
};
他の人のコードを見る
  • (queueとかしなくても)適当な順番に見ていくだけで良い。(色の選び方は早いもの勝ちで良い)
    • それはそう

Q3. Partition Array for Maximum Sum (6)

Loading...
はい
CなのでDP
現在位置から右にK個まで進んで、そこまでの最長を使って埋めて進む感じの†配るDP†
幅Kのmaxを取るのにセグ木を使う
最初サンプルが合わなかった:幅K決め打ちで進めていたせいだ
直して提出
→WA(1)
if (i+k > L) break; のところを if (i+K > L) で書いてた...(幅K決め打ちの時のまま)
直して
→AC
(1つずつmaxの区間を広げて見ていくってことは結局セグ木いらないよね…)

class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& A, int K) {
        int L=A.size();
        MaxSegmentTree<int> mx(A);
        
        vi dp(L+1, 0);
        for (int i=0; i<L; ++i) {
            for (int k=1; k<=K; ++k) {
                if (i+k > L) break;
                amax(dp[i+k], dp[i] + mx.query(i,i+k)*k);
            }
        }
        return dp[L];
    }
};
セグ木を使わずに書き直し

→AC

class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& A, int K) {
        int L=A.size();        
        vi dp(L+1, 0);
        for (int i=0; i<L; ++i) {
            int mx = 0;
            for (int k=1; k<=K; ++k) {
                if (i+k > L) break;
                amax(mx, A[i+k-1]);
                amax(dp[i+k], dp[i] + mx*k);
            }
        }
        return dp[L];
    }
};

Q4. Longest Duplicate Substring (8)

Loading...
N=10^5なんだけどこれどうやってTLE出さずに行けるんだ?

  • rolling hash使う?
    • 構築はO(N)だよね
    • 始点を2つ選んでそこから長さを二分探索するとしても、始点を選ぶのに_NC_2O(N^2)では
    • 【終了後】いや違う、長さを固定するとスタート地点だけ選べば良くなるのでO(N\log N)だ...

いずれにしてもきつい
とりあえずsuffix array (+LCP) を書いてみるけど
→WA(1)

デバッグ用に固定長で止めるコード入れたままだった
直して
→TLE(1)
"aaaaaaaaaaaaaaa...." みたいなやつで落ちる

13時からプランクトン・サミットに参加するのでここで離脱><

以下TLE恥コード

int cmp(const void *s1, const void *s2) {
    return strcmp(*(const char**)s1, *(const char**)s2);
}

const char *h;
int Lh;
int ever;

int match(const char* p, const char *q){
    int lp = Lh - (int)(p - h), lq = Lh - (int)(q - h);
    if (min(lp,lq) < ever) return 0;
    
    debug("match(%s %s)", p, q);
    int len=0;
    while (true) {
        if (*p=='\0' || *q=='\0' || *p != *q) break;
        ++len;
        ++p; ++q;
    }
    debug(" => %d\n", len);
    return len;
}

class Solution {
public:
    string longestDupSubstring(string S) {
        int L=S.size();
        const char *s = S.c_str();
        h = s; Lh = L;
        const char* ps[L];
        rep(i,L) ps[i] = s + i;
        qsort(ps, L, sizeof(const char*), cmp);

        int ever = 0;
        int len = -1, at = -1;
        for (int i=L-1; i>0; --i) {
            int matched = match(ps[i-1], ps[i]);
            if (matched > len) {
                len = matched; amax(ever, len);
                at = i;
            }
        }
        return string(ps[at], ps[at]+len);
    }
};
ロリハ+二分探索解

modを二通り取るいつものやつ(ハッシュ衝突予防)
→AC ※最悪ケースはローカルで1秒超

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) {
    }

    // void init(const string &s, int reserve=0) {
    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);
    }

    SIGNATURE concat(SIGNATURE h1, SIGNATURE h2, int h2_len) {
        return SIGNATURE(
            (h1.first * pow1[h2_len] + h2.first) % mod1,
            (h1.second * pow2[h2_len] + h2.second) % mod2
        );
    }
};

class Solution {
public:
    string longestDupSubstring(string S) {
        RollingHash rh;
        rh.init(S);

        int L=S.size();
        int lo=0, hi=L+1; // o x

        map<int,int> success;

        while (lo+1 < hi) {
            int mi = (lo+hi)/2;
            bool ok = false;

            map<SIGNATURE, int> mp;
            for (int i=0; i<=L-mi; ++i) {
                SIGNATURE s = rh.get(i, i+mi);
                if (++mp[s] == 2) {
                    success[mi] = i;
                    // debug("mi=%d, [%d..%d)\n", mi, i, i+mi);
                    ok = true;
                    break;
                }
            }
            if (ok) {
                lo = mi;
            } else {
                hi = mi;
            }
        }

        string ans = S.substr(success[lo], lo);
        return ans;
    }
};
Suffix Array (SA-IS) + LCPでも通るはずなので

SA-ISがO(N)、LCPもO(N)ってすごい
→AC ※最悪ケースでもローカルで数十ms

#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#include <cassert>


typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<string> vs;
typedef vector<char> vch;
typedef vector<bool> vb;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define clamp(v,lo,hi) min(max(v,lo),hi)

template <typename T>
inline bool found(set<T> &s, T elem) { return s.find(elem) != s.end(); }
template <typename T>
inline bool found(unordered_set<T> &s, T elem) { return s.find(elem) != s.end(); }
template <typename T, typename U>
inline bool found(map<T,U> &s, U elem) { return s.find(elem) != s.end(); }
template <typename T, typename U>
inline bool found(unordered_map<T,U> &s, U elem) { return s.find(elem) != s.end(); }
template <typename T>
inline bool found(vector<T> &s, T elem) { return find(s.begin(), s.end(), elem) != s.end(); }
inline int found(string &s, string t) { return (int)s.find(t); }
inline int found(string &s, int c) { return (int)s.find(c); }

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

inline ll square(ll x) { return x * x; }
inline ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }
template <typename T>
inline T mod(T a, T b) { return ((a % b) + b) % b; }

// ここから論文コードのコピペ
unsigned char mask[]={0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01};
#define tget(i) ( (t[(i)/8]&mask[(i)%8]) ? 1 : 0 )
#define tset(i, b) t[(i)/8]=(b) \
                      ?(mask[(i)%8]|t[(i)/8]) \
                      :((~mask[(i)%8])&t[(i)/8])
#define chr(i) (cs==sizeof(int) \
                      ?((int*)s)[i] \
                      :((unsigned char *)s)[i])
#define isLMS(i) (i>0 && tget(i) && !tget(i-1))
void getBuckets(unsigned char *s, int *bkt, int n, int K, int cs, bool end) {
  int i, sum=0;
  for(i=0; i<=K; i++) bkt[i]=0;
  for(i=0; i<n; i++) bkt[chr(i)]++;
  for(i=0; i<=K; i++)
  { sum+=bkt[i]; bkt[i]=end ? sum : sum-bkt[i]; }
}
void induceSAl(unsigned char *t, int *SA,
               unsigned char *s, int *bkt,
               int n, int K, int cs, bool end) {
  int i, j;
  getBuckets(s, bkt, n, K, cs, end);
  for(i=0; i<n; i++) {
    j=SA[i]-1;
    if(j>=0 && !tget(j)) SA[bkt[chr(j)]++]=j;
  }
}
void induceSAs(unsigned char *t, int *SA,
               unsigned char *s, int *bkt,
               int n, int K, int cs, bool end) {
  int i, j;
  getBuckets(s, bkt, n, K, cs, end);
  for(i=n-1; i>=0; i--) {
      j=SA[i]-1;
      if(j>=0 && tget(j)) SA[--bkt[chr(j)]]=j;
  }
}
void SA_IS(unsigned char *s, int *SA, int n, int K, int cs) {
  unsigned char t[n/8 + 1];
  int i, j;
  tset(n-2, 0); tset(n-1, 1);
  for(i=n-3; i>=0; i--)
    tset(i, (chr(i)<chr(i+1)
             || (chr(i)==chr(i+1)
             && tget(i+1)==1))?1:0);
  int bkt[K+1];
  getBuckets(s, bkt, n, K, cs, true);
  for(i=0; i<n; i++) SA[i]=-1;
  for(i=1; i<n; i++)
    if(isLMS(i)) SA[--bkt[chr(i)]]=i;
  induceSAl(t, SA, s, bkt, n, K, cs, false);
  induceSAs(t, SA, s, bkt, n, K, cs, true);
  int n1=0;
  for(i=0; i<n; i++)
    if(isLMS(SA[i])) SA[n1++]=SA[i];
  for(i=n1; i<n; i++) SA[i]=-1;
  int name=0, prev=-1;
  for(i=0; i<n1; i++) {
    int pos=SA[i]; bool diff=false;
    for(int d=0; d<n; d++)
      if(prev==-1 || chr(pos+d)!=chr(prev+d)
                  || tget(pos+d)!=tget(prev+d))
      { diff=true; break; }
      else if(d>0 && (isLMS(pos+d) ||
                      isLMS(prev+d)))
        break;
    if(diff) { name++; prev=pos; }
    pos=(pos%2==0)?pos/2:(pos-1)/2;
    SA[n1+pos]=name-1;
  }
  for(i=n-1, j=n-1; i>=n1; i--)
      if(SA[i]>=0) SA[j--]=SA[i];
  assert(n >= n1);
  int *SA1=SA, *s1=SA+n-n1;
  if (name < n1)
    SA_IS((unsigned char*)s1, SA1, n1,
          name-1, sizeof(int));
  else
    for(i=0; i<n1; i++) SA1[s1[i]] = i;
  getBuckets(s, bkt, n, K, cs, true);
  for(i=1, j=0; i<n; i++)
    if(isLMS(i)) s1[j++]=i;
  for(i=0; i<n1; i++) SA1[i]=s1[SA1[i]];
  for(i=n1; i<n; i++) SA[i]=-1;
  for(i=n1-1; i>=0; i--) {
      j=SA[i]; SA[i]=-1;
      SA[--bkt[chr(j)]]=j;
  }
  induceSAl(t, SA, s, bkt, n, K, cs, false);
  induceSAs(t, SA, s, bkt, n, K, cs, true);
}
// ここまでコピペ

vector<int> SA_IS(string& S) {
    int L = S.size();
    vector<int> SA(L+1);
    SA_IS((unsigned char*)S.c_str(), &SA[0], L+1, 256, 1);
    return SA;
}

vector<int> LCP(string& S, vector<int>& sa) { // 笠井法
    int L = S.size() + 1;
    const char *s = S.c_str();

    vi rsa(L);
    rep(i,L) rsa[sa[i]] = i;

    vi height(L); int h=0;
    rep(i,L){
        if (rsa[i] == L-1) {
            height[rsa[i]] = -1;
            h = 0;
        } else {
            int ofs = max(0, h-1);
            const char *p = s+ofs+i, *q = s+ofs+sa[rsa[i]+1];
            int lcp = 0;
            while (true) {
                if (*p==0 || *q==0 || *p != *q) break;
                ++lcp; ++p; ++q;
            }
            height[rsa[i]] = h = ofs + lcp;
        }
    }
    return height;
}

class Solution {
public:
    string longestDupSubstring(string S) {
        vi sa = SA_IS(S);
        vi height = LCP(S, sa);

        int ix = (int)(max_element(ALL(height)) - height.begin());
        int len = height[ix];
        return S.substr(sa[ix], len);
    }
};