NoiminのNoise

競技プログラミング (多め) とWeb (たまに) ,自然言語処理 (ブログではまだ)。

Educational Codeforces Round 74 E. Keyboard Purchase

問題: https://codeforces.com/contest/1238/problem/E

問題概要

小文字のアルファベットのうち最初の {\displaystyle m } 文字のみ (例えば{\displaystyle m = 3 } なら a と b と c のみ) からなり{\displaystyle \left| s \right| \leq 10^5 } を満たす文字列 {\displaystyle s } が与えられる.

ここで,小文字のアルファベットのうち最初の {\displaystyle m } 文字の順列 {\displaystyle t } を作る.

任意の {\displaystyle i \lt \left| s \right| } について,{\displaystyle s_{i} }{\displaystyle s_{i+1} }{\displaystyle t } 上で {\displaystyle d } 文字ぶん離れているとき,コストが {\displaystyle d } かかるとする.

{\displaystyle s } 全体での合計コストが最小になるように {\displaystyle t } を作るときの, {\displaystyle s } 全体での合計コストを求めよ.

解法概要

{\displaystyle s } において,文字{\displaystyle i } と 文字 {\displaystyle j } が隣り合っている回数を {\displaystyle \mathit{cnt}_{i, j} } と置く.

{\displaystyle t } を完成させてから全体のコストの合計を求める式は,{\displaystyle \left| t \right| = m } であることから

{\displaystyle \sum_{i=0}^{m-2} \sum_{j=i+1}^{m-1} \mathit{cnt}_{i, j} (j-i) }

これを,全体のコストの合計に対する {\displaystyle t_i } の寄与に着目して変形すると

{\displaystyle \sum_{i=0}^{m-1} i (\sum_{j=0}^{i-1} \mathit{cnt}_{i, j} -  \sum_{j=i+1}^{m-1} \mathit{cnt}_{i, j}) }

変形後のコスト計算式を用いれば, {\displaystyle i } 文字目を決めたときのその文字の寄与は, {\displaystyle \mathit{cnt}_{i, j} } を事前計算しておけば {\displaystyle O(m) } で求められる.したがって,1文字目から順に決めていく bitDP で最小コストを求めることができる.

ソースコード

#include <iostream>
#include <vector>
#include <string>

using namespace std;

using ll =  long long;

constexpr ll INF = 1LL<<60;

/*
 * こちらのページの,ビットを数えるアルゴリズムのバージョン5をお借りしました
 * http://www.nminoru.jp/~nminoru/programming/bitcount.html
 */
inline int count_bit(unsigned  int n) {
    n = (n &  0x55555555) + (n >>  1  &  0x55555555);
    n = (n &  0x33333333) + (n >>  2  &  0x33333333);
    n = (n &  0x0f0f0f0f) + (n >>  4  &  0x0f0f0f0f);
    n = (n &  0x00ff00ff) + (n >>  8  &  0x00ff00ff);
    return (n &  0x0000ffff) + (n >>  16  &  0x0000ffff);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    vector<vector<ll>> a(m, vector<ll>(m, 0));
    for(int i=0;i<n-1;++i) {
        ++a[s[i]-'a'][s[i+1]-'a'];
        ++a[s[i+1]-'a'][s[i]-'a'];
    }

    vector<ll> dp(1<<m, INF);
    dp[0] = 0;
    for(unsigned int i=0;i<(1<<m);++i) {
        if(dp[i] == INF) continue;
        // 立っているビットの数
        int set_bit_cnt = count_bit(i);
        // これだと TLE でした……こっちの方が速いと思っていたのに
        // int set_bit_cnt = __builtin_popcount(i);

        for(int j=0;j<m;++j) {
            if(i & (1<<j)) continue;
            // 集合 i に文字 j を追加する
            ll new_cost = dp[i];
            for(int k=0;k<m;++k) {
                if(j == k) continue;
                if(i & (1<<k)) new_cost += a[k][j] * set_bit_cnt;
                else new_cost -= a[k][j] * set_bit_cnt;
            }
            dp[i|(1<<j)] = min(dp[i|(1<<j)], new_cost);
        }
    }

    cout << dp[(1<<m) - 1] << endl;
}

所感

C の読解で破滅していたので E は全く読んでなかった.

