naoya_t@hatenablog

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

LeetCode Weekly Contest 127

4完2ペナで258/4734位...2ペナ痛い
これはレート冷やしそう
(追記:思ったほど冷えなかった。2304→2303)
f:id:n4_t:20190311163425p:plain:w400

A:負の数を優先的に正にして奇数残れば最小いじる
B:4つずつ分けて計算して足して
C:6かけ2全部試して最小値
D:最初が根、根との比較で左右分け、あとは再帰でやっていくだけ

Q1 (4)

  • 負の数にflipを使う
  • 正の数には極力使いたくない(どうしてもflipするなら一番小さいやつを1回)
  • ゼロがあるならそこで余ったflipを吸収したい
  • 総和は最後に計算

→WA(1)
負の数のみの場合、flipが奇数個余っていたら絶対値が最小のものをflipしなおすつもりでa.back()をflipしたが、正の数のflipをカウントしていなかったので元のa[]の最大値をflipしていた。
正の数のflipをカウントするようにして
→WA(2)
余りで1回やむなくflipする場合、絶対値が最小のものを選ぶべきなので再度ソートしてから
→AC

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& A, int K) {
        int L=A.size(); sort(ALL(A));
        for (int i=0; i<L; ++i){
            if (K==0) 
                break;
            if (A[i] < 0) { 
                A[i] = -A[i]; 
                --K;
            } else if (A[i] == 0) {
                K = 0;
                break;
            } else {
                break;
            }
        }
        K %= 2;
        if (K) {
            sort(ALL(A));
            A[0] = -A[0];
        }
        return accumulate(ALL(A), 0);
    }
};
後で

flipするのは常にa[]の中で一番小さい値
ってことは
もしかしてpriority_queue使ったらシンプルに書けるのでは?

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& A, int K) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for (int ai: A) pq.push(ai);
        for (int i=0; i<K; ++i) {
            int smallest = pq.top(); pq.pop();
            pq.push(-smallest);
        }
        int ans = 0;
        while (!pq.empty()) {
            ans += pq.top(); pq.pop();
        }
        return ans;
    }
};

→AC

Q2 (4)

大きいほうから4つずつのブロックで考える
f(a,b,c)=floor(a*b/c)とすると
Σ±f(n,n-1,n-2)+(n-3)みたいな(最初の±は最初だけ+であとは-)
最後の残りは手計算値を引いて終わり(fの足りないところに1を入れたのと同じ)
→AC

class Solution {
public:
    int q(int a,int b,int c) {
        a *= b; a /= c; return a;
    }
    int clumsy(int N) {
        if (N == 1) return 1; // q(1,1,1);
        if (N == 2) return 2; // q(2,1,1);
        if (N == 3) return 6; // q(3,2,1);
        // if (N == 4) return 7; // q(4,3,2);
        
        long long ans = 0, n = N;
        while (n) {
            switch (n) {
                case 1:
                    ans -= 1;
                    n = 0;
                    break;
                case 2:
                    ans -= 2;
                    n = 0;
                    break;
                case 3:
                    ans -= 6; // q(3,2,1);
                    n = 0;
                    break;
                default:
                    if (n == N) {
                        ans = ans + q(n,n-1,n-2) + (n-3);
                    } else {
                        ans = ans - q(n,n-1,n-2) + (n-3);
                    }
                    n -= 4;
                    break;
            }
        }
        return (int)ans;
    }
};

Q3 (5)

(1〜6どれで合わせるか)×(A側、B側)=12通り全部試して最小値
不可能な場合に-1を返す必要があってその処理に注意
→AC

class Solution {
    int sub(vector<int>& a, vector<int>& b, int m) {
        int L = a.size();
        int cnt = 0;
        for (int i=0; i<L; ++i) {
            if (a[i] == m) continue;
            if (b[i] == m) { ++cnt; continue; }
            return INT_MAX;
        }
        return cnt;
    }
public:
    int minDominoRotations(vector<int>& A, vector<int>& B) {
        int best = INT_MAX;
        for (int m=1; m<=6; ++m) {
            best = min(best, sub(A,B,m));
            best = min(best, sub(B,A,m));
        }
        if (best == INT_MAX) return -1;
        else return best;
    }
};

Q4 (6)

preorder traversalをBSTに展開
「最初の1つが根、その後の根より小さいエリアが左側、根より大きいエリアが右側」を再帰的にやっていくだけ
今回の中で一番やるだけ感あったし、書いたコードがRun Codeで一発で正解を出したの今日はこれだけだった
→AC

class Solution {
    vector<int> p;
    TreeNode* sub(int lo, int hi){
        if (lo == hi) return NULL;

        int rval = p[lo]; ++lo;
        TreeNode *root = new TreeNode(rval);
        if (lo == hi) return root;
        
        int right_lo = lower_bound(p.begin()+lo, p.begin()+hi, rval) - p.begin();
        root->left = sub(lo, right_lo);
        root->right = sub(right_lo, hi);
        return root;
    }
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        p = preorder;
        int L=preorder.size();
        return sub(0, L);
    }
};