ひらめの日常

日常のメモをつらつらと

AtCoder: ABC140-D Face Produces Unhappiness (400)

問題はこちら

atcoder.jp

長さ  N の文字列  S が与えられる。L は自分の左に L が来た時、R は自分の右に R が来た時、幸福になるという。以下の操作を  K 回以下繰り返して、幸福なものを最大いくつにできるか答えよ。

操作:  1 \leq l \leq r \leq N となる  l, r を選び、  [l, r] 内にある文字列を左右反転させ、方向も反転させる。

考え方

操作をする系は、その前後で何が変わるかを考えると良い(特に求める答えに関するもの)。今回の場合は、一回操作を行うたびに、その区間の両端の状態が変わる。 (いい加減こういうのに慣れたいですね...)

幸せになる数が増えるのは、LL, RR という並びが存在するときなので、操作をした時に内部の状態変化が答えに与える影響はない。しかし、両端とその隣の状態が変化し、最大でも +2 されることがわかる。

そこで、+2 を貪欲にやる方法を考えてみる。すると、同じものが続いている区間を反転すれば、両端が新しく条件を満たし、答えが +2 されると考えられる。この時点で、順番が反転することは考えなくてよくなり、向きが反転することだけ考えればよくなる。

  • LL RR LL RLL LL LL R
  • R LLLL RR RRRR R

注意するのは、以下のような時で、 +1 しかされない。

  • L RRRRRR RRRRR
  • L RRRRRL LLLLL

しかし、 +1 の操作は一回しか起こり得ないかつ、答えとしてありえる最大値 - 1 から最大値に移行する時に使用すると考えることができる。(つまり一番最後に行う。)

これらより、答えは 「min(もともと連続で続いている個数 + 2 * k, n - 1)」になる。

解答

考察が終わればいたって簡単。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

int main() {

    ll n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    ll ans = 0;
    rep(i, n - 1) {
        if (s[i] == s[i + 1]) ans++;
    }
    ans += 2 * k;
    cout << min(n - 1, ans) << '\n';
    return 0;
}

Submission #7416033 - AtCoder Beginner Contest 140

Codeforces Round #582 (Div. 3) G. Path Queries

問題はこちら

codeforces.com

頂点数  n の木が与えられる(木なので辺の数は  n - 1)。

以下のような  m 個のクエリ  q _ 1, q _ 2, ..., q _ i が投げられるので、それぞれに対する答えを出力せよ。

  • 求めるものは以下を満たす頂点  u,  v,  u \lt v のペアの個数。
  • 頂点  u v を結ぶパスの中で、辺の最大の重みが  q _ i を超えない。

考え方

 q _ i 以下のみの辺で連結になっている頂点数  n _ i が分かれば、その中を結ぶ頂点のペアの個数は  n _ i (n _ i - 1) /2 だとわかる。よって、重み  q _ i 以下の辺が出てきたら、その二つの頂点を同じグループに入れればいい。

このようなグループの構成は Union find木 を使えばいいということがわかる。

愚直に全てのクエリに対して順番にやると、毎回 Union find木を1から構成する必要があり、間に合わない。そこで、この問題を思い出す。

、クエリを先に読んでおいて、wが大きい順にクエリを処理する。こうすることで、既に存在する木に新たに条件を満たす辺を加えていくだけでよくなる。

ABC040-D 道路の老朽化対策について (500) - ひらめの日常

今回のポイントとして、 q _ i が小さい時に条件を満たすような頂点のペアは、それよりも大きい  q _ i の時も条件を満たし、同じグループに属するということがある。なので、クエリを小さい順に処理する。こうすることで、上記の引用部分と同様に、すでに存在する木に新たに条件を満たす辺を加えていくだけでよくなる。

また、個数をカウントする方法も工夫が必要で累積和的に管理する。 u, v が新たにグループになる時、今までの  u, v が属するそれぞれのグループで作れるペアの個数を引き、新たに作られたグループで作れるペアの個数を足す。