制約的に,{\displaystyle O(n^2 2^m) } (で合ってますか?) が通るとは思わなかった.まあこれがわかっても解けなかったんだけど…….

Codeforces Round #589 Div. 2 E. Another Filling the Grid

問題: https://codeforces.com/contest/1228/problem/E

公式解説: https://codeforces.com/blog/entry/70162

問題概要

{\displaystyle n \times n } のグリッドの各マスに,{\displaystyle 1} 以上 {\displaystyle k ( \leq {10}^9 ) }以下の整数値を書いていく.すべての行の最小値が 1 かつすべての列の最小値が 1 であるような整数値の書き方の通り数を {\displaystyle {10}^9 + 7 } で割ったものを求めよ.

解法概要

問題の条件は結局「各行各列に 1 つ以上 1 が含まれる」と等価なので,以下はこの条件で考える.

次のような dp を考える.

{\displaystyle dp_{i, j}  = i} 行目まですべての列を埋めたとき, 1が 1 つでも入っているような列が {\displaystyle j } 個ぴったりあるような埋め方の通り数

{\displaystyle i-1 } 行目までで {\displaystyle n } 列中 {\displaystyle j_1 } に 1 が含まれていて, {\displaystyle i } 行目までだと {\displaystyle n } 列中 {\displaystyle j_2 } (ただし {\displaystyle j_1 \leq j_2 }) に 1 が含まれているような埋め方の通り数は,次のように考えられる.

  • {\displaystyle i-1 } 行目までで 1 が含まれず,{\displaystyle i } 行目で 1 が含まれる列の選び方は{\displaystyle {}_{n-j_1} C_{j_2-j_1} } 通り
  • {\displaystyle i-1 } 行目までで 1 が含まれているような列は{\displaystyle i } 行目で何を選んでもよい.つまり {\displaystyle k } 種類の値が入りうる.
  • {\displaystyle i-1 } 行目までで 1 が含まれず,{\displaystyle i } 行目で 1 が含まれない列は1 以外の値を選ばなければならない.つまり {\displaystyle k-1 } 種類の値が入りうる.
  • {\displaystyle j_1 = n } のときはすでにすべての列に 1 が含まれるが,{\displaystyle i } 行目も少なくとも 1 つ 1 を含まなければならない.

これらのことから,

{\displaystyle dp_{i, j}  = \sum_{j^\prime = 1}^{j} \left( dp_{i-1, j^\prime} \times {}_{n-j} C_{j^\prime-j}  \times k^{j^\prime} \times (k-1)^{n-j} \right) - dp_{i-1, j} \times (k-1)^n }

が成り立つ.

あとは式をそのまま実装すれば良いのだが,{\displaystyle k }{\displaystyle k-1 } の累乗を事前計算しておかないと出てくるたびに繰り返し二乗法を行う羽目になり最悪時間計算量が {\displaystyle O(n^3 \log n) } となり TLE してしまうので注意.

ソースコード

#include <iostream>
#include <vector>

using namespace std;

using ll =  long long;

constexpr ll MOD = 1000000007;
constexpr int N_MAX = 250;

ll  n, k;
ll fact[N_MAX+1], rfact[N_MAX+1];
vector<ll> kpow(N_MAX+1, 1), k1pow(N_MAX+1, 1);

inline ll perm(ll n, ll r){
    return (fact[n] * rfact[r]) % MOD;
}

inline ll comb(ll n, ll r){
    return (perm(n, r) * rfact[n-r]) % MOD;
}

inline void init(ll n){
    for(int i=1;i<=n;++i) {
        kpow[i] = (kpow[i-1] * k) % MOD;
        k1pow[i] = (k1pow[i-1] * (k-1)) % MOD;
    }

    fact[0] = fact[1] = 1;
    rfact[0] = rfact[1] = 1;
    for(int i=2;i<=n;++i) {
        fact[i] = (fact[i-1] * (ll)i) % MOD;
        rfact[i] = 1;
        ll k = MOD-2;
        ll a = fact[i];
        while(k > 0){
            if(k & 1){
                rfact[i] *= a;
                rfact[i] %= MOD;
            }
            a *= a;
            a %= MOD;
            k  >>= 1;
        }
    }
}

