naoya_t@hatenablog

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

LeetCode Weekly Contest 119

1/13(日) 11:30-13:00
4完140/3334位

開始時にロードが酷く重いので開いた順に解いていく奴
C:累積和modで取って同じ値の箇所の個数のnC2の和
A:並べ替え二乗のままで大丈夫
B:ソートして大きいのから3つ取り、駄目なら順に大きい3つ
D:提出後初めて気づく読み違え。5分とはいえペナルティ痛し

575(77)に揃えてみた
だがしかしDは答えになってないw

レーティングは微増(2271→2279)
f:id:n4_t:20190115143430p:plain:w450

Q3: 974. Subarray Sums Divisible by K

最初なかなかページがロードされないので、先に開いたQ3に手をつけた。
累積和をmodで取っていって同じ値になるところの個数n_nC_2していくやつだ
累積和が負になるケースに注意だね
→AC 08:28

class Solution {
public:
    int subarraysDivByK(vector<int>& A, int K) {
        int L=A.size();
        vi st(K,0);
        vi ac(L+1); ac[0]=0; rep(i,L) ac[i+1]=(ac[i]+A[i])%K;
        rep(i,L+1) st[ (ac[i]+K)%K ]++;
        int ans = 0;
        rep(i,K) {
            int n = st[i];
            ans += n*(n-1)/2;
        }
        return ans;
    }
};

Q1: 973. K Closest Points to Origin

ゼロからの距離。平方根取らなくても二乗のまま(intで)比較可能
ソートして小さいほうからK個答えるだけ
→AC 12:44

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        int L = points.size();
        vii tmp(L);
        rep(i,L) {
            int x = points[i][0], y = points[i][1];
            int d = x*x + y*y;
            tmp[i] = make_pair(d, i);
        }
        sort(ALL(tmp));
        vvi ans(K);
        rep(i,K) ans[i] = points[ tmp[i].second ];
        return ans;
    }
};

Q2: 976. Largest Perimeter Triangle

三角形
O(N^2)で総当たり…
いや違う
降順ソートして上から3つ見るじゃん
一番大きいのが長辺で
あとの2つの和がそれより大きければよくて
小さければそこをどう交換しようが(それと同じか短いものしか残っていないので)無理。
てことは1つ目を捨てて、2つ目から4つ目までを見ればいい。
みたいにN-2箇所調べて、駄目なら0
→AC 21:50

class Solution {
public:
    int largestPerimeter(vector<int>& A) {
        int L = A.size();
        sort(ALL(A));
        for (int i=L-1; i>=2; --i){
            if (A[i-2] + A[i-1] > A[i]) return A[i-2] + A[i-1] + A[i];
        }
        return 0;
    }
};

Q4: 975. Odd Even Jump

  • priority_queueに飛び先未確定の場所と値を放り込んで、飛び先テーブルを構築していく
  • 飛び先テーブルが出来たら、各場所の上下にノードを持たせてグラフを繋いで
  • ゴール(右端)に繋がっているか調べる。(これはUnionFindで出来る)

サンプルケース通ったし投げてみるか
→WA(1) 42:00
大丈夫、まだ48分ある

[1,2,3,2,1,4,4,5] のケースは6を返すべきところを7を返してる、とな
手計算してみたけど7で合ってるじゃん

問題の制約を読み返す
ん?
右側の最寄りの位置に飛ぶんじゃなくて、A_iと同じか一番(上に・下に)近い値に飛ぶのね
(それでどう変わる?)

飛び先テーブルの作り方を

  • 右から1つずつmap<int,vector<int>>に挿入していく。
  • 自分より右の位置に同じ値のものがあればその中で最寄りの場所
  • なければ値の最も(上下に)近いものの場所

といった感じに変えて(あとは同じ)
投げる
→AC 1:10:27

class Solution {
public:
    int oddEvenJumps(vector<int>& A) {
        int L = A.size();
        vi up(L,-1), down(L,-1);
        priority_queue<ii,vector<ii>,greater<ii>> uq;
        priority_queue<ii> dq;

        map<int,vi> mp;
        for (int i=L-1; i>=0; --i) {
            int x = A[i];

            if (i < L-1) {
                if (found(mp, x)) {
                    up[i] = down[i] = mp[x].back();
                } else {
                    // up
                    auto it = mp.upper_bound(x);
                    if (it != mp.end()) {
                        up[i] = it->second.back();
                    }
                    // down
                    if (it != mp.begin()) {
                        --it;
                        down[i] = it->second.back();
                    }

                }
            }
            mp[x].pb(i);
        }

        UnionFind uf(L*2);
        rep(i,L){
            if (up[i] != -1) {
                uf.unionSet(i, L+up[i]);
            }
            if (down[i] != -1) {
                uf.unionSet(L+i, down[i]);
            }
        }

        set<int> goal;
        goal.insert(uf.root(L-1));
        goal.insert(uf.root(L + L-1));

        int ans = 0;
        rep(i,L){
            if (found(goal, uf.root(i))) ++ans;
        }

        return ans;
    }
};