SRM735 Div. 2 1000 MajoritySubarray

programming contest

このエントリーをはてなブックマークに追加

Div.2に落とされた直後のSRMで、自己最高の4位を取ることができました。本当は同時開催のTCOに出るつもりだったところ操作ミスでSRMにエントリーしてしまっていたのですが、結果オーライでした。記念のスクリーンショット。 f:id:minus9d:20180628224923p:plain

本番では解けなかった1000のMajoritySubarrayが勉強になったので解法をメモしておきます。

問題概要

  • TopCoder Statistics - Problem Statement
    • 長さN(最大100000)で、M(最大50)以下の整数からなる数列が与えられる。この数列のうち、"majority element”が存在するような部分数列の数を求める。
    • ここで"majority element"とは、数列の過半数を占める数のこと。例えば数列{2, 2, 3, 3, 3}では3がmajority element。

解法

数列の長さが100000なことから、すべての部分文字列でシミュレーションするのは計算量的に無理です。

公式ブログSingle Round Match 735 Editorials - Topcoder 2.0 にわかりやすい解法があります。まず、ある数字に着目して、その数字がmajority elementである部分数列を数えることだけを考えます。数列中に着目する数字が現れれば+1, 現れなければ-1して新たな数列を作成すると、この数列中の任意の2要素の大小関係を見るだけで、その部分数列に"majority element”が存在するかを判定できるようになります。これができれば、BITやセグメントツリーなどのデータ構造を使って、"majority element”が存在する部分数列の数を高速に数えられます。詳しくは以下に貼るソースコード中の説明を見てください。

この「ある数列の部分数列が条件を満たすかどうか、2要素の大小関係を見るだけで判定できるような数列を作れれば、BITで数え上げができる」という部分は他にも応用ができそうだと思いました。

// 公式解答を見た
//   https://www.topcoder.com/blog/single-round-match-735-editorials/

// 配列Aの構成要素はせいぜい50なので、各構成要素ごとに考えればよい。
// 次のような配列Aで、'o'が支配的になる部分配列の数を考える
// 
//   oxxooxo
//   0123456 (idx)
//
// 配列Bを以下のように構成する。
//   B[0]=7  (すべての要素が0以上になるよう下駄を履かせる)
//   a[i]が'o'であればb[i+1]=b[i]+1, 'o'以外であればb[i+1]=b[i]-1
// すると配列Bは以下のようになる
//  78767878
//  01234567 (idx)
// b[j] < b[i]となるj < iのペアを探す。このとき aの部分文字列[j, i)は'o'が支配的になっていることがわかる。
// 列挙すると以下のようになる。
// (j, i) = (0, 1), (0, 5), (0, 7),
//          (2, 5), (2, 7),
//          (3, 4), (3, 5), (3, 6), (3, 7),
//          (4, 5), (4, 7),
//          (6, 7)
//
// このようなペアの数は、BITを使うと効率的に求められる。
// たとえば B[5]に注目すると、これより左にある、B[5]より小さい値であるようなidxの数が、BITにより効率的に求められる

#include <iostream>
#include <sstream>
#include <string>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <cstring>
#include <fstream>

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

using namespace std;

class MajoritySubarray {
public:
    vector<ll> F;
    int fenwick_sum(int i) { // BITのこと。実装は蟻本と同じ
        int s = 0;
        while (i > 0) {
            s += F[i];
            i -= i & -i;  // i & -i: 1, 2, 4, 8, 16, ...のうち、iを割れる最大の数
                          //         言い換えると、iの一番右に立っているビットに等しい
        }
        return s;
    }
    void fenwick_add(int i, int val) {
        while(i < (1<<18)) {
            F[i] += val;
            i += i & -i;
        }
    }

    long long solve(ll N, ll seed, ll MOD) {
        vector<ll> As(N);
        REP(i, N) {
            As[i] = (seed / 65536) % MOD;
            seed = (seed * 1103515245 + 12345) % 2147483648;
        }

        F.resize(1<<18);
        ll ans = 0;
        REP(x, MOD) {
            fill(ALL(F), 0);
            int bal = N;
            REP(i, N) {
                fenwick_add(bal, 1);
                if (As[i] == x) {
                    ++bal;
                } else {
                    --bal;
                }
                ans += fenwick_sum(bal - 1);
            }
        }
        return ans;
    }

    long long getCount(int n_, int seed_, int m_) {
        ll n = n_;
        ll seed = seed_;
        ll MOD = m_;

        return solve(n, seed, MOD);
    }
};