inline ll modpow(ll a, ll t) {
    if(a == k) {
        return kpow[t];
    } else if(a == k-1) {
        return k1pow[t];
    }
    ll ret = 1LL;
    while(t){
        if(t & 1LL){
            ret *= a;
            ret %= MOD;
        }
        a *= a;
        a %= MOD;
        t >>= 1;
    }
    return ret;
}

int main() {
    cin >> n >> k;
    init(n);
    vector<vector<ll>> dp(n, vector<ll>(n+1, 0));

    for(int j=1;j<=n;++j) {
        dp[0][j] = (comb(n, j) * modpow(k-1, n-j)) % MOD;
    }

    for(int i=1;i<n;++i) {
        for(int j=1;j<=n;++j) {
            for(int j_=1;j_<=j;++j_) {
                dp[i][j] += (((dp[i-1][j_] * comb(n-j_, j-j_)) % MOD) * ((modpow(k, j_) * modpow(k-1, n-j)) % MOD)) % MOD;
                dp[i][j] %= MOD;
            }
            // j_ = j の場合,足し過ぎてしまうので引く
            dp[i][j] += MOD - ((dp[i-1][j] * modpow(k-1, n)) % MOD);
            dp[i][j] %= MOD;
        }
    }

    cout << dp[n-1][n] << endl;
}

所感

log は定数じゃない,それはそう.

AtCoder Beginner Contest 142 F - Pure

問題文: F - Pure

Writer 解説: https://img.atcoder.jp/abc142/editorial.pdf

問題概要

{\displaystyle  N (\leq 1000)} 頂点 {\displaystyle  M (\leq 2000)} 辺の有向グラフ{\displaystyle  G} が与えられる.

すべての頂点の入次数が 1 ,出次数が 1 となるような {\displaystyle  G} の部分誘導グラフを 1 つ答えよ.ただし,空グラフは含まない.

解法概要

f:id:noimin:20190930221213p:plain
図1: 問題の条件を満たす部分誘導グラフの例

「すべての頂点の入次数が 1 ,出次数が 1 となるような {\displaystyle  G} の部分誘導グラフ」というのは,図1のような部分誘導グラフ {\displaystyle  G^\prime} を構成するすべての頂点が一つの閉路を作っており,分岐がないようなグラフである.

つまり,閉路が存在しないときは問題の条件を満たす部分誘導グラフは存在しない.

閉路を見つけるには, dfs をしながら先祖とつながっている頂点がないか探せばよい.同時に,dfs で辿ってきた頂点は保存しておき,見つけた閉路が条件を満たすかどうかの確認および条件を満たすために行う閉路の縮約に用いる.なお今回は閉路を列挙していると時間が足りないしすべての閉路の情報が必要なわけではないので,閉路を 1 つ見つけたら探索をやめてよい.

さて,dfs で 1 つでも閉路を見つけたら,その閉路が問題の条件を満たすか確認する必要がある.閉路に使われる頂点同士をつなぐ辺だけを残した新しいグラフを作ったとき,図1のように条件を満たしていればよいが,図2のように閉路の中に余計な辺がある場合もある.図2の場合,部分誘導グラフに頂点 1〜6 をすべて含もうとすると 2 -> 6 のような閉路を作らない辺が入るので,頂点 1, 2, 6 からなる新しい閉路を作りたい.

f:id:noimin:20190930222307p:plain
図2: 問題の条件を満たさない部分誘導グラフの例

新しい部分誘導グラフを作るには,まず 2 -> 6のような閉路を作らない辺を検出する必要がある.これは dfs で閉路を探すときに閉路を作っている頂点とその順番を記録しておき,その情報を使うことで実現できる.すなわち,部分誘導グラフの中で閉路を作っている辺をチェックすれば,チェックされていない辺が閉路を作らない辺ということである.

閉路を作らない辺を見つけたら,今度はその辺 {\displaystyle  e} を使ったより小さい閉路 を作る.これは元々の部分誘導グラフの閉路のうち,{\displaystyle  e} の終点で始まり {\displaystyle  e} の始点でで終わるような部分 (図2 では 6->1->2) を持ってきて,これと {\displaystyle  e} を合わせればよい (図2 では 6->1->2->6) .個人的には,dfs の地点で閉路に使われる頂点を deque に持っておくことでこの部分の実装が楽になった気がする (ソースコード中の deque<int> history).