ペア u, v が新たに条件を満たす時。

count -= unionfind.size(u) * (unionfind.size(u) - 1) / 2;
count -= unionfind.size(v) * (unionfind.size(v) - 1) / 2;
unionfind.unite(u, v);
count += unionfind.size(u) * (unionfind.size(v) - 1) / 2;

解答

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

class UnionFind {
private:
    vector<ll> size; // グループに属する物の数.
public:
    vector<ll> par; // 親
    vector<ll> rank; // 木の深さ

    explicit UnionFind(unsigned int n) {
        par.resize(n);
        rank.resize(n);
        size.resize(n);
        rep(i, n) {
            par[i] = i;
            rank[i] = 0;
            size[i] = 1;
        }
    }

    // 木の根を求める
    ll find(ll x) {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = find(par[x]);
        }
    }

    // グループのサイズを求める.
    ll calc_size(ll x) {
        return size[find(x)];
    }

    // xとyの属する集合を併合
    void unite(ll x, ll y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (rank[x] < rank[y]) {
            par[x] = y;
        } else {
            par[y] = x;
            if (rank[x] == rank[y])rank[x]++;
        }
        size[x] = size[y] = size[x] + size[y];
    }

    // xとyが同じ集合に属するか否か
    bool is_same(ll x, ll y) {
        return find(x) == find(y);
    }
};

template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
using P = pair<ll, ll>;
using edge = pair<ll, P>;

int main() {

    ll n, m;
    cin >> n >> m;
    minpq<edge> que;
    rep(i, n - 1) {
        ll u, v, c;
        cin >> u >> v >> c;
        u--, v--;
        que.push(edge(c, P(u, v)));
    }
    vector<P> q(m);
    rep(i, m) {
        cin >> q[i].first;
        q[i].second = i;
    }
    sort(q.begin(), q.end());

    vector<ll> ans(m);
    UnionFind uf(n);
    ll cnt = 0;
    rep(i, m) {
        ll target = q[i].first, idx = q[i].second;

        while (!que.empty() && que.top().first <= target) {
            edge now = que.top();
            ll u = now.second.first, v = now.second.second;
            ll s1 = uf.calc_size(u), s2 = uf.calc_size(v);
            cnt -= s1 * (s1 - 1) / 2;
            cnt -= s2 * (s2 - 1) / 2;
            uf.unite(u, v);
            ll s3 = uf.calc_size(u);
            cnt += s3 * (s3 - 1) / 2;
            que.pop();
        }
        ans[idx] = cnt;
    }
    rep(i, m) cout << ans[i] << ' ';
    return 0;
}

Submission #59803208 - Codeforces

Codeforces Round #582 (Div. 3) D. Equalizing by Division

問題はこちら

codeforces.com

長さ  n の 配列  a が与えられる。一回の操作によって任意の要素一つ、  a_i を2で割って切り捨てることを行う。 (つまり、  a _ {i} :=\left\lfloor\frac{a _ i}{2}\right\rfloor

 k 個の等しい要素を  a 中で得るには、何回操作を行えばいいか、その最小値を求めよ。

考え方

全ての  a_i を、0になるまで割る2して、各値を得るまでにかかった作業回数を記録しておく。コードの方がわかりやすいと思うのでその部分を抜粋する。

while (a[i] > 0) {
    mp[a[i]].emplace_back(t);
    a[i] /= 2;
    t++;
}

そして、存在している全ての要素に対して以下を行う。

  • 素数 k よりも以上の場合は、要素をsortする。
  • その後、  k 番目までの必要回数の和を計算する。

以上を行なって、 k 個以上作ることのできる要素の最小操作回数を求め、それが答えとなる。

なぜこれで間に合うのか?

最初は、全ての要素に対して、各要素を得るための操作回数をsortするために間に合わないと思っていたがそんなことはなかった。

以下は簡略化のために  O(max(a)) = O(n) として話を進める。 まず、全ての要素数 O(nlog(n)) である。(一つの要素は2で割っていくので  log(n) 個存在し、それが  n 個あるため。)

次に、その各値に対応する操作回数をsortする部分だが、sortする対象の合計個数も高々  O(nlog(n)) 個である。よって、各値に対応する操作回数を全てsortしたとしても計算量は  O(xlog(x)), x = nlog(n) で抑えられ、時間内に間に合う。

基本的に、合計個数  n あるものを、それぞれ  A, B, C... 個を要素とするグループに分けたときを考える。計算量 O(n) 以上となる同じ操作hogeを各グループに対して行なった合計の計算量は、合計個数全てに対する計算量で抑えられる。つまり、  O(hoge(A)) + O(hoge(B)) + O(hoge(C)) + ...\ =\ O(hoge(n))

hogeの計算量が  O(log(n)) とかだと、グループに分けない方が計算量が小さいはず。今回は hoge に相当するのが sort なので、 O(n) 以上の計算量である。)

