Educational Codeforces Round 98 E - Two Editorials

難しい、全然分からんかった。

リンク

codeforces.com

問題概要 (雑)

長さ の区間があり、 個の区間が の形式で与えられる。これらの区間を つのグループに分けることを考える。(各区間はただ一つのグループに属し、複数個には属さない。) 各グループでは長さ の区間を一つだけ設置して、この区間と 番目の区間との重複している長さを とする。このときの を最大化する。

制約

(考察)

愚直解として、 つの区間をどこにするか決めて、毎回 個の区間をどちらかに割り当てるという処理が考えられる。
これは、 で間に合わない。

以下の気付きが重要である。
長さの等しい つの区間 があるとき、 番目の区間がどちらに属した方が得であるか。
これは、それぞれの区間の中央値を比較すればよく、中央値が近い方を選択する。
他方を選んでも得をしないことから示せる。(らしい)
これ天才すぎる、全然気付かなかった。

この事実を活かすために、 個の区間を中央値に関連する値 () でソートしておく。
この数列における区切り線を全探索する。
区切り線より左側は中央値が左側の区間に、区切り線より右側は中央値が右側の区間に属する、と考えることができる。
区切り線を固定したときに、長さ の区間をどこに設置すればよいかは、各グループで累積和を取っておいて全探索すればよい。
ここまでの処理は、 で実現でき、制限時間内に答えを求めることができる。

難しすぎて困った。

コード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using P = pair<int, int>;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}

int main(){
    int n, m, k;
    cin >> n >> m >> k;
    vector<P> sections(m);
    for(auto& [l, r] : sections){
        cin >> l >> r;
        --l;
    }
    
    // (l + r) 昇順にソート
    sort(sections.begin(), sections.end(), [](const P& a, const P& b){
        return a.first + a.second < b.first + b.second;
    });
    
    // 区間を prefix, suffix の 2 つのグループに分ける
    vector<int> prefix(n + 1), suffix(n + 1), prefix_sum(n + 1), suffix_sum(n + 1);
    int ans = 0;
    
    // 区切り線を全探索
    for(int i = 0; i < m; ++i){
        // 位置 j を横切る区間が何個あるかを imos 法で求めておく
        for(int j = 0; j <= n; ++j) prefix[j] = suffix[j] = 0;
        for(int j = 0; j < i; ++j){
            auto [l, r] = sections[j];
            prefix[l] += 1;
            prefix[r] -= 1;
        }
        for(int j = i; j < m; ++j){
            auto [l, r] = sections[j];
            suffix[l] += 1;
            suffix[r] -= 1;
        }
        for(int j = 0; j < n; ++j){
            prefix[j + 1] += prefix[j];
            suffix[j + 1] += suffix[j];
        }
        
        // 重複する長さの合計を累積和から取得できるようにする
        prefix_sum[0] = suffix_sum[0] = 0;
        for(int j = 0; j < n; ++j){
            prefix_sum[j + 1] = prefix_sum[j] + prefix[j];
            suffix_sum[j + 1] = suffix_sum[j] + suffix[j];
        }
        
        // 長さ k の区間を置く場所を全探索
        int prefix_cnt = 0, suffix_cnt = 0;
        for(int j = 0; j + k <= n; ++j){
            chmax(prefix_cnt, prefix_sum[j + k] - prefix_sum[j]);
            chmax(suffix_cnt, suffix_sum[j + k] - suffix_sum[j]);
        }
        
        chmax(ans, prefix_cnt + suffix_cnt);
    }
    
    cout << ans << '\n';
}

雑記

雑なメモなので、あとで修正したりするかもしれない。

Educational Codeforces Round 98 D - Radio Towers

こういう問題を素早く解けるようになりたい。

リンク

codeforces.com

問題概要

の 個の街がある。街 には の確率で電波塔が設置される。電波塔のパワー は自由に設定でき、距離が 未満の街に電波が供給される。街 と街 には電波が供給されず、 に重複なしで電波が供給されるように電波塔が設置される確率を で求める。

制約