以降は,新しい閉路に含まれる頂点同士をつなぐ辺のみを残した新しい部分誘導グラフを作り,閉路を作らない辺を検出し,また新しい部分誘導グラフを作る……といったことを条件を満たすまで繰り返す.

dfs で閉路を見つけて以降に作る部分誘導グラフは常に閉路を持つし,新しい閉路を作るたびに頂点数は減っていく.そして,頂点数が2の閉路を持つグラフは常に問題の条件を満たす.このことから,前段落の繰り返しは必ず条件を満たして終了することができる.

元々のグラフは {\displaystyle  N (\leq 1000)} 頂点 {\displaystyle  M (\leq 2000)} 辺なので,閉路を全部列挙しようとするとかしない限り間に合う.

ソースコード

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

using Pii = pair<int, int>;

constexpr int N_MAX = 1123;

int n, m;
vector<int> graph[N_MAX];
vector<Pii> edges;
vector<bool> used(N_MAX, false), in_history(N_MAX, true);
deque<int> history;

inline void show_history() {
    int l = history.size();
    cout << l << endl;
    for(int i=0;i<l;++i) {
        cout << history[i]+1 << endl;
    }
}

inline bool check() {
    vector<int> indeg(N_MAX, 0), outdeg(N_MAX, 0);
    for(int i: history) {
        for(int j: graph[i]) {
            ++outdeg[i];
            ++indeg[j];
        }
    }

    for(int x: history) {
        if(outdeg[x] != 1 || indeg[x] != 1) return false;
    }
    return true;
}

inline bool dfs(int node) {
    used[node] = true;
    in_history[node] = true;
    history.push_back(node);
    for(int child: graph[node]) {
        if(in_history[child]) {
            while(history.front() != child) {
                in_history[history.front()] = false;
                history.pop_front();
            }
            return true;
        }
        if(dfs(child)) return true;
    }
    history.pop_back();
    in_history[node] = false;
    return false;
}

int main() {
    cin >> n >> m;
    int a, b;
    for(int i=0;i<m;++i){
        cin >> a >> b;
        --a; --b;
        graph[a].push_back(b);
        edges.emplace_back(a, b);
    }

    // 閉路探し (閉路がなければ終わり)
    {
        int i = 0;
        for(;i<n;++i) {
            if(used[i]) continue;
            in_history = vector<bool>(N_MAX, false);
            if(dfs(i)) break;
        }
        if(i == n) {
            cout << -1 << endl;
            return 0;
        }
    }

    // 閉路縮約
    while(!check()) {
        // いらないエッジを消す
        for(int i=0;i<n;++i) graph[i].clear();
        for(Pii e: edges) {
            if(in_history[e.first] && in_history[e.second]) {
                graph[e.first].push_back(e.second);
            }
        }

        // 閉路を作っている辺をチェックする
        vector<bool> selected[n];
        for(int i=0;i<n;++i) {
            selected[i].assign(graph[i].size(), false);
        }
        int n_history = history.size();
        for(int i=0;i<n_history;++i) {
            int a = history[i], b = history[(i+1)%n_history];
            for(int j=0;j<graph[a].size();++j) {
                if(graph[a][j] == b) {
                    selected[a][j] = true;
                }
            }
        }

        // 閉路を作っている辺以外の辺を見つける
        Pii e = {-1, -1};
        for(int i=0;i<n;++i) {
            for(int j=0;j<selected[i].size();++j) {
                if(selected[i][j] == 0) {
                    e.first = i;
                    e.second = graph[i][j];
                    break;
                }
            }
        }

        // いらないノードを消す
        if(e.first != -1) {
            while(history.front() != e.second) {
                history.push_back(history.front());
                history.pop_front();
            }
            while(history.back() != e.first) {
                in_history[history.back()] = false;
                history.pop_back();
            }
        }
    }

    show_history();
    return 0;
}

所感

前回の ABC ではレートを1500台まで戻すことができて,やっとスランプから脱出できたのではと思っています.

しかしこれは本番で解きたかった…….

Codeforces Round #588 (Div. 1 B / Div 2. E) Kamil and Making a Stream

問題: https://codeforces.com/contest/1229/problem/B

公式解説: https://codeforces.com/blog/entry/70008

問題概要

{\displaystyle n (\le {10}^5) } 頂点の木が与えられる.{\displaystyle i } 番目の頂点には非負整数 {\displaystyle a_i (\le {10}^{12} )} が割り当てられている. 次式の値を求めよ.

