naoya_t@hatenablog

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

LeetCode Weekly Contest 113

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

朝食後に猛烈に眠くなって11:25に目覚ましをセットして寝てからの参加。
その割に4問スムーズに解けた。早解き回。
40/3524位
f:id:n4_t:20181202131718p:plain
レート上がれー
→あがったー(2175→2232)
f:id:n4_t:20181205163036p:plain:w380

f:id:n4_t:20181205163139p:plain

Q1 - Largest Time for Given Digits (4)

こういうのの早解きは変に賢くやろうとしてはいけない。
h:[23 downto 0], m:[59 downto 0]の二重ループでカウントダウンして、最初に当てはまるやつを返した。
→AC 5:35

// いろいろ略
class Solution {
public:
    string largestTimeFromDigits(vector<int>& A) {
        sort(ALL(A));
        char tmp[6];
        for (int h=23; h>=0; --h) {
            int h10 = h / 10, h1 = h % 10;
            for (int m=59; m>=0; --m) {
                int m10 = m/10, m1 = m % 10;
                vi B { h10, h1, m10, m1 };
                sort(ALL(B));
                if (A == B) {
                    sprintf(tmp, "%02d:%02d", h, m);
                    return string(tmp);
                }
            }
        }
        return "";
    }
};

Q2 - Flip Equivalent Binary Trees (5)

再帰で解けた。
ローカルでTreeNodeを組み立ててテストするのが面倒くさい。
→AC 24:28

// いろいろ略
class Solution {
public:
    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        if (root1 == NULL && root2 == NULL) return true;
        if (root1 == NULL || root2 == NULL) return false;
        if (root1->val != root2->val) return false;

        if (flipEquiv(root1->left, root2->left) && flipEquiv(root1->right, root2->right))
            return true;
        if (flipEquiv(root1->left, root2->right) && flipEquiv(root1->right, root2->left))
            return true;
        return false;
    }
};

Q3 - Reveal Cards In Increasing Order (5)

  • 仮に[0..N-1]の配列に対して同じ操作をして、配列の何番目がいつ出てくるかをメモっておいて
  • deck[] をソートしたものにそれを適用したのが答え

→AC 34:42

// いろいろ略
class Solution {
public:
    vector<int> deckRevealedIncreasing(vector<int>& deck) {
        int L = deck.size();
        if (L<=2) return deck;
        sort(ALL(deck));

        vi a(L); rep(i,L) a[i] = i;
        vi b(L);
        for (int i=0,j=0; j<L; ){
            b[j++] = a[i++];
            a.pb(a[i++]);
        }

        vi c(L);
        rep(i,L) c[b[i]] = deck[i];
        return c;
    }
};

Q4 - Largest Component Size by Common Factor (8)

N=20000なので1対1にgcdを取っていたら間に合わない。

  • それぞれ素因数分解して、ある素数を素因数に持つグループ、のようにまとめておいて
  • 素数グループごとにUnionFindでくっつける
    • (配列の最初の要素 vs 2番目以降のやつを1つずつ)
  • 一番大きな島のサイズが答え

→AC 50:51

// いろいろ略
class Solution {
public:
    int largestComponentSize(vector<int>& A) {
        sieve(100001);

        int L = A.size();

        vvi comm(100001);

        rep(i,L){
            int x = A[i];
            vi fs = factorize(x); // 素因数分解。重複は排除したものが出てくる
            for (int f: fs) {
                comm[f].pb(i);
            }
        }

        UnionFind uf(L);
        rep(f,100001){
            int m = comm[f].size();
            if (m >= 2){
                int first = comm[f][0];
                for (int i=1; i<m; ++i) {
                    int ith = comm[f][i];
                    uf.unionSet(first, ith);
                }
            }
        }

        map<int,int> st;
        rep(i,L) {
            int root = uf.root(i);
            st[root]++;
        }
        int ans = 0;
        for(auto p: st) {
            ans = max(ans, p.second);
        }
        return ans;
    }
};