考察

設置する個数を固定するなどが浮かぶが、今回は素直な DP で解くことができる。

電波が到達していない連続する区間の長さが のときの条件を満たす電波塔の設置方法の総数
と定義する。

これがどこから遷移されたかを考えるために、最初の行動で場合分けをする。
この問題の場合、左から見て一番最初に置かれる電波塔がどこであるかで場合分けする。

例えば、 の場合は以下のようになる。

真ん中の、左から つ目の街に電波塔を設置する場合を考えてみる。
街 に電波を供給する必要があるため、パワーは にしなければいけない。( 街 には電波を供給しない。)
すると、街 まで電波は供給される。
残りは街 と街 に電波を供給するように電波塔を設置しなければいけないが、これは ] に等しい。

一般に、

である。
愚直にやると更新に かかってしまうが、累積和を取っておくことで更新が でできる。
累積和は 上で取っていく。

求めるものは確率であるので、

を出力すればよい。

コード

#include <iostream>
#include <vector>
using namespace std;

constexpr int mod = 998244353;
struct mint { /* mod 上での演算を定義 */ };

int main(){
    int n;
    cin >> n;
    
    vector<mint> dp(n + 1), sum(n + 1);
    dp[0] = dp[1] = 1;
    sum[0] = sum[1] = 1;
    
    for(int i = 2; i <= n; ++i){
        // dp[i] = dp[i - 1] + dp[i - 3] + ...
        //       = sum[i - 1]
        dp[i] = sum[i - 1];
        
        // mod2 における累積和を取る
        sum[i] = sum[i - 2] + dp[i];
    }
    
    cout << dp[n] / mint(2).pow(n) << '\n';
}

AGC049 A - Erasing Vertices

リンク

atcoder.jp

問題概要

頂点有向グラフが与えられる。
グラフの頂点をランダムに選び、選んだ頂点から到達可能な頂点を消す作業を、グラフが空になるまで繰り返す。
このときの操作回数の期待値を求める。

制約

(考察)

同じような考え方を用いる問題を解いたことあるけど、解けなかった、反省。
強連結成分分解を長時間考えてしまったが、問題の配置的に本当にそうかと疑っていたら、案の定違った。

まず、期待値の線形性を用いて問題を言い換える。
本番中この考え方には至ったのだが、確率変数よく分かっていないので、考えきれなかった。

操作回数の確率変数を とする。
この期待値を と表すと、これが求める期待値である。

期待値には線形性があり、
(和の期待値) (期待値の和)
が成り立つ。
これは確率変数 があるとき、

が成り立つというものである。
この性質を使うために、操作回数の部分を言い換える。

操作中に頂点 を選ぶか選ばないかを表す確率変数を とする。
選ぶときは 、選ばないときは である。
このとき、操作回数 は


と表せる。

あとは、期待値の線形性より


であるので、頂点が選ばれる期待値を個別に求められればよい。

これは、頂点 が操作中に選ばれる確率に等しい。
操作中に頂点 を選ぶ確率を で表すとき、


になるからである。
この確率は、初期状態のグラフで頂点 に到達可能な頂点数を とすると、

である。
これは、操作中に頂点 が選ばれるのは、 個の頂点の中で頂点 が一番最初に選ばれるときだからである。
個の頂点の中で頂点 以外が最初に選ばれると、頂点 は消滅してしまい選ばれることはない。
(これに似た考えを用いる問題 : B - Removing Blocks)

あとは、到達可能な頂点数を求められればよい。
制約がゆるいので方法はいろいろある。

• 各頂点から DFS, BFS
• ワーシャルフロイド (実装が一番楽)
• 強連結成分分解からグラフを作り変える

ステップをまとめると、

• 操作回数の期待値を、各頂点が操作中に選ばれる回数の期待値に言い換える。
• 頂点が選ばれる期待値 ( 確率) は、到達可能な頂点数に等しいので、到達可能性を調べる。

コード

#include <iostream>
#include <iomanip>
using namespace std;

int g[105][105];