{\displaystyle \sum_{u は v の先祖} f(u, v) }

ただし {\displaystyle f(u, v) }{\displaystyle u } から {\displaystyle v } までのパス上にあるすべての頂点に割り当てられている非負整数の最大公約数を指す.

解法概要

一言で言ってしまえば,「上から順に gcd の値を保持しながら dfs していく」それだけ.

実はこの解法,コンテスト中に思いついたものの秒で棄却してしまった解法だった.

「木のパスに分岐がないような最悪ケースの場合,空間計算量 {\displaystyle O(n) } の gcd を保持してノードごとに更新していく必要があり,時間計算量が {\displaystyle O(n^2) } になってしまうのでは?」

と考えたためである.

しかしこれは誤りで,gcd の種類数は {\displaystyle \log (\max a_i) } で抑えることができる.何故ならば,根からパスをたどっていく過程で gcd の値が変化するとき,新しい gcd {\displaystyle g' } と古い gcd {\displaystyle g } について, {\displaystyle g' \le \frac{g}{2} } が成り立つためである.{\displaystyle g'  = \mathit{gcd}(g, a_i )} なので, {\displaystyle g' } は必ず {\displaystyle g } の約数でもある.なので,{\displaystyle g' \le g } が成り立つ場合,{\displaystyle g' \le \frac{g}{2} } も成り立つことになる.このことから,gcd の種類数は {\displaystyle \log (\max a_i) } で抑えることができることがわかる.

ソースコード

#include <iostream>
#include <vector>
#include <map>

using namespace std;

using ll =  long long;

constexpr ll MOD = 1000000007;
constexpr int N_MAX = 100000;

int n, u, v;
vector<int> graph[N_MAX];
vector<ll> nodes(N_MAX);

ll gcd(ll a, ll b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}

ll dfs(int node, int par, map<ll, ll> mp) {
    ll ret = 0;
    map<ll, ll> mp2;
    for(auto p: mp) {
        ll g = gcd(nodes[node], p.first);
        mp2[g] += p.second;
        ret += (g * p.second) % MOD;
        ret %= MOD;
    }
    ++mp2[nodes[node]];
    ret += nodes[node];
    ret %= MOD;
    for(int child: graph[node]) {
        if(child == par) continue;
        ret += dfs(child, node, mp2);
        ret %= MOD;
    }
    return ret;
}


int main() {
    std::ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=0;i<n;++i) cin >> nodes[i];
    for(int i=0;i<n-1;++i) {
        cin >> u >> v;
        --u; --v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    cout << dfs(0, -1, map<ll, ll>()) << endl;
}

所感

計算量解析,大事。

AtCoder Grand Contest 038 C - LCMs

問題: C - LCMs

公式解説: https://img.atcoder.jp/agc038/editorial.pdf

問題概要

長さ {\displaystyle N (\leq 2 \times {10}^5) } の数列 {\displaystyle A_0, A_1, \dots, A_{N-1} } (ただし {\displaystyle A_i \leq {10}^6 } ) が与えられる.次式の値を 998244353 で割ったものを求めよ.

{\displaystyle \sum_{i=0}^{N-2} \sum_{j=i+1}^{N-1} \mathit{lcm}(A_i, A_j) }

解法概要

参考: 公式解説pdf, 公式解説動画, tourist さんのソースコード

{\displaystyle \mathit{lcm}(x, y) = \frac{xy}{\mathit{gcd}(x, y)} }

なので,

{\displaystyle \sum_{d|\mathit{gcd}(x, y)} w_d =  \frac{1}{\mathit{gcd}(x, y)} } となるような係数 {\displaystyle w_d } が用意できると, {\displaystyle A_0, A_1, \dots, A_{N-1} } の中で {\displaystyle d } の倍数となるものの和 (と二乗和) から求めたい値が求められるので嬉しい.

具体的には,以下のような式変形を行う:

{\displaystyle \sum_{i=0}^{N-2} \sum_{j=i+1}^{N-1} \mathit{lcm}(A_i, A_j) }

{\displaystyle  = \sum_{i=0}^{N-2} \sum_{j=i+1}^{N-1} A_i A_j (\sum_{d|A_i, d|A_j} w_d) }

