naoya_t@hatenablog

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

LeetCode Weekly Contest 118

1/6(日) 11:30-13:00
4完(残り53秒でAC)149/3586位
レート微増 (2263→2271)
f:id:n4_t:20190108090058p:plain:w450

Q1 - Powerful Integers (3)

全探索でよさそう
→WA(1)
x,yに1が来たときに死
→AC 09:37 (+1)

class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        vi xs(1,1),ys(1,1);
        if (x > 1)
          for (int xi=x; xi<=bound; xi*=x) xs.push_back(xi);
        if (y > 1)
          for (int yi=y; yi<=bound; yi*=y) ys.push_back(yi);
        set<int> g;
        for (int xi: xs) for (int yi:ys) {
            if (xi+yi <= bound)
                g.insert(xi + yi);
        }
        return vi(ALL(g));
    }
};

Q2 - Pancake Sorting (5)

右から揃える
一番大きいものを一旦左へ、その後右へ
(最初逆にやってて結果が合わなかった)
→AC 28:19

class Solution {
public:
    vector<int> pancakeSort(vector<int>& A) {
        vi ans;
        int L = A.size();
        if (L <= 1) return A;
        for (int w=L; w>1; --w) {
            int ix = max_element(A.begin(), A.begin()+w) - A.begin();
            if (ix == w-1) continue;
            if (1+ix != 1) {
                ans.push_back(1+ix);
                reverse(A.begin(), A.begin()+1+ix);
            }
            ans.push_back(w);
            reverse(A.begin(), A.begin()+w);
        }
        return ans;
    }
};

Q3 - Flip Binary Tree To Match Preorder Traversal (6)

左右のsubtreeに含まれるvalを集計して、flipした場合/しない場合にそれで辻褄があうか見ていく再帰
制約きつくないからsetで書いたけど
→AC 58:57

class Solution {
    set<int> vals(TreeNode *root) {
        if (!root) return set<int>{};
        set<int> s, lefts, rights;
        s.insert(root->val);
        if (root->left){
            lefts = vals(root->left);
            s.insert(ALL(lefts));
        }
        if (root->right) {
            rights = vals(root->right);
            s.insert(ALL(rights));
        }
        return move(s);
    }

    int sub(TreeNode *root, vi& voyage, int lo, int hi, vi& out) {
        // cerr << "sub" << voyage << lo << " " << hi << endl;
        if (!root) {
            if (lo == hi) return 0;
            else return -1;
        }

        if (lo == hi) return -1;
        if (voyage[lo] != root->val) return -1;

        ++lo;
        if (lo == hi) {
            if (!root->left && !root->right) return 0;
            return -1;
        }

        set<int> lefts, rights;
        if (root->left) lefts = vals(root->left);
        if (root->right) rights = vals(root->right);
        int lc = 0, rc = 0;
        for (int i=lo; i<hi; ++i) {
            if (found(lefts, voyage[i])) ++lc;
            else break;
        }
        for (int i=lo+lc; i<hi; ++i) {
            if (found(rights, voyage[i])) ++rc;
            else break;
        }

        if (lo+lc+rc == hi) {
            // no flip here
            if (sub(root->left, voyage, lo, lo+lc, out) == -1) return -1;
            if (sub(root->right, voyage, lo+lc, hi, out) == -1) return -1;
            return 0;
        }
        lc = rc = 0;
        for (int i=lo; i<hi; ++i) {
            if (found(rights, voyage[i])) ++rc;
            else break;
        }
        for (int i=lo+rc; i<hi; ++i) {
            if (found(lefts, voyage[i])) ++lc;
            else break;
        }
        if (lo+rc+lc == hi) {
            //  flip here
            out.push_back(root->val);
            if (sub(root->right, voyage, lo, lo+rc, out) == -1) return -1;
            if (sub(root->left, voyage, lo+rc, hi, out) == -1) return -1;
            return 0;
        }
        return -1;
    }
public:
    vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
        vi result;
        if (sub(root, voyage, 0, voyage.size(), result) == -1) {
            return vi{-1};
        }
        return result;
    }
};

Q4 - Equal Rational Numbers (8)

long doubleで書きかけてやっぱり分数と思って分数で

  • aaa = \displaystyle aaa
  • aaa. = \displaystyle aaa
  • aaa.bbb = \displaystyle aaa+\frac{bbb}{10^{|bbb|}}=\frac{aaa\cdot10^{|bbb|}+bbb}{10^{|bbb|}}
  • aaa.(ccc) = \displaystyle aaa+\frac{ccc}{10^{|ccc|}-1}=\frac{aaa\cdot(10^{|ccc|}-1)+ccc}{10^{|ccc|}-1}
  • aaa.bbb(ccc) = \displaystyle aaa+\frac{bbb}{10^{|bbb|}}+\frac{ccc}{10^{|bbb|}(10^{|ccc|}-1)}=\frac{aaa\cdot10^{|bbb|}(10^{|ccc|}-1)+bbb\cdot(10^{|ccc|}-1)+ccc}{10^{|bbb|}(10^{|ccc|}-1)}

→WA(1)
整数部の長さ(aaa)を1で決め打ちしてた
→AC 1:29:07 (+1)

ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }

typedef pair<ll,ll> R;

R ts(R x) {  // 通分
    if (x.first == 0) return R(0,1);

    ll g = gcd(x.first, x.second);
    if (g == 0) return x;
    return R(x.first/g, x.second/g);
}
bool eq(R x, R y) {
    x = ts(x); y = ts(y);
    return (x.first == y.first && x.second == y.second);
}

R type3(string& s) {
    // x.yyyy(zzzz)
    int L = s.size(), op = -1, dot = -1;
    for (int i=2; i<L-1; ++i) {
        if (s[i] == '(') { op=i; break; }
    }
    for (int i=1; i<L; ++i) {
        if (s[i] == '.') { dot = i; break; }
    }
    ll x = atoi(s.substr(0,dot).c_str());
    int ly = op - 1-dot, lz = L-1-dot - 1 - ly - 1;

    ll y = atoi(s.substr(1+dot, ly).c_str());
    ll z = atoi(s.substr(1+dot+ly+1, lz).c_str());

    ll denom1 = 1, denom2 = 1;
    rep(i,ly) denom1 *= 10;
    rep(i,lz) denom2 *= 10; denom2--;
    ll numer = x * denom1 + y;
    R r(numer*denom2 + z, denom1*denom2);
    return r;
}

R type2(string& s) {
    // x.yyyy
    int L = s.size();
    int dot = -1;
    for (int i=1; i<L; ++i) {
        if (s[i] == '.') { dot = i; break; }
    }
    ll x = atoi(s.substr(0,dot).c_str());

    int ly = L - 1 - dot;
    ll y = atoi(s.substr(dot+1,ly).c_str());

    ll denom = 1; rep(i,ly) denom *= 10;
    ll numer = x * denom + y;
    R r(numer, denom);
    return r;
}

R f(string& s){
    R x(0,1);
    int L = s.size();

    if (s[L-1] == ')') {
        return type3(s);
    }
    if (s[L-1] == '.') {
        int a = atoi(s.substr(0, L-1).c_str());
        return R(a,1);
    }
    // 0  / 0.1
    for (int i=1; i<L; ++i) {
        if (s[i] == '.') return type2(s);
    }
    // integer part only
    int a = atoi(s.c_str());
    return R(a,1);
}

class Solution {
public:
    bool isRationalEqual(string S, string T) {
        R sa = f(S), sb = f(T);
        return eq(sa, sb);
    }
};