int main(){
    int N;
    cin >> N;
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            char ch;
            cin >> ch;
            g[i][j] = ch - '0';
        }
    }
    for(int i = 0; i < N; ++i)  g[i][i] = 1;
    
    for(int k = 0; k < N; ++k){
        for(int i = 0; i < N; ++i){
            for(int j = 0; j < N; ++j){
                g[i][j] |= g[i][k] & g[k][j];
            }
        }
    }
    
    double ans = 0.0;
    for(int i = 0; i < N; ++i){
        int V = 0;
        for(int j = 0; j < N; ++j){
            V += g[j][i];
        }
        ans += 1.0 / V;
    }
    
    cout << fixed << setprecision(15);
    cout << ans << endl;
}

雑記

B のみの 1 完で、頭の中で問題の条件がすり替わっていて時間を食った。
黄パフォで稼いだレートを日々溶かしていて悲しい...

HTTF2021 は就活枠で本戦に進めるらしい。
本戦に進むようなことはないと思っていたので嬉しい！
マラソンはほとんどやっていないので、本戦で戦えるようにちゃんと勉強しないとな...

マスコットの片付け (Mascots - JOI 13 春合宿 2-2)

問題へのリンク

atcoder.jp

問題概要

の収納スペースと、既に片付けられている 個のマスコットの配置が与えられたとき、残りのマスコットの片付ける方法を で割った余りを求める。
ただし、途中で長方形ができるだけ多くなるように並べる。

制約

考察

長方形が完成していなければ、まず長方形を完成させるような並べ方を考える。
これは、最初にできる長方形を求めて、まだ埋まっていないところを埋めていけばよい。
この並べ方は、長方形の内部で埋まっていない部分が 個のとき、 通りある。

長方形が完成したあとは、それを縦方向・横方向に伸ばしていくようにして並べていく。

イメージは上図の通りで、どう求めるかを一旦置いておくと、
dp[上方向の残りの行][下方向の残りの行][左方向の残りの列][右方向の残りの列]
のように dp テーブルを設定すれば求めることができる。
ただ、これは計算量が となるので厳しい。

行方向と列方向をまとめればキーを減らすことができ、
dp[残りの行][残りの列]
と定義できる。
これで計算量を におさえることができる。

今できている長方形の縦の長さを 、横の長さを とする。
長方形を縦方向に伸ばすときの方法は 通りあり、 となる。
同様に、横方向に伸ばすときの方法は 通りあり、 となる。
この要領で dp テーブルを埋めることができる。

この方法はどちらの方向に長方形を伸ばすかで遷移しているので、縦方向と横方向は区別できている。
ただ、上下方向と左右方向の区別はできていないので、最後にその部分の帳尻を合わせる。
テーブルに書かれた値は、縦方向と横方向のあらゆる順番における並べ方の総数であるが、このすべてについて縦方向と横方向は独立に考えることができる。
まず、縦方向について考える。
上方向の残り行数が 個、下方向の残り行数が 個であるとすると、上下の並べ方は ↑ を 個と ↓ を 個の並べ方に帰着できる。
これは二項係数で求めることができるので、前計算しておき二項計算を で求められるようにしておく。( 二項係数の求め方については割愛。)
この前計算により、階乗も で求まる。
横方向についても同様である。

計算量は、二項係数の前計算がボトルネックで、。
ただし、 である。

コード

#include <iostream>
#include <vector>
using namespace std;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

constexpr int mod = 1000000007;

struct modint{ /* modint の定義 */ };

template<typename T>
struct Combination{
    // 二項係数の前計算
    // fact(X) で X! の値を返す
    // (n, k) で nCk の値を返す
};