{\displaystyle  = \sum_{d=1}^{\max A_i} w_d \sum_{d|A_i, d|A_j, i \lt j} A_i A_j  }

{\displaystyle  = \sum_{d=1}^{\max A_i} w_d \cdot \frac{1}{2} ((\sum_{d|A_i} A_i )^2 - \sum_{d|A_i} A_i^2) }

あとは式変形後の Σ の部分と,{\displaystyle w_d } が求められれば良いのだが,{\displaystyle 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{N} \simeq O(\log n)} より時間計算量 {\displaystyle O(n \log n) } で求めることができる.

ただしこの問題は定数倍がきつめで,{\displaystyle w_d } を求めるときなどにオーダでは変わりなくても定数倍が重い処理を書いてしまうと簡単に TLE してしまうので注意.以下のソースコードでは TLE となる処理も AC だった処理と併記している.

ソースコード

#include <iostream>
#include <vector>

using namespace std;

using ll =  long long;

constexpr ll MOD = 998244353;
constexpr ll N_MAX = 200000;
constexpr ll A_MAX = 1000000;

inline ll modpow(ll a, ll t) {
    ll ret = 1LL;
    while(t){
        if(t & 1LL){
            ret *= a;
            ret %= MOD;
        }
        a *= a;
        a %= MOD;
        t >>= 1;
    }
    return ret;
}

inline ll modinv(ll a) {
    return modpow(a, MOD-2);
}

vector<ll> w(A_MAX);


