naoya_t@hatenablog

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

LeetCode Weekly Contest 111

ARCの700点問題を1問(ARC 094 F)埋めて、ブログエントリを下書きして、ふとTLを見たらLeetCodeがちょうどこれから始まるらしい。(11:25am前後)
あれ?今日も11:30〜なのか?
というわけで開始4分前ぐらいにれじった
leetcode.com
11/18(日) 11:30-13:00 JST

Q4のデバッグが終わらず3完><
12点で375/3585位
(そしてレーティングの変更まで数日かかるのがLeetCode)

追記11/22: レーティング チョット アガリマシタ

f:id:n4_t:20181122140800p:plain:w448

Q1 - Valid Mountain Array (3)

→WA(1)
山頂が端に来ても許容するミス

直して
→AC

class Solution {
public:
    bool validMountainArray(vector<int>& A) {
        int L = A.size();
        if (L < 3) return false;
        int left = 0, right = 0;
        for (int i=0; i<L-1; ++i) {
            if (A[i] >= A[i+1]) break;
            left++;
        }
        if (left == 0) return false;  // これ忘れてた
        for (int i=L-1; i>0; --i) {
            if (A[i] >= A[i-1]) break;
            right++;
        }
        if (right == 0) return false;  // これ忘れてた
        return (left + right == L-1);
    }
};

Q2 - Delete Columns to Make Sorted (4)

問題をふんふんと読んで実装してみて
case1は0なんだけどなんでdelete要るの?
ってよく見たらcolumn毎
はい(問題を難しくしていました)
→AC

class Solution {
    bool is_ordered(vector<string>& A, int c) {
        int N = A.size();
        for (int i=0; i<N-1; ++i){
            if (A[i][c] > A[i+1][c]) return false;
        }
        return true;
    }
public:
    int minDeletionSize(vector<string>& A) {
        int N = A.size(), L = A[0].size();

        int cnt = 0;

        for(int j=0; j<L; ++j) {
            if (!is_ordered(A,j)) ++cnt;
        }
        return cnt;
    }
};

Q3 - DI String Match (5)

えっと
仮に先頭を0として、

  • Iのとき現在の値より大きい(既出でない)値
  • Dのとき現在の値より小さい(既出でない)値

という風に繋げて行って、あとで [0,N-1] の範囲になるように座標圧縮というか -dec だけシフトすれば良いのでは
(いやそれじゃ簡単すぎない?罠ありそうじゃん?でもどうせペナルティ5分だから出しとくか)
→AC

class Solution {
public:
    vector<int> diStringMatch(string S) {
        int N = S.size()+1;
        vector<int> tmp(N, 0);
        int inc = 0, dec = 0;
        for (int i=0; i<N-1; ++i){
            if (S[i] == 'I') {
                tmp[1+i] = ++inc;
            } else {
                tmp[1+i] = --dec;
            }
        }
        for (int i=0; i<N; ++i) tmp[i] -= dec;
        return tmp;
    }
};

Q4 - Find the Shortest Superstring (8)

問題をぱっと見てRosalindぽいなあと思った。
サンプルケース2番とかほんとそれっぽい。

文字列12本だし、全探索は無理だけどなんか適当にDP (bitDP)とかで解けるかな?

謎のSEGVを連発してデバッグに苦しんで終わった。
dijkstra改造して書いてたんだけど、用意していたvisitedの配列の長さが足りてなかった。

終了後

もうちょいシンプルに(最初から)書き直す
というかちゃんとbitDPで。(マクロとか別に使ってもいいんだよな…なんか使わずに頑張ってたけど)

  • bitパターンはN=12なので4096通り
    • 短い順とか気にせず、bitパターンを0から2^N-1までなめていけばいい(topologicalな順序になっているので)
  • 最後にどれを使ったかだけでいい。(あるAiがあるAjのsubstringであったりしない制約があるので、overwrapは必ず最後に追加したAiの後半で起こり、Aiをまたいでそれ以前に噛むことはない)
    • 最後にどれを使って、次にどれを足すか、のN×N通りのoverwrapをあらかじめ求めておけば捗る
      • 前がこれの場合にこれを足したらこのsubstring、みたいなのも求めておいてもいいのかもしれない
    • 全体の計算量はO(2^N N^2) に文字列処理分を掛けた感じ

→AC

typedef long long ll;
typedef long double Double;
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<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#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 found(s,e)  ((s).find(e)!=(s).end())
#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 cons make_pair



class Solution {
    int wrap(string& a, string& b){
        int al=a.size(), bl=b.size(), lmin=min(al,bl);
        for (int l=lmin; l>0; --l){
            bool good = true;
            rep(i,l){
                // assert(IN(al-l+i, 0, al-1) && IN(i,0,bl-1));
                if (a[al-l+i] != b[i]) { good = false; break; }
            }
            if (good) return l;
        }
        return 0;
    }
public:
    string shortestSuperstring(vector<string>& A) {
        int N=A.size();
        if (N == 1) return A[0];

        int P = 1 << N;
        vvi dp(P, vi(N, INT_MAX));
        vector<vector<string>> dps(P, vector<string>(N, ""));

        vvi w(N, vi(N));
        rep(i,N) rep(j,N) w[i][j] = wrap(A[i], A[j]);

        rep(i,N) {
            // dp[0][i] = 0;
            // dps[0][i] = "";
            dp[1<<i][i] = A[i].size();
            dps[1<<i][i] = A[i];
        }
        for (int pat=1; pat<P; ++pat) {
            rep(i,N){
                int mi = 1 << i;
                if (!(pat & mi)) continue;
                rep(j,N){
                    if (j == i) continue;
                    int mj = 1 << j;
                    if (!(pat & mj)) continue;

                    string s = dps[pat - mj][i] + A[j].substr(w[i][j]);
                    int len = s.size();
                    if (len < dp[pat][j]) {
                        dp[pat][j] = len;
                        dps[pat][j] = s;
                    }
                }
            }
        }

        int shortest_len = INT_MAX;
        string shortest;
        rep(i,N) {
            if (dp[P-1][i] < shortest_len) {
                shortest_len = dp[P-1][i];
                shortest = dps[P-1][i];
            }
        }
        return shortest;
    }

};