int main(){
    int R, C, N;
    cin >> R >> C >> N;
    int sx = R, sy = C, tx = 0, ty = 0;
    for(int i = 0; i < N; ++i){
        int x, y;
        cin >> x >> y;
        --x, --y;
        chmin(sx, x);
        chmin(sy, y);
        chmax(tx, x);
        chmax(ty, y);
    }
    ++tx, ++ty;
    int H = tx - sx, W = ty - sy;

    // 二項係数の前計算
    Combination<modint> comb(R * C);
    // 長方形を完成させる
    modint ans = comb.fact(H * W - N);
    
    // 縦方向と横方向を区別して dp の計算
    vector<vector<modint>> dp(R - H + 1, vector<modint>(C - W + 1));
    vector<vector<bool>> decided(R - H + 1, vector<bool>(C - W + 1, false));
    dp[0][0] = 1;
    decided[0][0] = true;
    auto MemoRec = [&](auto&& self, int i, int j) -> modint {
        if(decided[i][j])   return dp[i][j];
        modint res = 0;
        if(i > 0)   res += self(self, i - 1, j) * comb.fact(C - j);
        if(j > 0)   res += self(self, i, j - 1) * comb.fact(R - i);
        decided[i][j] = true;
        return dp[i][j] = res;
    };
    ans *= MemoRec(MemoRec, R - H, C - W);

    // 上下方向と左右方向の区別
    ans *= comb(R - H, sx) * comb(C - W, sy);

    cout << ans << endl;
}

雑記

よくありそうな計算量の削減だが、解くのに時間がかかった。
数え上げの問題を素早く解けるようになりたい。
現状、解けても時間がかかりすぎて全然使い物にならない。

AGC は手も足も出なくて悲しすぎる…
Trie は最近理解したんだけど、よく分からなくなってしまった。

漸化式の一般項の値を高速に求める

隣接 項間漸化式の一般項 の値を高速に求める手法を最近知ったのでメモをしておく。
一般項を求めるのは、 行列で行列累乗を用いると、 で求めることができる。
ただ、きたまさ法と呼ばれる手法を用いれば、 で求めることができる。

表記など怪しいので、詳しくは参考文献を見ることをお薦めする。

項の初期値と、隣接 項の関係が以下のように与えられているとする。


ただし、 は初期値のベクトル、 は と隣接 項間の関係を書き表すための係数ベクトルである。( 一般的な表記とは異なっているので注意。)

ここで、次のような 次元ベクトル を導入する。

このとき、 は以下のように書けるものと定義する。

のとき、 である。

を求めるために、 を求めることを考える。
が分かっているときに、 が求めることができれば、ダブリングの要領で、 から始めて 回の計算で を求めることができる。

まず、 が分かっているとき、 は で求めることができる。
は 項前から 個取った項との関係を表すものであるので、

のとき、すべての の添え字に をして、

これに の式を代入してまとめると、

すなわち、

となる。

次に、 が分かっているときに、 を求めることを考える。

のとき、すべての の添え字に をすると、

となるので、
の 個のベクトルが分かっていれば、 を求めることができる。
個のベクトルは、 から始めて で求めることができる。
各計算は前述の方法と同様 であるので、合計で となる。
そして、 の計算では、各ベクトルから の係数、 の係数... を足し込めばいいので、これも で求めることができる。

よって、全体で の計算量で、 を求めるための係数ベクトルが求まる。

コード

#include <iostream>
#include <vector>
using namespace std;

template<typename T>
struct Kitamasa{
    vector<T> a;    // 初期値ベクトル
    vector<T> d;    // 係数ベクトル
    int k;
    
    Kitamasa(vector<T>& a, vector<T>& d) : a(a), d(d), k((int)a.size()) {}
    
    // a_n の係数ベクトルを求める
    vector<T> dfs(int64_t n){
        if(n == k)  return d;
        
        vector<T> res(k);
        if(n & 1 || n < k * 2){
            vector<T> x = dfs(n - 1);
            for(int i = 0; i < k; ++i)  res[i] = d[i] * x[k - 1];
            for(int i = 0; i + 1 < k; ++i)  res[i + 1] += x[i];
        }
        else{
            vector<vector<T>> x(k, vector<T>(k));
            x[0] = dfs(n >> 1);
            for(int i = 0; i + 1 < k; ++i){
                for(int j = 0; j < k; ++j)  x[i + 1][j] = d[j] * x[i][k - 1];
                for(int j = 0; j + 1 < k; ++j)  x[i + 1][j + 1] += x[i][j];
            }
            for(int i = 0; i < k; ++i){
                for(int j = 0; j < k; ++j){
                    res[j] += x[0][i] * x[i][j];
                }
            }
        }

        return res;
    }

