naoya_t@hatenablog

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

LeetCode Weekly Contest 123

leetcode.com
2/10(日) 11:30-13:00

4問目が間に合わず3完で233/3714位。

A.Kの値を配列形に変換し多倍長にて足し算をする
B.等号でUnionFind繋いだら不等号にてテストしていく
C.倍々にしたXとYの差を2の冪乗で削って減らす
D.尺取りのデバッグにただ時間かけギリ間に合わずあと20秒

Q1 - 989. Add to Array-Form of Integer (4)

Kを配列形式に変換したやつ(変換するまでもないが)をA[]に足し込む。
昨日のゆるふわオンサイトで多倍長の足し算問題が出たのが記憶に新しい。
→AC 04:44

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& A, int K) {
        int L=A.size();
        reverse(ALL(A));
        rep(i,12) A.pb(0);
        rep(i,A.size()) {
            A[i] += K % 10;
            if (A[i] >= 10) {
                A[i+1] += A[i]/10;
                A[i] %= 10;
            }
            K /= 10;
        }
        while (!A.empty() && A.back() == 0) A.pop_back();
        if (A.empty()) A.pb(0);
        reverse(ALL(A));
        return A;
    }
};
||
<


** Q2 - 990. Satisfiability of Equality Equations (6)
最初2-SAT的に(true/falseの二値しかない想定で)解こうとして1WAの後
- UnionFind
- <code>==</code> で繋がっている2変数を繋ぐ
- <code>=!</code> で繋がっている2変数が別々の島に属しているかチェック
→AC 16:41 (+1)
>||
class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        int L = equations.size();
        UnionFind uf(26);
        vii tests;
        for (string& s: equations){
            int a = s[0] - 'a', b = s[3] - 'a';
            int eq = s[1] == '=';
            if (eq) {
                 uf.unionSet(a,b);
            } else{
                 tests.emplace_back(a,b);
            }
        }
        for (ii p: tests){
            int a=p.first, b=p.second;
            if (uf.root(a) == uf.root(b)) return false;
        }
        return true;
    }
};

Q3 - 991. Broken Calculator (6)

  • duplicateすると x, 2x, 4x, 8x, 16x, ... と増えていく
  • decrementするとx-1, 2x-1, 4x-1, 8x-1, 16x-1 のようなのが作れる
  • 2x-2=2(x-1) なので 2x経由でもx-1経由でも作れる(どちらも2手)
  • たとえば 16x-5=4(4x-1)-1 で、2回dupして4xになったところで1decrし、さらに2回dupして16x-4になったところで1decrすることで9手を6手に短縮できる
  • 2の冪乗(0乗から〈dupした回数〉乗まで)を大きい方から使っていけばよい
    • 最初dupした回数縛りを考えずに __builtin_popcount で行けるかと思って1WA。

→AC 39:50 (+1)

class Solution {
public:
    int brokenCalc(int X, int Y) {
        if (Y <= X) return X-Y;
        ll a=(ll)X, b=(ll)Y;
        ll best = LLONG_MAX, lim = LLONG_MAX/2;
        for (ll ka=a,s=0; ka<=lim; ka*=2,++s) {
            // debug("kx=%lld s=%lld; b=%lld\n", ka, s, b);
            if (ka < b) continue;
            if (ka == b) { best=min(best,s); break; }
            // kx > y; y=kx-w
            ll w = ka - b;
            ll sc = s;
            for (ll m=1LL<<s,j=s; j>=0; m>>=1,--j) {
                sc += w/m;
                w %= m;
            }
            // debug("w=%lld, s=%lld: sc=%lld\n", ka-b,s,sc);
            best=min(best, sc);
        }
        return (int)best;
    }
};

Q4 - 992. Subarrays with K Different Integers (8)

尺取りだろって一瞬で分かるんだけど
尺取りの実装&デバッグが苦手すぎる
(何とかしておきたい)

残り15秒でRun Testしたらデバッグ出力用のcoutが入っててCE
→除去して投げてAC(コンテスト終了後20秒)
><

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& A, int K) {
        int ans = 0;
        int L=A.size();
        vi cnt(L+1, 0);
        int kind=0;
        for (int i=0,j=0; i<L && j<=L; ) {
            // printf("(%d %d)\n", i, j);
            while (kind <= K) {
                if (kind == K) {
                    // printf("  + (%d %d)\n", i, j);
                    ++ans;
                }
                if (j==L) break; // goto out;
                if (cnt[A[j]] == 0) {
                    if (kind == K) break;
                    ++kind;
                }
                cnt[ A[j] ]++;
                ++j;
            }
            // kind == K

            while (i<j) {
                // printf("{%d %d} ", i, j); cout << cnt << endl;
                cnt[A[i]]--;
                if (cnt[A[i]] == 0) kind--;
                ++i;
                if (kind < K) break;

                // kind == K
                int jb = j;
                vi _cnt = cnt;

                while (kind == K) {
                    // printf(" {%d %d} ", i, j); cout << cnt << endl;
                    --j;
                    cnt[A[j]]--;
                    if (cnt[A[j]] == 0) { // --kind
                        cnt[A[j]]++;
                        ++j;
                        break;
                    }
                }

                ans += jb - j + 1;
                j = jb; cnt = _cnt;
                assert(kind==K);
            }

        }
        out:;
        return ans;
    }
};

上位陣の実装を見て

1位のuwi先生の実装を見ると「K種類以下」-「K-1種類以下」でシンプルに求まるようだ

uwiさんのコードを(自分が書いたコードに寄せつつ)C++に書き直したやつ

class Solution {
public:
    int subarraysWithKDistinct(vector<int> A, int K) {
        return count(A, K) - count(A, K-1); // (K種類が何通りか) = (K種類以下が何通りか) - (K-1種類以下が何通りか)
    }
    
    int count(vector<int>& a, int K) {
        // cnt[n] : 数nがいくつあるか。種類数の増減もここから読む。
        vector<int> cnt(a.size()+1, 0);

        int kind=0; // 種類数
        int p=0; // 尺取りの後ろ足(iが前足)
        int ret=0; // 返り値

        for (int i=0; i<a.size(); i++) { 
            // 前足が進んだのでcntを更新。種類数も更新。
            // cnt, kind はここでは区間 [p, i) の状態
            if (++cnt[a[i]] == 1) ++kind;
            // cnt, kind はここでは区間 [p, i] の状態

            // K種類を超えてしまったら、ちょうどK種類になるところまで後ろ足を進める
            while (kind > K) {
                if (--cnt[a[p++]] == 0) --kind;
                // cnt, kind はここでは区間 (p++, i] = [++p, i] の状態
            }
            // この時点で、[p, i] 区間にちょうどK種類の数が含まれている。
            // p以降 (inclusive) で始まり i で終わる任意の区間において、含まれる数はK種類以下である。
            // ここでの数え上げ対象は区間終点が i のものに限るので、始点を p から i までで i-p+1 通り。
            ret += i-p+1;
        }

        return ret; // count(a,K) はK種類以下の区間が何通りあるかを返す
    }
};