LeetCode Weekly Contest 149: Swap For Longest Repeated Character Substring

本番に書いたコードの実装が悪すぎたので書き直し

問題概要

原文 → Loading...

文字列 が与えられる。この文字列に対して、あるふたつの文字を選んで swap することが一度だけできる。同じアルファベットを最大で何連続させられるか答えよ。

解説

まずランレングス圧縮をする。あとはそれぞれの要素に対して次に示すものを計算して max をとればよい。

• swap する前の長さ
• swap する前の長さ + 1 (ただし、この結果が文字の登場回数より多くなってはいけない)
• aa...a b aa...a のように真ん中が 1 文字だけ異なる場合を考慮するために、(左の要素の長さ) + (右の要素の長さ) + 1 を計算する。ただし、この結果が文字の登場回数より多くなってはいけない。

ソースコード

class Solution {
public:
    int maxRepOpt1(string text) {
        vector< pair<char, int> > rle;
        vector<int> cnt(26);
        
        for(auto c : text) {
            if(rle.empty() or rle.back().first != c) rle.emplace_back(c, 1);
            else rle.back().second++;
            cnt[c - 'a']++;
        }
        
        int N = rle.size(), ans = 0;
        for(int i=0; i<N; i++) {
            int id = rle[i].first - 'a';
            ans = max(ans, min(cnt[id], rle[i].second + 1));
        }
        for(int i=1; i+1<N; i++) {
            if(rle[i-1].first == rle[i+1].first and rle[i].second == 1) {
                int id = rle[i-1].first - 'a';
                ans = max(ans, min(cnt[id], rle[i-1].second + rle[i+1].second + 1));
            }
        }
        return ans;
    }
};

これくらい簡潔な実装を思いつきたかったなあ。

LeetCode Weekly Contest 149: Online Majority Element In Subarray

問題概要

はじめに、長さ の数列 が与えられるので、以下のクエリにオンラインで答えよ。

• の 番目から 番目の間に 回以上出現するものを答えよ。なお は区間の長さの半分を真に超えるため該当する場合は 1 つしか該当しない。そのような要素がなければ -1 と答えよ。

解説

クエリの長さで平方分割を行う。ある があって、クエリで与えられる区間の長さが 以下であるかどうかで場合分けを行う。

• 長さが 以下である場合
  • この場合は から までを愚直に調べて、最も多いものが条件を満たすかどうかを見ればよい。
• 長さが 以上である場合
  • クエリで与えられる区間の長さを とする。クエリの条件より、答えが存在するならばその数は区間内に 回を超えて出現するはずであるため、そもそも数列内に 回以下しか登場しない要素について調べる必要がない。そして、 であることから、調べるべき要素の種類数は高々 個である。よって、各要素についてインデックス列を持ち二分探索を行うことで処理できる。

と置くと、前者の処理で に、後者の処理で となるので、高速に処理可能である。

別解

知りたいのは区間内の majority なので、区間内にある値を乱択し、それが majority であるかどうかをチェックするだけでも高い確率で通る。majority ならば選ばれる確率はだいたい 2 分の 1 で、20 回試行したときにそれを全部外すのは なので、確率としてはとても低い。

ソースコード

愚直に調べるパートには Boyer-Moore majority vote algorithm を使用している。線形だけど定数倍が軽そう。

class MajorityChecker {
public:
    vector<int> vec;
    unordered_map< int, vector<int> > rec;
    vector< pair<int, int> > occur;
    int s;
    MajorityChecker(vector<int>& arr) {
        this->vec = arr;
        int N = vec.size(); s = sqrt(N);
        for(int i=0; i<N; i++) {
            rec[ vec[i] ].emplace_back(i);
        }
        for(auto e : rec) {
            occur.emplace_back(e.second.size(), e.first);
        }
        sort(occur.rbegin(), occur.rend());
    }
    
    int query(int left, int right, int threshold) {
        right++;
        if(right - left <= s) {
            int cand = 0, cnt = 0;
            for(int i=left; i<right; i++) {
                if(cnt == 0) cand = vec[i], cnt = 1;
                else if(cand == vec[i]) cnt++;
                else cnt--;
            }
            for(int i=left; i<right; i++) {
                if(vec[i] == cand) threshold--;
            }
            return (threshold <= 0 ? cand : -1);
        }
        else {
            for(size_t k=0; k<occur.size(); k++) {
                int cand = occur[k].second, cnt = occur[k].first;
                if(cnt < threshold) break;
                auto u = lower_bound(rec[cand].begin(), rec[cand].end(), right);
                auto d = lower_bound(rec[cand].begin(), rec[cand].end(), left );
                if(u - d >= threshold) return cand;
            }
            return -1;
        }
    }
};