    // a_n を求める
    T calc(int64_t n){
        vector<T> x = dfs(n);
        T res = 0;
        for(int i = 0; i < k; ++i)  res += x[i] * a[i];
        return res;
    }
};

関連問題

T - フィボナッチ

参考文献

きたまさ法メモ - よすぽの日記
TDPC T - フィボナッチ - ferinの競プロ帳

雑記

世の中天才しかいないな…

ABC106 D - AtCoder Express 2

問題へのリンク (問題内容は省略)

atcoder.jp

考察

想定解ではなかったが、汎用性がありそうなのでメモしておく。

各クエリに対して効率的に求めたいが、 をそのままにして考えるのは難しい。( 例えば、 について昇順でソートしても、 について単調性がある保証がないので、二分探索などができない。)

列車とクエリの区間をまとめて について昇順にソートしてみる。( 思考過程も書きたかったが省略… )
が等しいときはクエリが先にくるようにしておく。
ソートされた順にデータを見ると、クエリに訪れたときに、クエリ以降の列車で条件を満たすのは、右端がクエリの右端以下になっているものである。
昇順に並んでいるので、左端に関しては考慮する必要がない。
この条件を満たす個数を求めて保存していけばよい。
個数は、右端を添え字として列車の個数を累積和で持っておくことで求めることができる。
データを順に見ているときに、列車に関する情報であるときは、以降で現れるクエリで考慮しないように減算しておく。
この解き方だと、区間和取得と一点更新が効率的に行えるデータ構造が必要であるが、Segment Tree や Binary Indexed Tree (Fenwick Tree) を用いればよい。

計算量は となる。

ソートによって左端を考慮する必要なくすことで、右端を点としてみることを可能にするという考え方を、すぐにアウトプットできるようにインプットしておくべきだと感じた。

コード

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;

template<typename T>
struct BinaryIndexedTree{
    vector<T> data;
    int sz;

    BinaryIndexedTree(int n){
        sz = n + 1;
        data.assign(sz, 0);
    }

    void add(int i, T x){
        ++i;
        while(i < sz){
            data[i] += x;
            i += i & -i;
        }
    }

    // [0, i] の区間和
    T sum(int i){
        T res = 0;
        ++i;
        while(i > 0){
            res += data[i];
            i -= i & -i;
        }
        return res;
    }

    // [l, r) の区間和
    T sum(int l, int r){
        return sum(r - 1) - sum(l - 1);
    }

    // val 以上を満たす 0-indexed の位置を返す
    int lower_bound(T val){
        // if(val <= 0)    return -1;
        int res = 0;
        int n = 1;
        while(n < sz)   n <<= 1;
        for(int k = n >> 1; k > 0; k >>= 1){
            if(res + k < sz && data[res + k] < val){
                val -= data[res + k];
                res += k;
            }
        }
        return res;
    }
};

int main(){
    int n, m, q;
    cin >> n >> m >> q;
    vector<tuple<int, int, int>> table;
    // bit.data[i] := 右端が i である列車の個数
    BinaryIndexedTree<int> bit(n + 1);
    for(int i = 0; i < m; ++i){
        int l, r;
        cin >> l >> r;
        table.emplace_back(l, q, r);
        bit.add(r, 1);
    }
    for(int i = 0; i < q; ++i){
        int l, r;
        cin >> l >> r;
        table.emplace_back(l, i, r);
    }
    // 列車とクエリを左端昇順ソート (左端が同じものはクエリが先にくるようにする。)
    // こうすることで、クエリの区間に対して左端がはみ出たものを考慮せずに済む。
    sort(table.begin(), table.end());

    vector<int> ans(q);
    for(auto tup : table){
        int i = get<1>(tup);
        // 列車であれば、以降は利用しないので減算しておく。
        if(i == q)  bit.add(get<2>(tup), -1);
        // クエリであれば、[l, r] に含まれる列車の個数を取得する。
        else{
            int l = get<0>(tup), r = get<2>(tup);
            ans[i] = bit.sum(l, r + 1);
        }
    }
    for(int x : ans)    cout << x << '\n';
}

