naoya_t@hatenablog

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

LeetCode Weekly Contest 128

3/17(日) 11:30-13:00
遅めの朝食を摂りながら

4完0ペナ80/5164位

A.0の時どうするべきか分からずに自信はないが1にしてみた
B.60で割った余りで分類し
C.キャパシティを二分探索するだけで
D.一度でも使った数で桁DP

レート2303→2312
f:id:n4_t:20190319195523p:plain:w400
20回連続出場!TreeNodeにも慣れてきたw
f:id:n4_t:20190319195840p:plain:w600

Q1: 1012. Complement of Base 10 Integer (2)

Nより小さい1の補数、みたいな感じだけど
N=0のときどうしたらいいのか悩んで
問題文を何度も読み返して
(N=0のとき以外はleading zeroは付かない、ということはN=0なら付くということ?)
WAなら再提出するつもりで提出
→AC

class Solution {
public:
    int bitwiseComplement(int N) {
        for (int a=1; a<=0x3fffffff; a=2*a+1) {
            if (a >= N) return a-N;
        }
        return 0;
    }
};

Q2: 1013. Pairs of Songs With Total Durations Divisible by 60 (4)

  • 60で割った余りで分類して
  • 0の組、30の組については_nC_2
  • 1〜29の組については足して60になる59〜31の組との掛け算

→AC

class Solution {
public:
    int nC2(int n){
        return n*(n-1)/2;
    }
    int numPairsDivisibleBy60(vector<int>& time) {
        map<int,int> mp;
        for(int t:time){
            mp[t%60]++;
        }
        int ans = 0;
        ans += nC2(mp[0]);
        ans += nC2(mp[30]);
        for(int t=1; t<=29; ++t) {
            ans += mp[t] * mp[60-t];
        }
        return ans;
    }
};

Q3: 1014. Capacity To Ship Packages Within D Days (6)

キャパシティを二分探索

  • max(weights)未満では不可能なのでNG側をmax(weights)-1に
  • キャパがweightsの合計以上なら1日で終わるのでOK側をsum(weights)に

→AC

class Solution {
    int days(vector<int>& weights, int cap){
        int L=weights.size();
        int sum = 0, cnt = 0;
        for (int i=0; i<L; ++i) {
            if (weights[i] > cap) return INT_MAX;
            
            if (sum + weights[i] <= cap) {
                sum += weights[i];
            } else {
                ++cnt;
                sum = weights[i];
            }
        }
        if (sum > 0) ++cnt;
        return cnt;
    }
public:
    int shipWithinDays(vector<int>& weights, int D) {
        int L=weights.size();
        int lo=*max_element(weights.begin(), weights.end())-1,
            hi=accumulate(weights.begin(), weights.end(), 0);
        while (lo+1 < hi) { // [lo, hi), x o
            int mi = (lo+hi)/2;
            if (days(weights, mi) <= D) {
                hi = mi;
            } else {
                lo = mi;
            }
        }
        return hi;
    }
};

Q4: 1015. Numbers With 1 Repeated Digit (8)

Dは桁DPのD

  • dp[何桁目][0より大きい][N以下][直前の数字(なければ10)][yesかnoか]

みたいなのを実装
"repeated digit"というのは 00 11 22 33 44 55 66 77 88 99 みたいに数字が連続する箇所のことだと思って解いてて、N=1000でも181にしかならないしバグってる?あるいはサンプル間違ってるのでは?と思いながら
ひょっとして101 みたいなのでもrepeated digitになるのか?
とすると、直前の数字ではなく「1度でも使った数字」の集合(1024通り)を持たせる必要がある。

  • dp[何桁目][0より大きい][N以下][使った数字の集合][yesかnoか]

これで1000のとき262が出るようになった
ふぅ
→AC

class Solution {
public:
    int numDupDigitsAtMostN(int N) {
        vector<int> A;
        while (N) {
            A.push_back(N%10); N /= 10;
        }
        reverse(ALL(A));
        const int n = A.size();

        int dp[11][2][2][1024][2]; // dp[i][0<][<x][used][flag]
        mset(dp, 0);

        dp[0][0][0][0][0] = 1;


        for (int i=0; i<n; ++i) {
            for (int m=0; m<2; ++m) {
                for (int j = 0; j < 2; j++) {
                    for (int used=0; used<1024; ++used) {
                        for (int f=0; f<2; ++f) {
                            int x = j ? 9 : A[i];
                            for (int d = 0; d <= x; d++) {
                                int f_ = f;
                                if (used & (1 << d)) f_ = 1;
                                int used_ = (d==0 && m==0) ? used : (used | (1<<d));
                                dp[i + 1][m || d > 0][j || d < x][used_][f_]
                                += dp[i][m][j][used][f];
                            }
                        }
                    }
                }
            }
        }

        int ans = 0;
            for (int j = 0; j < 2; j++) {
                for (int l = 0; l < 1024; l++) {
                    ans += dp[n][1][j][l][1];
                }
            }

        return ans;
    }
};