解答

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define each(i, mp) for(auto& i:mp)

int main() {

    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    unordered_map<ll, vector<ll>> mp;
    rep(i, n) {
        ll t = 0;
        while (a[i] > 0) {
            mp[a[i]].emplace_back(t);
            a[i] /= 2;
            t++;
        }
    }

    ll ans = 1e18;
    each(e, mp) {
        vector<ll> times = e.second;
        if (times.size() >= k) {
            sort(times.begin(), times.end());
            ll now = accumulate(times.begin(), times.begin() + k, 0LL);
            ans = min(ans, now);
        }
    }
    cout << ans << '\n';
    return 0;
}

Submission #59801874 - Codeforces

AtCoder: ABC123-D Cake 123 (400)

問題はこちら

atcoder.jp

美味しさは以下のように表される。

  •  X 種類のケーキ  A _ 1, A _ 2, ..., A _ X
  •  Y 種類のケーキ  B _ 1, B _ 2, ..., B _ Y
  •  Z 種類のケーキ  C _ 1, C _ 2, ..., C _ Z

この時、それぞれのケーキ美味しさの合計として大きい順に  K 個出力しなさい。

 \begin{array}{l}{1 \leq X \leq 1000}, \ {1 \leq Y \leq 1000}, \ {1 \leq Z \leq 1000}, \ {1 \leq K \leq \min (3000, X \times Y \times Z)}\end{array}

考え方

 X \times Y \times Z の全探索をすると  O(10 ^ 9) のループが周り、さらに大きい順に出力するので間に合わない。そこで、計算量を落とすことを考える。

いろんな解法があり、勉強になったので3つほど載せておく。元となる考え方は K が最大で3000 というところに注目するところにある。

解答1 - 解の候補を絞る

 A B の組み合わせを  X \times Y 分だけ全列挙すると、 O(10 ^ 6) となるので、sortしても大丈夫。この配列を  A \times B とおく。

大きい方から  K 個ということは、以下が成り立つ。

  •  A \times B からは最大でも  K 個使われる。
  •  C からは最大でも  K 個使われる。

よって、それぞれの配列の大きい方から  K ずつだけループを回して、大きい順に値を保持し、最後にsortして  K 個分出力すれば良い。計算量はここのsortがボトルネックとなって、  O(K ^ 2 \log(K))

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vl = vector<ll>;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define all(obj) (obj).begin(), (obj).end()

int main() {
    ll x, y, z, k;
    cin >> x >> y >> z >> k;
    vl a(x), b(y), c(z);
    rep(i, x) cin >> a[i];
    rep(i, y) cin >> b[i];
    rep(i, z) cin >> c[i];

    vl ab;
    rep(i, x) rep(j, y) ab.emplace_back(a[i] + b[j]);
    sort(all(ab), greater<>());
    sort(all(c), greater<>());

    vl ans;
    rep(i, min(k, x * y)) rep(j, min(k, z)) ans.emplace_back(ab[i] + c[j]);
    sort(all(ans), greater<>());

    rep(i, k) cout << ans[i] << '\n';

    return 0;
}