雑記

二次元平面上で考えることで の組を点で管理できる。
今回は の制約が小さいので、二次元累積和でこれを管理できる。
二次元で問題を捉える考え方が苦手なのでものにしたいものである。
何回も解き直してるんだけど、スラスラと解けるようにはなかなかならないね。
競プロやってたら一日が終わっているが…？

ARC036 C - 偶然ジェネレータ

atcoder.jp

問題概要

'0', '1', '?' からなる長さ の文字列が与えられる。
'?' には、'0' または '1' が入れられる。
それを埋めた '0' と '1' からなる文字列の任意の連続部分列の中で '0' と '1' の個数の差が 以下となる文字列の個数を で割った余りを求める。

制約

(考察)

制約も小さいし、雰囲気は DP かと思ったけど、定義できないね。
最近見てる問題難しくて困った。

dp[ ][ ][ ] := 桁目から左方向に見たときの ('0' の個数 - '1' の個数) の最大値が , 最小値が であるときの通り数
と定義する。
が負になるときは、代わりに に遷移させる。
の場合も同様である。
この定義、正直あまり理解しきれていない。

自分の中では、現在地からどれだけ上または下に戻れるかという状態を持っていると解釈している。
例えば、文字列が "000110111" であったとき、お絵かきをしてみると、下図のようになる。

'1' のとき上方向、'0' のとき下方向に進んでいて、 と の遷移も書いてある。
(このお絵かきするなら、 と の定義は逆の方がよかったな…)
例えば、最終地点を見ると となっているが、これはその地点から左方向を見たときに、上方向には 、下方向には だけ進めるということを示している。

図を見ると分かるように、最終地点での が連続部分列で取り得る最大の差となるので、それが 以下となるものの合計を出力すればよい。

いやちょっとみんな纏め方うますぎるな、困る。

コード

modint の定義は長くなるので省略。
遷移では、 を超えてもそのまま計算させている。
超えるときは遷移させないのが普通な気がするが、 は短くはならなさそうなので、これでも多分大丈夫である。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

constexpr int mod = 1000000007;
struct modint{ /* modint の定義 */ };

// dp[i][j][k] := i 桁目から左方向を見たとき、('0'の個数 - '1'の個数)
//                の最大値が j, 最小値が -k である通り数
// y 軸で捉えると、i 桁目の現在の座標 y_{i} から、正方向に j, 負方向に k だけ進めるということを表している。 
// j + k が連続部分列最大の差になるので、j + k <= K を満たすものの合計が答えとなる
modint dp[305][305][305];

int main(){
    int n, K;
    string s;
    cin >> n >> K >> s;

    dp[0][0][0] = 1;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j <= i; ++j){
            for(int k = 0; j + k <= i; ++k){
                if(dp[i][j][k] == 0)    continue;
                
                if(s[i] == '0'){
                    dp[i + 1][j + 1][max(0, k - 1)] += dp[i][j][k];
                }
                else if(s[i] == '1'){
                    dp[i + 1][max(0, j - 1)][k + 1] += dp[i][j][k];
                }
                else{   // s[i] == '?'
                    dp[i + 1][j + 1][max(0, k - 1)] += dp[i][j][k];
                    dp[i + 1][max(0, j - 1)][k + 1] += dp[i][j][k];
                }
            }
        }
    }

    modint ans = 0;
    for(int i = 0; i <= K; ++i){
        for(int j = 0; i + j <= K; ++j){
            ans += dp[n][i][j];
        }
    }
    cout << ans << endl;
}

参考文献

ARC 036 C - 偶然ジェネレータ - srupのメモ帳
ARC036 | en30's blog

雑記

5 月、どうして...