// これだと TLE
// inline void init_w() {
//     w[1] = 1;
//     w[2] = (modinv(2)-1+MOD) % MOD;
//     for(int i=3;i<=A_MAX;++i) {
//         ll s = 0;
//         for(int j=1;j*j<=i;++j) {
//             if(i % j) continue;
//             s += w[j];
//             if(1 < j && j*j < i) s += w[i/j];
//             s %= MOD;
//         }
//         w[i] = (modinv(i) - s + MOD) % MOD;
//     }
// }
// こっちは余裕で AC
inline void init_w() {
    for(int i=1;i<=A_MAX;++i) {
        w[i] = modinv(i);
    }
    for(int i=1;i<=A_MAX;++i) {
        for(int j=i+i;j<=A_MAX;j+=i) {
            w[j] += MOD-w[i];
            w[j] %= MOD;
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false); cin.tie(nullptr);
    init_w();
    int n;
    cin >> n;

    vector<ll> a(A_MAX+1, 0);
    ll aa;
    for(int i=0;i<n;++i) {
        cin >> aa;
        ++a[aa];
    }

    ll ans = 0LL;
    for(int i=1;i<=A_MAX;++i) {
        ll s = 0, t = 0;
        for(int j=i;j<=A_MAX;j+=i) {
            ll tmp = (j*a[j]) % MOD;
            s += tmp;
            s %= MOD;
            t += (tmp * j) % MOD;
            t %= MOD;
        }
        ans += (w[i] * (((s*s)%MOD - t + MOD) % MOD)) % MOD;
        ans %= MOD;
    }
    
    cout << (ans * modinv(2)) % MOD << endl;
}

所感

解説放送見て「頭いいー!」を連発することしかできなかった

Educational Codeforces Round 73 (Rated for Div. 2) E. GameWithString

問題: https://codeforces.com/contest/1221/problem/E

問題概要

Alice と Bob が2人でゲームをする.先攻は Alice である.

'.' と 'X' のみからなる,{\displaystyle \left| s \right| (\leq 3 \times 10^5) } を満たす文字列 s がある.

この文字列 s から, Alice は {\displaystyle a (\leq 3 \times 10^5) } 個, Bob は {\displaystyle b (\leq 3 \times 10^5) } 個連続している '.' をすべて 'X' に変える操作を行う.どちらも操作ができなくなったとき,最後に操作したプレイヤーの勝利となる.ただし {\displaystyle a \gt b } が必ず成り立つ.

2人が最適に操作を選択したとき,Alice が勝利するかどうかを答えよ.

解法概要

参考: keymoon さんのツイート

連続する {\displaystyle v } 個の '.' を," {\displaystyle v } の要素" と呼ぶこととする.

{\displaystyle a \gt b } より, Bob が有利なゲームである.なぜならば,Alice が操作ができず Bob は操作ができる要素 ({\displaystyle  b \le v \lt a } となる {\displaystyle v } の要素) が1つでもあるならば,Alice は負けてしまうからである.残りの要素が「2人とも操作できない要素」と「Alice が操作ができず Bob は操作ができる要素」だけになったとき,Alice のターンなら Alice は操作ができずに負けるし, Bob のターンなら Bob が操作した後やはり Alice は操作ができず負ける.

Bob しか操作できない要素がなければ,最適な戦略は Bob は自分だけが操作できる要素を作り出すこと,Alice は Bob だけが操作できる要素を作らせないこととなる. Bob しか操作できない要素を作り出すには,{\displaystyle 2b \le v } となるような要素に対して片側を {\displaystyle b \le i \lt a } 個だけ残して操作すればよい.

これらの戦略を頑張って場合分けで実装する. 場合分けの詳細はソースコードのコメント参照.

ソースコード

#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool solve() {
    int a, b;
    cin >> a >> b;
    string s;
    cin >> s;
    if(s.back() != 'X') s += 'X';
    int n = s.length(), continuous_cnt = 0;

    // '.' が何個続くかを格納したベクトル v を作る
    vector<int> v;
    for(int i=0;i<n;++i) {
        if(s[i] == 'X') {
            if(continuous_cnt >= b) {   // b未満の要素は2人とも取れないので考えなくていい
                v.push_back(continuous_cnt);
            }
            continuous_cnt = 0;
        } else {
            ++continuous_cnt;
        }
    }

    int cnt = 0;
    int max_v = 0;
    for(int vv: v) {
        if(vv < a) return false; // Bob しか取れない要素
        else if(vv < 2*b) ++cnt; // 2人とも取れて,かつ Bob が自分か取れない要素を作り出せない要素
        else {                   // Bob が自分しか取れない要素を作り出せる要素
            if(max_v) {
                return false;
            } else {
                max_v = vv;      // 1つだけなら Bob しか取れない要素を作られる前に阻止できる
            }
        }
    }

    // Bob しか取れない要素の作成を阻止してからの戦い

    // この地点で max_v 以外は (a <= vv && vv < b) な要素だけでできている
    if(max_v) {
        /*
         * Alice は最初のターンで max_v から a 個を取ったものと仮定する
         * (他の要素から取ると,max_v ( >= 2*b) を用いて Bob しか取れない要素を作り出されてしまうので)
         */
        for(int i=0;i<=max_v-a;++i) {   // Alice が最初のターンで取る位置は全探索
            int j = max_v - (i+a);  // Alice がa個取ると max_v が i 個と j 個に分かれる
            if((b <= i && i < a) || (b <= j && j < a) || 2*b <= i || 2*b <= j) {
                // Bob しか取れない要素ができちゃったり,
                // 次の Bob のターンで Bob しか取れない要素を作られてしまうような取り方はしたくない
                continue;
            } else {
                // (a <= vv && vv < b) な要素 + 最初のターンで取った分 + i から取れる分 + j から取れる分
                // の合計が奇数ならそのように取ればいい
                if((cnt + 1 +  ((a <= i)?1:0) + ((a <= j)?1:0)) % 2) return true;
            }
        }
        // 勝てる手筋がなければアウト
        return false;
    }

    // (a <= vv && vv < b) な要素だけなら,単純に要素数の偶奇
    return cnt % 2;
}

int main() {
    std::ios::sync_with_stdio(false); cin.tie(nullptr);
    int q;
    cin >> q;
    while(q--) {
        cout << (solve()?"YES":"NO") << endl;
    }
}

所感

Codeforces 紫になりました!  これで AtCoderCodeforcesTopCoder SRM の色がすべて違うことに……

鬼場合分けもそろそろ本番で解けるようにならないとな.

f:id:noimin:20190920235324p:plain

AtCoder Beginner Contest 132 F - Small Products

問題文: F - Small Products

Writer 解説: https://img.atcoder.jp/abc132/editorial.pdf

問題概要

正の整数 {\displaystyle  K (\leq 100)} 個からなる数列で,隣接するどの 2 つの整数の積も {\displaystyle  N (\leq 10^9)} 以下であるものの個数を {\displaystyle  {10}^9 + 7 } で割ったあまりを求めよ.

解法概要