Submission #7171632 - AtCoder Beginner Contest 123

解答2 - 貪欲とpriority_queueを使う

 A, B, C をそれぞれ大きい順にsortしておくとする。

最大値は  A _ 0 + B _ 0 + C _ 0 である。この次に大きいのはどれかということを考える。しかし、一意に定まりそうではないので候補を絞ることにする。すると、次の候補は以下の3つであるということがわかる。

  •  A _ 1 + B _ 0 + C _ 0 A のindexを一つだけ進めた。
  •  A _ 0 + B _ 1 + C _ 0 B のindexを一つだけ進めた。
  •  A _ 0 + B _ 0 + C _ 1 C のindexを一つだけ進めた。

なので、現在の最大値をpopした上で、これらを全て priority_queue にpushする。すると、次はtopにあるものが2番目に大きいものとなり、順に大きいものをpopしていくことができる。計算量は、priority_queue からpopする回数が  K 回、上記のように候補を3つpushする回数が  3K 回なので、 O(K log(K)) で間に合う。

ここで実装上の注意点は以下のようになる。

  • priority_queue にそれぞれのindexも含めて管理する。なぜなら、popした後にindexを一つ進める作業が必要になるため、和の値とそれぞれのindexの情報が必要。
  • 一度見たindexの和の値は priority_queue にpushしないように気をつける。例えば  A _ 1 + B _ 0 + C _ 1 は以下の二つのものから到達可能であり、重複して出力してしまう可能性があるからだ。
    •  A _ 1 + B _ 0 + C _ 0 から、 C のindexを増やした時。
    •  A _ 0 + B _ 0 + C _ 1 から、 A のindexを増やした時。

この辺の実装は以下の記事を参考にして実装させていただいた。

drken1215.hatenablog.com

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vl = vector<ll>;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define all(obj) (obj).begin(), (obj).end()

using data = pair<ll, vl>;

int main() {

    ll x, y, z, k;
    cin >> x >> y >> z >> k;
    vl a(x), b(y), c(z);
    rep(i, x) cin >> a[i];
    rep(i, y) cin >> b[i];
    rep(i, z) cin >> c[i];
    sort(all(a), greater<>()), sort(all(b), greater<>()), sort(all(c), greater<>());

    priority_queue<data> ans;
    set<data> used;
    ans.push(data(a[0] + b[0] + c[0], vl({0, 0, 0})));
    while (k-- > 0) {
        auto now = ans.top();
        ans.pop();
        cout << now.first << '\n';
        ll ia = now.second[0], ib = now.second[1], ic = now.second[2];

        data tmp;
        if (ia + 1 < a.size()) {
            tmp = data(a[ia + 1] + b[ib] + c[ic], vl({ia + 1, ib, ic}));
            if (used.find(tmp) == used.end()) {
                used.insert(tmp);
                ans.push(tmp);
            }
        }
        if (ib + 1 < b.size()) {
            tmp = data(a[ia] + b[ib + 1] + c[ic], vl({ia, ib + 1, ic}));
            if (used.find(tmp) == used.end()) {
                used.insert(tmp);
                ans.push(tmp);
            }
        }
        if (ic + 1 < c.size()) {
            tmp = data(a[ia] + b[ib] + c[ic + 1], vl({ia, ib, ic + 1}));
            if (used.find(tmp) == used.end()) {
                used.insert(tmp);
                ans.push(tmp);
            }
        }
    }
    return 0;
}

Submission #7171780 - AtCoder Beginner Contest 123

解答3 - K個以上になる境目の値を二分探索

ここでも  A, B, C をそれぞれ大きい順にsortしておくとする。

 K 個以上になる美味しさの合計の境目を二分探索で探索」し、二分探索内での判定方法として「美味しさの合計が  p 以上であるものが  K 個以上あるかどうか調べる」方法を考える。

