Codeforces Round #581 Div. 2 D: Kirk and a Binary String

問題概要

原文 → Problem - D2 - Codeforces

0 と 1 のみからなる長さ の文字列 が与えられる。 の文字を、以下の条件が満たされた上で変更することを考える。

• 全ての に対して、 の 文字目から 文字目までのみからできる最長単調非減少列の大きさが元の文字列と変わらない

変更後の文字列であって、0 を最も多く含むものを求めよ。

解説

まず、"10" という文字列について変更不可能であることがわかる。ここから考察を進めていこう。

"10" という文字列は 1 と 0 を 1 文字ずつ含んでいるが、"10" を通過する直前の部分列が最後にどの文字を使ったかによって場合分けする。

• 部分列が最後に "0" を使用していた場合、つまり "....0xxx10" (x は選択していない文字) のような状況であった場合、それに "10" の 0 を続けるか 1 を続けるか 2 通りの選択ができる
• 部分列が最後に "1" を使用していた場合、つまり "...1xxx10" のような状況であった場合、それに "10" の 1 を続けることができる

最後に使用した文字に続きうる文字のうち、どれか 1 つを "10" から使用することができることがわかるであろう。言い換えれば、「"10" を通過するときは必ずどれか 1 文字をその中から使っていて、適切に選択すれば最長単調非減少列の大きさに影響しない」ということにもなるため、このようなパターンは元々なかったものとして (削除して) 構わない。

文字列から "10" というパターンを左から順に消していくと、最終的にできる文字列は "0000...0111.....1" のように左が 0 で右が 1 となる文字列である。この文字列に関しては全て "0" に変更してしまっても最長単調非減少列の大きさは変わらない。

ゆえに、stack などを用いて高速に解くことができる。

ソースコード

int main() {
    string s; cin >> s;

    vector<bool> checked(s.size());
    stack< pair<char, int> > st;
    for(size_t i=0; i<s.size(); i++) {
        if(st.empty() or st.top().first == s[i] or st.top().first == '0') {
            st.emplace(s[i], i);
        }
        else {
            checked[i] = checked[st.top().second] = true;
            st.pop();
        }
    }

    for(size_t i=0; i<s.size(); i++) {
        if(!checked[i]) s[i] = '0';
    }
    cout << s << endl;
    return 0;
}

"10" が変わらないのは思いついたけど、その後が全然ダメだった。難しい・・・

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;
        }
    }
};

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