数列の値を左から順に決めるとすると,{\displaystyle  i} 番目の値を決めるのに必要なのは {\displaystyle  (i-1) } 番目の値のみである. このことから,(制約をとりあえず置いておくと) 次のような DP が考えられる.

{\displaystyle  \mathit{dp}_{i, j} = i} 番目の値が {\displaystyle  j} であるような数列の個数 (を{\displaystyle  {10}^9 + 7 } で割ったあまり)

このとき,更新は次のようにできるはずである.

{\displaystyle  \mathit{dp}_{i, j} = \sum_{k=1}^{t} \mathit{dp}_{i-1, k}  } (ただし {\displaystyle t = \lfloor \frac{N}{j} \rfloor })

今回の制約では,この DP は当然間に合わない.(この TLE 解の時間計算量って {\displaystyle  O(N^2K)} でしょうか? 自信がないので教えていただけたら嬉しいです)

累積和を使って,

{\displaystyle  \mathit{dp}_{i, j} = i} 番目の値が {\displaystyle j } 以下 であるような数列の個数 (を{\displaystyle  {10}^9 + 7 } で割ったあまり)

とすると,各更新が定数時間で済むようになり時間計算量が {\displaystyle  O(NK)} となるが,それでも遅い.

……と,ここまでは自力で考えついてあとは隣り合った要素の積の列などを考えたりもしたが思いつかず,解説をチラ見.

実はこの DP による解法は,状態をまとめることでさらなる時間計算量改善が可能. 具体的には,{\displaystyle \lfloor \frac{N}{j_1} \rfloor =  \lfloor \frac{N}{j_2} \rfloor } となるような {\displaystyle j_1, j_2 } はまとめることができる.何故ならば,両者とも

{\displaystyle  \mathit{dp}_{i, j} = i} 番目の値が {\displaystyle  j} であるような数列の個数 (を{\displaystyle  {10}^9 + 7 } で割ったあまり)

について,

{\displaystyle  \mathit{dp}_{i, j_1} = \mathit{dp}_{i, j_2} = \sum_{k=1}^{t} \mathit{dp}_{i-1, k}  } (ただし {\displaystyle t = \lfloor \frac{N}{j_1} \rfloor = \lfloor \frac{N}{j_2} \rfloor })

という同一の更新式によって更新できるためである.

そこで {\displaystyle  N} で割った商が同じ数は同じグループと考えて,グループごとに DP の値を保持して更新もグループごとに行うことで,今まで {\displaystyle  O(NK)} だった空間計算量が {\displaystyle  O(\sqrt{N}K)} となる.

時間計算量については,解説によると {\displaystyle  O(\sqrt{N}K)} で書けるらしい.私の解法だと sort を使っているので {\displaystyle  O(\sqrt{N}\log{N} \cdot K)}

ソースコード

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

using ll =  long long;

constexpr ll MOD = 1000000007;

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> quotients(1, 0);
    for(int i=1;i<=min(n, int(sqrt(n))+1);++i) {
        quotients.push_back(n/i);
        quotients.push_back(n/(n/i));
    }
    sort(quotients.begin(), quotients.end());
    quotients.erase(unique(quotients.begin(), quotients.end()), quotients.end());
    int m = quotients.size();

    vector<int> inv_quotients_idx(m, -1);
    {   
        int j = m-1;
        for(int i=1;i<m;++i) {
            while(i <= j && quotients[i]*quotients[j] > n) --j;
            if(i > j) break;
            inv_quotients_idx[i] = j;
            inv_quotients_idx[j] = i;
        }
    }
    
    vector<vector<ll>> dp(k+1, vector<ll>(m, 0));
    for(int j=1;j<m;++j) dp[0][j] = quotients[j];
    for(int i=1;i<k;++i) {
        for(int j=1;j<m;++j) {
            dp[i][j] = (dp[i-1][inv_quotients_idx[j]] * (quotients[j] - quotients[j-1])) % MOD;
        }

        for(int j=1;j<m;++j) {
            dp[i][j] += dp[i][j-1];
            dp[i][j] %= MOD;
        }
    }

    cout << dp[k-1][m-1] << endl;
    
}

所感

「状態をまとめる」ことを考える際の着眼点や,「本当にまとめて良いのか?」を判断するときに考慮すべきポイントみたいなものを学べた.そういえば DEGwer さんの数え上げ pdf にも状態をまとめられる条件が書いてあったね.