まず後者は、以下のように枝刈りをすれば  O(K ^ 2) の計算量で抑えられる。

auto solve = [&](ll p) -> bool {
    ll cnt = 0;
    rep(i, x) { // ここは最大でK回ループがまわる
        rep(j, y) { // ここから下は最大でK回ループがまわる
            rep(l, z) {
                ll val = a[i] + b[j] + c[l];
                if (val < p) break;
                if (++cnt >= k) {
                    return true;
                }
            }
        }
    }
    return false;
};

なぜか???それは、 A, B, C をそれぞれ大きい順にsortしてあるので、以下の操作をすることにより  y, z の二重ループが高々  K 回しか回ることがないからだ。

  • 合計が  p より小さいなら一番ネストの深いループを抜ける。
  • 合計が  p 以上なら、カウントを一つ増やし、 K 以上になったら関数をreturnする。

よって、二分探索内での判定は可能になった。

最後に、境目がわかった後にどうすれば良いのかを考える。この境目を  Border とする。

  • 合計が   Border 以上のものは  K 個以上ある。(が、最大で何個あるかどうかはわからない...!)
  • 合計が  Border + 1 以上のものは  K 個より少ない。

よって、以下のようにして上位  K 個を求めることで間に合う。

  • 合計が  Border + 1 以上のものを全部列挙する。 これは先ほどの二分探索内での判定方法をほとんど同じ。
  • この個数が  K 個よりも少なければ、残りの美味しさは全て  Border であるので、それをpushする。

計算量は、二分探索に  O(log(A _ {max} + B _ {max} + C _ {max})) 、枝刈りに  O(K ^ 2 ) より、  O(K ^ 2 log(A _ {max} + B _ {max} + C _ {max})) で間に合う。

この考え方は公式の解説を参考にした。
https://img.atcoder.jp/abc123/editorial.pdf

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define all(obj) (obj).begin(), (obj).end()

int main() {
    ll x, y, z, k;
    cin >> x >> y >> z >> k;
    vl a(x), b(y), c(z);
    rep(i, x) cin >> a[i];
    rep(i, y) cin >> b[i];
    rep(i, z) cin >> c[i];

    sort(all(a), greater<>()), sort(all(b), greater<>()), sort(all(c), greater<>());

    auto solve = [&](ll p) -> bool {
        ll cnt = 0;
        rep(i, x) { // ここは最大でK回ループがまわる
            rep(j, y) { // ここから下は最大でK回ループがまわる
                rep(l, z) {
                    ll val = a[i] + b[j] + c[l];
                    if (val < p) break;
                    if (++cnt >= k) {
                        return true;
                    }
                }
            }
        }
        return false;
    };

    ll s = -1, e = a[0] + b[0] + c[0] + 1;
    while (e - s > 1) {
        ll mid = (s + e) / 2;
        if (solve(mid)) s = mid;
        else e = mid;
    }
    vl ans;
    rep(i, x) {
        rep(j, y) {
            rep(l, z) {
                ll val = a[i] + b[j] + c[l];
                if (val < s + 1) break;
                ans.emplace_back(val);
            }
        }
    }
    while (ans.size() < k) ans.emplace_back(s);
    sort(all(ans), greater<>());
    for (auto val: ans) cout << val << '\n';
    return 0;
}

Submission #7171934 - AtCoder Beginner Contest 123

AtCoder: ABC136-E Max GCD (500)

問題はこちら

atcoder.jp

 A_1, A_2, ..., A_N から  i \neq j となる  A_i, A_j を選び、 A_i = A _ i + 1, A_j = A _ j - 1 とする。この時、 K 以下の操作回数で  A の最大公約数として考えられるもののうち、最大のものを求めよ。

考え方

step1 - 解の候補

まず、 A_i に+1して、 A_j に-1するという操作は、 A_i の値を一つ  A_j に移動する操作と考えることができる。

