naoya_t@hatenablog

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

LeetCode Weekly Contest 116

12/23(日) 11:30-13:00
https://leetcode.com/contest/weekly-contest-116/

2-5-5-9
3問目で時間溶かして3完228/2965位。レート下がるか?
f:id:n4_t:20181223165602p:plain

Q1 - N-Repeated Element in Size 2N Array (2)

数えるだけ
フォームに直接書き込んだ
→AC (1:48)

class Solution {
public:
    int repeatedNTimes(vector<int>& A) {
        map<int,int> st;
        for(int a:A) st[a]++;
        int h=A.size()/2;
        for(auto p:st) if (p.second==h) return p.first;
        return -1;
    }
};

Pythonなら多分collections.Counter で殴ってこんな感じ:

from collections import Counter

class Solution(object):
    def repeatedNTimes(self, A):
        c = Counter(A)
        for k, v in c.items():
            if v == len(A)/2:
                return k

Q2 - Maximum Width Ramp (5)

  • 数ごとにまとめて(indexの小さい順にそれぞれ並べて)
  • 数の小さい組から set<int> に入れていく
    • *set.begin() にそこまでの最小インデックスがあるので、そことの差分を調べて最大値を保持

→AC (12:07)

// いろいろ略
class Solution {
public:
    int maxWidthRamp(vector<int>& A) {
        int L = A.size();
        map<int,vi> mp;
        rep(i,L) mp[ A[i] ].pb(i);
        
        int best = -1;
        set<int> s;
        for (auto p: mp) {
            int lev = p.first;
            s.insert(ALL(p.second));
            int largest = p.second.back();
            int smallest = *s.begin();
            best = max(best, largest-smallest);
        }
        return best;
    }
};

Q3 - Minimum Area Rectangle II (5)

4つの頂点を全探索(_nC_4通り)×4頂点の順列を全探索 (4!通り)。
隣接辺が直交している(内積=0)&長さが全て同じ(※問題ちゃんと読んでなかったとしか)
→ WA(1)

  • 4頂点の順列の全探索ができてない(next_permutation()してるのに使っていない)
  • あと、fabs()ではなくabs()を使っていた

直して
→ WA(2)

  • あれ? Output 0.0, Expected: 0 とかで落ちてる...(謎)

f:id:n4_t:20181223165542p:plain:w400

  • 0と-0で違うとか?答えにfabs()かけるか

→ WA(3)
あれ? Expected:2 って

  • 面積が最大の正方形を探していた
  • もしかして:最小 (WA)
  • もしかして:長方形 (WA)

はあ
向かい合う辺同士の長さが同じかどうかのチェックに緩めて
→TLE(1)

  • _nC_4O(N^4))は重いか。3点選んでもう1点は計算で出して、そこに存在するかチェックすることにしよう(O(N^3\log N)

→AC (1:07:03)

1位のnatsugiriさんの解法を見たらO(N^4)で回してた。
next_permutation() なんか使わなくても重複排除をループの中ですればいいだけのこと。
長方形判定もシンプル(向かい合う2つのベクトルが等しければそれでいい;当然だ…)

// いろいろ略
inline ii vec(ii& a, ii& b){
    return ii(b.first-a.first, b.second-a.second);
}
inline double len(ii& v){
    return hypot(v.first, v.second);
}
inline bool rect(ii& u, ii& v){
    return (u.first * v.first + u.second * v.second) == 0;
}
inline ii sub(ii& u, ii& v) {
    return ii(u.first - v.first, u.second - v.second);
}

class Solution {
    vii p;
    set<ii> pointset;

    double check(int i,int j,int k){
        vi a{i,j,k};
        vector<ii> v(4);
        vector<double> d(4);
        do{
            v[0] = vec(p[a[0]], p[a[1]]);
            v[1] = vec(p[a[1]], p[a[2]]);

            ii p3 = sub(p[a[2]], v[0]);
            if (!found(pointset, p3)) continue;

            v[2] = vec(p[a[2]], p3);
            v[3] = vec(p3, p[a[0]]);

            rep(s,4){
                d[s] = len(v[s]);
            }

            bool ok = true;
            rep(s,4){
                if (!rect(v[s], v[(s+1)%4])){ok = false; break;}
            }
            if (fabs(d[0] - d[2]) > 1e-6){ok = false;}
            if (fabs(d[1] - d[3]) > 1e-6){ok = false;}

            if (ok) {
                return d[0]*d[1];
            }
        }while(next_permutation(ALL(a)));

        return -1;
    }
public:
    double minAreaFreeRect(vector<vector<int>>& points) {
        int L=points.size();
        if (L < 4) return 0.0;
        p.resize(L);
        rep(i,L) {
            p[i] = ii(points[i][0], points[i][1]);
        }
        pointset.insert(ALL(p));

        double best = -1;
        for(int i=0; i<L-2; ++i){
            for(int j=i+1; j<L-1; ++j){
                for(int k=j+1; k<L; ++k){
                    double area = check(i,j,k);
                    if (area == -1) continue;

                    if (best == -1) best = area;
                    else best = min(best, area);
                }
            }
        }
        if (best == -1) return 0.0;
        else return fabs(best);
    }
};

Q4 - Least Operators to Express Number (9)

括弧が使えない = x^k + x^{k-1} + ... + x^2 + x^1 + x^0 のような表現を累乗なしに表記するのと同じ(=x進法でtargetを表現している)

x-1のように表現したほうが短くなる場合は上から1つ借りてくる。

自分の実装だと 5 24 のように繰り上がり(?繰り下がり?)が複数発生するケースで最適値が求められないと気づいたときには残り時間わずか
で試合終了

後で

  • ±を全通り試す→2 200000000 のようなケースでTLE
  • DPで出来ないか?
    • 右から決めて行く(高々2通りずつ)
    • それまでの最小値を超えたらそこで足切りできる

→AC

// いろいろ略
class Solution {
public:
    int leastOpsExpressTarget(int x, int target) {
        if (target == x) return 0;

        map<int,int> dp;

        {
            int t = target, r = t % x;
            int u = (t-r)/x;
            if (r == 0) {
                dp[u] = 0;
            } else {
                dp[u] = 2*r;
                dp[u+1] = 2*(x-r);
            }
        }

        int best = INT_MAX;

        for (int dim=1;  ; ++dim) {
            map<int,int> dp2;
            for (ii p: dp) {
                int t = p.first, v = p.second;
                if (t == 0) {
                    best = min(best, v);
                    continue;
                }
                if (v > best) {
                    continue;
                }
                int r = t % x;
                int u = (t-r)/x;
                if (r == 0) {
                    if (found(dp2, u))
                        dp2[u] = min(dp2[u], v);
                    else
                        dp2[u] = v;
                } else {
                    if (found(dp2, u))
                        dp2[u] = min(dp2[u], v + dim*r);
                    else
                        dp2[u] = v + dim*r;

                    if (found(dp2, u+1))
                        dp2[u+1] = min(dp2[u+1], v + dim*(x-r));
                    else
                        dp2[u+1] = v + dim*(x-r);
                }
            }
            if (dp2.empty()) break;
            dp = dp2;
        }

        return best - 1;
    }
};