これは勉強になりました。

TopCoder SRM 764: RectangleHunt

問題概要

原文 → TopCoder Statistics - Problem Statement

個の点が与えられる。

与えられる点から 4 つ選んでできる長方形のうち、面積が最大のものを答えよ。ただし長方形を作ることができなければ -1 と答えよ。なお、長方形は軸に平行でなくてもよい。

解説

全探索が許される制約なので、4 重ループをしてそれぞれについて長方形になりうるかどうかを判定すればよい。

長方形を判定する前に、平行四辺形の場合にどのように判定するべきかを考える。以下、平行四辺形の頂点を反時計回りに とそれぞれおくことにする。おそらく最も簡単なのは以下の判定方法である。

• 辺 と辺 が平行
• 辺 と辺 が平行

しかし、これだけではまだ不十分な場合があって、たとえば一直線上に と並んでいるとき、上の条件をすべて満たしてしまう。なので、追加で以下の条件も見る必要がある。

• 辺 と辺 が平行でない

これらは全て外積の計算で判定できる。

では元の問題に立ち返り、長方形の場合にどうすべきか考える。長方形とは平行四辺形の特殊な例で、対角線の長さが等しくなる。つまり、下の条件も満たす必要がある。

• 辺 と辺 の長さが等しい

今回の問題とは関係ないが、正方形かどうかを判定するには 4 辺すべての辺の長さが等しい必要があるので追加で以下の条件も必要になるはず。(これが必要十分でなかったら教えてください)

• 辺 と辺 の長さが等しい

struct RectangleHunt {
    ll cross(pair<ll, ll> a1, pair<ll, ll> a2, pair<ll, ll> b1, pair<ll, ll> b2) {
        ll x1 = a1.first - a2.first;
        ll x2 = b1.first - b2.first;
        ll y1 = a1.second - a2.second;
        ll y2 = b1.second - b2.second;

        ll res = x1 * y2 - x2 * y1;
        return res;
    }

    ll area(pair<ll, ll> a1, pair<ll, ll> a2, pair<ll, ll> b1) {
        ll x1 = a1.first - b1.first;
        ll x2 = a2.first - b1.first;
        ll y1 = a1.second - b1.second;
        ll y2 = a2.second - b1.second;
        return llabs(x1 * y2 - y1 * x2);
    }

    ll len(pair<ll, ll> s1, pair<ll, ll> s2) {
        ll dfx = s1.first - s2.first;
        ll dfy = s1.second - s2.second;
        return dfx * dfx + dfy * dfy;
    }
    
    double get(const vector< pair<int, int> > &points, const vector<int> &ord) {
        vector< pair<int, int> > p;
        for(int i=0; i<4; i++) {
            p.emplace_back(points[ ord[i] ]);
        }

        if(cross(p[0], p[1], p[3], p[2]) != 0) return -1;
        if(cross(p[0], p[3], p[1], p[2]) != 0) return -1;
        if(cross(p[0], p[2], p[1], p[3]) == 0) return -1;
        if(len(p[0], p[2]) != len(p[1], p[3])) return -1;
        return area(p[0], p[1], p[3]);
    }
    
    double largest(vector <int> x, vector <int> y) {
        double ans = -1;
        int N = x.size();
        for(int i=0; i<N; i++) {
            for(int j=i+1; j<N; j++) {
                for(int k=j+1; k<N; k++) {
                    for(int l=k+1; l<N; l++) {
                        vector< pair<int, int> > points;
                        points.emplace_back(make_pair(x[i], y[i]));
                        points.emplace_back(make_pair(x[j], y[j]));
                        points.emplace_back(make_pair(x[k], y[k]));
                        points.emplace_back(make_pair(x[l], y[l]));

                        vector<int> ord(4);
                        iota(ord.begin(), ord.end(), 0);

                        do {
                            ans = max(ans, get(points, ord));
                        }while(next_permutation(ord.begin(), ord.end()));
                    }
                }
            }
        }
        return ans;
    }
};

幾何の条件いつもミスするけどそろそろどうにかしたいな。