次に大事なのは、答えの候補は  A の和の約数 となること。これはなぜかを考えてみる。今、答えとなる最大の最大公約数を  x とする。

  • 約数であるという性質から、 A _ 1 \% x = A _ 2 \% x =...= A _ N \% x = 0
  • modの性質から、 (A _ 1 + A _ 2 + ... + A _ N ) \% x = 0
  • 今回の操作は片方に+1, もう片方に-1するだけなので、総和は操作終了後にも変わらない。
  • 以上より、答えの候補は  A の和の約数となる。

なので、ある最大公約数  x K 回以下の操作によって達成されるかをすべて確かめ、達成されるものの中で最大のものが答えとなる。

step2 - 達成可能かを確認する

 x で割ったあまりが小さい方(=  A_i)から、大きい方(=  A_j)へと渡すのが操作方法が少なくて良い方法だとわかる。 A _ i \% x = a _ i ,  A _ j \% x = a _ j ,  a _ i \lt a _ j とおく。(簡単にするため、二つの数字でやり取りすることで割り切れる場合を考えてみる。)

  •  a_i から  a_j へ渡して  x で割り切れるようにする時。操作回数は  max(a _ i, x - a _ j)
  •  a_j から  a_i へ渡して  x で割り切れるようにする時。操作回数は  max(a _ j, x - a _ i)
  •  a _ i \lt a _ j より、  max(a _ i, x - a _ j) \lt max(a _ j, x - a _ i)

よって、 x で割った余りを小さい順でsortして、インデックス i より小さい側を渡す側。インデックス i 以上を渡される側として、必要な操作回数が K 以下であれば満たすと判定すれば良い。

解答

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for(auto& i:mp)
#define all(obj) (obj).begin(), (obj).end()

/* ------------- ANSWER ------------- */
/* ---------------------------------- */
// 約数列挙
vector<ll> divisor(ll n) {
    vector<ll> res;
    for (ll i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            res.emplace_back(i);
            if (i != n / i) res.emplace_back(n / i);
        }
    }
    return res;
}

int main() {

    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    vector<ll> divs = divisor(accumulate(all(a), 0LL));

    ll ans = 0;
    each(e, divs) {
        vector<ll> mods(n);
        rep(i, n) mods[i] = a[i] % e;
        sort(all(mods));

        vector<ll> minus(n + 1);
        rep(i, n) minus[i + 1] = minus[i] + mods[i];

        vector<ll> plus(n + 1);
        repr(i, n) plus[i] = plus[i + 1] + e - mods[i];

        for (ll i = 0; i <= n; ++i) {
            if (max(plus[i], minus[i]) <= k) ans = max(ans, e);
        }
    }
    cout << ans << '\n';
    return 0;
}

Submission #7148617 - AtCoder Beginner Contest 136

AtCoder: 第一回日本最強プログラマー学生選手権-予選- D Classified (600)

問題はこちら

atcoder.jp

今回はほぼ解説放送と解説ブログを参考にした自分用のメモ。

考え方

JSC2019予選 - D 「Classified」 (600) - Mister雑記

[AtCoder 参加感想] 2019/08/25:JSC2019予選 | maspyのHP

  • 奇閉路が存在しないようにグラフを分割できれば良い。
  • 奇閉路が存在しないことは、二部グラフが構成できることと同値。
  • よって、完全グラフを二部グラフに分割することを考える。
  • なるべくたくさんの辺を取り除いていきたいので、最大の完全二部グラフを取り除いていくことを考える。
  • 完全グラフから完全二部グラフを取り除いていくと、残りの部分グラフはそれぞれ完全グラフを構成している。
  • よって、再帰的に完全グラフから完全二部グラフを構成していくことを繰り返せば良い。

解答

ほぼ写経コード。

残っている頂点を半分ずつに分割して、完全二部グラフを構成していく。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;

int main() {
    ll n;
    cin >> n;

    vvl level(n, vl(n));
    auto dfs = [&](auto &&f, ll l, ll r, ll lev) -> void {
        if (l + 1 == r) return;
        ll mid = (l + r) / 2;
        for (ll i = l; i < mid; ++i) {
            for (ll j = mid; j < r; ++j) {
                level[i][j] = lev;
            }
        }
        f(f, l, mid, lev + 1);
        f(f, mid, r, lev + 1);
    };
    dfs(dfs, 0, n, 1);
    for (ll i = 0; i < n - 1; ++i) {
        for (ll j = i + 1; j < n; ++j) {
            cout << level[i][j] << ' ';
        }
    }
    return 0;
}

AtCoder: 第一回日本最強プログラマー学生選手権-予選- C Cell Inversion (500)

問題はこちら

atcoder.jp

考え方

なんか自分で書いててもあまり納得感がないかもしれない... 記事を書いた後に自分がわかりやすかったものを参考として載せておきます。

misteer.hatenablog.com

step1 - 反転する操作の言い換え

まず、操作の順番を変えても答えは変わらないことに注意する。

任意の  [l, r] を選んでその区間を逆にする操作は、 [0, l-1] [0, r]に対してそれぞれ操作をすることと等価であることに注目する。

f:id:thescript1210:20190825021430j:plain:w600

step2 - それぞれの文字が影響を及ぼす範囲を整理

つまり、 i番目に存在する文字 s_iは、以下のように考えることができる。

  •  r として使った時は 自分を含めた 左側に影響を及ぼす。
  •  l として使った時は 自分を含めない 左側に影響を及ぼす。
  • s_iに影響を及ぼすのは、それよりも右側にある文字だがこれの数は一定。

=> 以上より、 i番目よりも右側に存在する文字によって反転させられたあと自分の文字を変更できるのは、自分を r として使うか、 lとして使うかのどちらかのみ ということになる。

すべての要素は2N個あり、自分よりも右側のものに影響を受ける場合のみ考えると、終了時には以下のような状態になる。

// 0-indexで考える

if index % 2 == 0 then 色が反対に
else 色はそのまま

上記の操作を終了した時に、色を全て "W" にするためには以下のように振り分ける。

  • "B" になっているものは  r として使う(自分を反転させるため)。
  • "W" になっているものは  l として使う(自分を反転させないため)。

step3 - 組み合わせ計算

 r は自分よりも左側にある使われていない  l の数分だけペアになる候補がある。 よって累積の lの数を数えておけばよく、疑似言語書くとこのようになる。

count = 1

for i in 2N:
  if is_right[i] == true:
    count *= left_count  
    left_count--

  else:
    left_count++

ただし rよりも左側にまだペアになっていない lがない時や、最終的に lが余ってしまう時は答えは0なので、実装時はそこにも注意する。

最後に、操作順だけの場合の数があるので、 N!をかけて出力する。

解答

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll mod = 1000000007;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

/* ------------- ANSWER ------------- */
/* ---------------------------------- */
ll factorial(ll n) {
    ll ans = 1;
    while (n > 1) {
        ans *= n;
        ans %= mod;
        n--;
    }
    return ans;
}


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

    n *= 2;

    vector<bool> is_right(n);
    rep(i, n) {
        if (i % 2 == 0 && s[i] == 'W') is_right[i] = true;
        if (i % 2 == 1 && s[i] == 'B') is_right[i] = true;
    }
    ll ans = 1;
    ll left_sum = 0;
    rep(i, n) {
        if (is_right[i]) {
            if (left_sum == 0) {
                cout << 0 << '\n';
                return 0;
            }
            ans *= left_sum;
            ans %= mod;
            left_sum--;
        } else {
            left_sum++;
        }
    }
    if (left_sum > 0) cout << 0 << '\n';
    else cout << ans * factorial(n / 2) % mod << '\n';
    return 0;
}

Submission #7126826 - Japanese Student Championship 2019 Qualification