ながめも

競技プログラミングについて

AtCoder Beginner Contest ABC025 C - 双子と○×ゲーム

AtCoder ゲーム 操作を逆順で考える DFS 順列 2変数を1変数に

C - 双子と○×ゲーム

問題へのリンク

解説

まず、置く順番は 9!通りありますが、すべて試していいだろうとわかります。順列の列挙は、簡単に行う場合はnext_permutationを使いますが、今回は順列の生成とともにゲーム木を構成したいので、自前で実装します。基本的なDFSです。

木が構成されたとき、偶奇によって先攻と後攻どちらに意思決定権があるかが変わります。ゲーム木が葉までいったとき、順番が決まるわけですが、その順番で置いたときの先攻と後攻の得点を計算します。そして、意思決定権のある方の得点が最大になるような手のみを親に伝播させていくことで、最初にどちらの手を打つべきかがわかり、このゲームにおける最適な行動がわかるというわけです。

より簡単に考えると、2人の得点の和は一定なので、両方を保持する必要はなく、先攻の得点のみを記録し、先攻が決める場合は最大、後攻が決める場合は最小のように実装しても同様の結果になります。

以上のような実装で、計算回数は 9!回ほどで終わり、間に合います。

実装

int b[10][10], c[10][10];
int d[10][10];
bool visited[10];
// 順列が与えられるので、計算する
i_i calc(vector<int> &v){
    int sz = v.size();// = 9
    rep(i,sz){
        int x = v[i] % 3;
        int y = v[i] / 3;
        d[x][y] = i&1;
    }
    int l = 0, r = 0;
    rep(i,2)rep(j,3){
        if(d[i][j] == d[i+1][j])l += b[i][j];
        else r += b[i][j];
    }
    rep(i,3)rep(j,2){
        if(d[i][j] == d[i][j+1])l += c[i][j];
        else r += c[i][j];
    }
    return make_pair(l,r);
}
i_i dfs(vector<int> &v){
    if(v.size() == 9)return calc(v);
    int sz = v.size();
    int maxx = -1;
    i_i res;
    rep(i,9){
        if(visited[i])continue;
        v.emplace_back(i);
        visited[i] = true;
        auto p = dfs(v);
        int l = p.first;
        int r = p.second;
        v.pop_back();
        visited[i] = false;
        if(sz&1){ // lをmaxにする手を選ぶ
            if(chmax(maxx, r))res = p;
        }
        else{ // rをmaxにする手を選ぶ
            if(chmax(maxx,l))res = p; 
        }
    }
    return res;
}
int main() {

    rep(i,2)rep(j,3)cin >> b[i][j];
    rep(i,3)rep(j,2)cin >> c[i][j];
    rep(i,10)visited[i] = false;
    vector<int> v;
    auto ans = dfs(v);
    cout << ans.first << endl;
    cout << ans.second << endl;
}

AtCoder Grand Contest AGC005 B - Minimum Sum

AtCoder AGC 主客転倒 二分探索 区間

B - Minimum Sum

問題へのリンク

解説

区間がたくさん与えられるので、その中のある値の和を求めよという問題は多くありますが、基本的に区間をすべて列挙して解くことはできません。今回も例によってそのパターンで、ある値 a_iが、いくつの区間の値になるかを求める問題だと捉えることでソリューションを見出します。いわゆる寄与ゲー、主客転倒と言われる部類の問題です。

ある値 a_iが最小値になる区間は、左右に広がっているので、その境界を二分探索することでうまくいきます。左右の境界が求まったら、左右の境界の組み合わせが寄与する個数になるので、 \Theta(N\log{N})で解くことができました。

実装

template<typename T>
class SegTree {
  public:
    int N;//葉の数
    vector<T> data;//配列
    T unit;//単位元
    function<T(T,T)> op;//区間クエリで使う処理
    function<T(T,T)> update;//点更新で使う処理
    T _query(int a, int b, int k, int l, int r) {
        if(r <= a || b <= l)return unit;
        if(a <= l && r <= b){
            return data[k];
        }
        else{
            T c1 = _query(a, b, 2 * k + 1, l, (l + r) / 2); //左の子
            T c2 = _query(a, b, 2 * k + 2, (l + r) / 2, r); //左の子
            return op(c1, c2);
        }
    }
    //コンストラクター
    //_N: 必要サイズ, _unit: 初期値かつ単位元, _op: クエリ関数, _update: 更新関数
    SegTree(int _N, T _unit, function<T(T, T)> _op, function<T(T, T)> _update) 
        :unit(_unit), op(_op), update(_update){
        N = 1;
        while(N < _N)N *= 2;
        data.assign(2 * N - 1, unit);
    }
    //i(0-indexed)の値にupdate関数を適用
    void change(int i, T x){
        i += N - 1;
        data[i] = update(data[i], x);
        while(i > 0){
            i = (i - 1) / 2;
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2]);
        }
    }
    //[a, b)の区間クエリの実行
    T query(int a, int b){
        return _query(a, b, 0, 0, N);
    }
    //添字でアクセス
    T operator[](int i) {
        return data[i + N - 1];
    }
};

int main(){
    int N;
    cin >> N;    
    long long inf = (1LL << 31) - 1;
    auto f = [&](long long a, long long b){
        return min(a, b);
    };
    auto g = [&](long long a, long long b){
        return b;
    };
    SegTree<long long> Tree(N,inf,f,g);
    vector<ll> A(N);
    rep(i, N)cin >> A[i];
    rep(i,N)Tree.change(i, A[i]);
    auto checkl = [&](int l, int r) -> bool{
        return Tree.query(l,r) == A[r-1];
    };
    auto checkr = [&](int l, int r) -> bool{
        return Tree.query(l,r) == A[l];
    };
    ll ans = 0;
    rep(i,N){
        // calc 左端と右端を計算する O(logN)
        ll l, r;
        {
            int ng = -1;
            int ok = i;
            while(ok - ng > 1){
                int mid = (ok + ng) >> 1;
                if(checkl(mid, i+1))ok = mid;
                else ng = mid;
            }
            l = i+1 - ok;
        }
        {
            int ok = i+1;
            int ng = N+1;
            while(ng - ok > 1){
                int mid = (ok + ng) >> 1;
                if(checkr(i,mid))ok = mid;
                else ng = mid;
            }
            r = ok - i;
        }
        ll cnt = l * r;
        ans += cnt * A[i];
    }
    cout << ans << endl;
}

AtCoder Beginner Contest 174 ABC174 参加記

AtCoder ABC コンテスト参加記 桁ごとに見る MOD ceil 決めうち二分探索 BIT クエリ先読み 終端ソート 区間

Eまでノーペナ30分だったのにF既出を検索できずにしょっぱいパフォを取ってしまいました。もったいなかったです。

目次

A - Air Conditioner

問題へのリンク

解説

if文を使います。C++では以下のような書き方でifを使わずに書くことができます。

実装

int main() {
    int N;
    cin >> N;
    cout << ((N >= 30) ? "Yes" :"No") << endl;
}

B - Distance

問題へのリンク

解説

ルートは外して整数で考えましょう。intだとオーバーフローするので、long longを使いましょう。

実装

int main() {
    ll N, D;
    cin >> N >> D;
    ll ans = 0;
    rep(i,N){
        ll x, y;
        cin >> x >> y;
        ans += (x*x+y*y) <= D*D;
    }
    cout << ans << endl;
}

C - Repsept

問題へのリンク

解説

modは、基本的に桁ごとにみていいです。 これ説明難しいです、エスパーして大きめに回すと解を得ます。

実装

int main() {

    ll K;
    cin >> K;
    vector<ll> v(10*K);
    v[0] = 0;
    rep(i,10*K){
        v[i+1] = (v[i]*10 % K) + 7;
        v[i+1] %= K;
        if(v[i+1] == 0){
            cout << i+1 << endl;
            return 0;
        }
    }
    cout << -1 << endl;
}

D - Alter Altar

問題へのリンク

解説

Rを左に寄せれば良いので、まず既存のRの個数 cntrを計算し、先頭から長さ cntrの中にある Wと右にある Rをswapすることを考えれば良いです。これが操作回数の最小値です。

実装

int main() {
    int N;
    cin >> N;
    string S;
    cin >> S;
    ll cntr = 0;
    rep(i,N)cntr += S[i] == 'R';
    ll ans = 0;
    rep(i,cntr)ans += S[i] == 'W';
    cout << ans << endl;
}

E - Logs

問題へのリンク

解説

最大値の最小化問題なので、二分探索をしたくなります。いわゆる決めうち二分探索です。全てを X以下にするために必要な操作回数を \Theta(N)で求めることができれば、全体の計算量が \Theta(N\log \max(A))になります。

長さ A_iを X以下の長さに分けるのに必要な回数は、 A_i / X - 1（切り上げ）です。

実装

int main() {
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N);
    rep(i, N)cin >> A[i];
    sort(all(A));
    auto check = [&](ll X) -> bool{
        ll cnt = 0;
        rep(i,N)cnt += (A[i] + X - 1) / X;
        return cnt-N <= K;
    };
    ll ng = 0;
    ll ok = A[N-1];
    while(ok - ng > 1){
        ll mid = (ok + ng) >> 1;
        if(check(mid))ok = mid;
        else ng = mid;
    }
    cout << ok << endl;
}

F - Range Set Query

問題へのリンク

感想

既出臭がプンプンするのでぐぐると出てくるようです。私は英語でググっていたので全くヒットしませんでした。

AtCoder Beginner Contest ABC023 C - 収集王

AtCoder ABC グリッド

C - 収集王

問題へのリンク

解説

行 iにある点の個数が r個のとき、列が K - r個のとき和が Kになりそうなところから考察を進める。

ここで、列が K - r個の列の個数を追加すれば良さそうだが、ここに罠がある。その列に点があるときはその列は K - r - 1、点がないときは K - rであることが条件であり、そのように単純に数えることができない。

よって、まず K - r個の点を持つ列の個数を追加した後、実際の頂点を見て、その列が K - r個だったら削除し、 K - r - 1だったら追加するというアルゴリズムでうまく数えることができる。

計算量は \Theta(R+C+N)。

実装

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)

int H, W, K, N;
int x, y;
int mpy[100050];
vector<pair<int, int>> v[100050], vv[100050];
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> H >> W >> K;
    cin >> N;
    rep(i,N){
        cin >> x >> y;
        x--;
        y--;
        v[x].emplace_back(x,y);
        vv[y].emplace_back(x,y);
    }
    rep(j,W)mpy[vv[j].size()]++;
    long long ans = 0;
    rep(i,H){
        int r = v[i].size();
        int add = mpy[K-r];
        for(auto p: v[i]){
            int cnty = vv[p.second].size();
            if(cnty == K-r)add--;
            if(cnty == K-r+1)add++;
        }
        ans += add;
    }
    cout << ans << endl;
}

AtCoder Grand Contest AGC025 B - RGB Coloring

AtCoder AGC 数え上げ 操作を言い換える

B - RGB Coloring

問題へのリンク

解説

各マスの状態が4種類ある

  • A
  • A + B
  • B
  • 無

デフォルトを無だと考えて、そこに得点を割り振っていくと考えると、 A(B)にするかしないかを A,B独立に決めて、重なったら A+Bにすると考えればよいことがわかる。

よって、 Aの個数を iに決めれば、和が Kになる Bの個数 jは一意に定まり、

\displaystyle{ j = \frac{K-A \times i}{B} }

になる。ただし (K-A \times x)\%B == 0が条件。

A,Bの個数がそれぞれ i,jになるような塗り方は _N C_{i} * _N C_jである。これをすべての iについて足し合わせればよい。

計算量は \Theta(N)。

実装

struct mint {
};

struct combination {
}C(300010);

int main() {

    ll N, A, B, K;
    cin >> N >> A >> B >> K;
    mint ans = 0;
    for(ll i = 0; i <= N; i++){
        ll rem = K - A * i;
        if(rem < 0)continue;
        if(rem % B > 0)continue;
        ll j = rem / B;
        ans += C.Comb(N,i) * C.Comb(N,j);
    }
    cout << ans << endl;
}

AtCoder Beginner Contest ABC008 C - コイン

ABC 主客転倒 期待値の線形性 数え上げ

問題へのリンク

解説

公式解説とは異なる方針でACしたので記録を残しておきます。

まず、いわゆる主客転倒（寄与ゲー）と呼ばれる問題だと捉えます。 今回求めたいのは、 N!の並びのうち、表のコインの数の期待値ですが、 これを期待値ではなく数え上げの問題として認識します。 つまり、表のコインの枚数を数え上げ、最後に N!で割れば期待値の計算ができます。

これを、あるコインが表になる場合の数を足し合わせることで計算します。

あるコイン iが表になるのは、そのコインより左のコインの中に C_iの約数が偶数個ある場合です。

まず、コイン i以外で C_iの約数の個数を Sとします。

コイン iが位置 jにあって、その左に k個コインがある場合を数え上げればよく( kは偶数)、これはcombinationとpermutation、階乗の計算を前計算すれば解くことができます。

  1. C_iの約数 S個から左に置くコイン k個を選び (_{S} C_{k})、
  2. 選んだ約数 k個を左への並べ方が _{j} P_{k}通り（場所を選んで並べるイメージ）、
  3. 残りの約数 S - k個を右への並べ方が _{N-1-j} P_{S - k}通り（場所を選んで並べるイメージ）、
  4. 約数以外の並べ方が (N-1-S)!（場所は上で確定しているので、並べるだけ）通り。

計算量は \Theta(N^{3})です。

実装

ところでこの階乗の計算で誤差ってどこまで許容されるんですかね（わかっていない顔）。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)

int main() {
    cout << fixed << setprecision(20);
    int N;
    cin >> N;
    vector<int> C(N);
    rep(i, N)cin >> C[i];
    vector<int> cnt(N,0);
    rep(i,N)rep(j,N){
        if(i == j)continue;
        if(C[j]%C[i] == 0)cnt[j]++;
    }

    long double kai = 1;
    for(int i = 1; i <= N; i++)kai /= i;
    vector<long double> fact(N+1);
    fact[0] = kai;
    rep(i,N)fact[i+1] = fact[i] * (i+1);

    auto comb = [&](int a, int b) -> long double{
        if(a == 0 || b == 0)return 1;
        if(b > a)return 0;
        return fact[a] / fact[a-b] / fact[b] * kai;
    };
    auto perm = [&](int a, int b) -> long double{
        if(a == 0 || b == 0)return 1;
        if(b > a)return 0;
        return fact[a] / fact[a - b];
    };

    long double ans = 0; 
    // あるコインiが場所jにいて
    // 自分より左にk個、右にcnt[i] - k個おくときの場合の数
    // kは偶数のみ
    rep(i,N)rep(j,N){
        for(int k = 0; k <= j && k <= cnt[i]; k+=2){
            int S = cnt[i];
            if(k > j)continue;
            if(S-k > N-1-j)continue;
            long double tmp = comb(S,k) * perm(j,k) * perm(N-1-j,S-k) * fact[N-1-S];
            ans += tmp;
        }
    }
    cout << ans << endl;
}

公式解説

公式の解説では、もっと簡単に問題を捉えています。 まず、期待値の線形性を考えれば、コインごとの期待値の足し合わせが答えになることがわかります。

コイン iについて考えると、期待値を計算するのであれば、とても簡潔に考えることができます。 コイン iの位置について、約数の並べの中でどの位置にあるかを考えます。この位置に関して、共通して現れる計算として、約数の並べ方と約数以外の並べ方があります。これらはコイン iが約数の並べの中でどの位置になるかに依存しません。まず約数を並べて、位置を選び、その後約数以外を挿入すると考えるとわかりやすいでしょう。よって、約数の個数のみを考慮すれば良いことになります。

考える順番を変えるだけでかなり楽に計算することができました。

Codeforces Round #658 (Div. 2) 参加記

Codeforces ゲーム deque

B - Sequential Nim

最初に a_i > 1に到達した方が、常に先に山に手をつけることができる。これは、次が a_i > 1なら、その山を 1だけ残して相手に渡し、次が 1の場合は山を全て取ることで実現できる。よって、到達するまでの回数を数えればよい。注意点として、最後の山は数えない。

void solve(){
    int N;
    cin >> N;
    vector<int> a(N);
    rep(i,N)cin >> a[i];
    int cnt = 0;
    rep(i,N-1){
        if(a[i] == 1)cnt++;
        else break;
    }
    cout << ((cnt%2 == 0)? "First": "Second") << endl;
}

C - Prefix Flip

Easy Version

右から揃えていく。 iが揃っていない場合、反転させるためには、 a_0 == a_iであることが条件である。この条件を満たしていない場合は、先頭だけの処理を挟めばよい。

\Theta(N^{2})である。

void solve(){
    int N;
    cin >> N;
    string a, b;
    cin >> a >> b;
    auto f = [&](int x){
        //cerr << x << ":" << endl << a << endl;
        rep(i,x+1){
            a[i] = char(((a[i] - '0') ^ 1) + '0');
        }
        reverse(a.begin(), a.begin()+x+1);
        //cerr << a << endl;
    };
    vector<int> ans;
    for(int i = N-1; i >= 0; i--){
        if(a[i] == b[i])continue;
        if(a[0] == a[i]){
            f(i);
            ans.push_back(i+1);
        }
        else{
            f(0);
            ans.push_back(1);
            f(i);
            ans.push_back(i+1);
        }
        //dump(a);
    }
    cout << ans.size() << " ";
    for(auto v: ans){
        cout << v << " ";
    }
    cout << endl;
}

Hard Version

右から揃えていくのは変わらないが、reverseを実装するとTLEになる。 ここで、reverseする代わりに、左右端のindex l,rを持ち、reverseされることをswap(l,r)に言い換える。また、間が何回反転されたかも持つ。間がどこにあるかを持つ必要はない。先頭だけの処理もあるので、個別の反転回数も持って、合計何回反転されたかをもてば偶奇でわかるようになる。

\Theta(N)。

void solve(){
    int N;
    cin >> N;
    string a, b;
    cin >> a >> b;
    vector<int> x(N), y(N);
    rep(i,N){
        x[i] = a[i] - '0';
        y[i] = b[i] - '0';
    }
    int l = 0;
    int r = N-1;
    int cnt_all = 0;
    vector<int> cnt(N,0);
    vector<int> ans;
    for(int i = N-1; i >= 0; i--){
        int xr = x[r] + cnt_all + cnt[r];
        int xl = x[l] + cnt_all + cnt[l];
        xr %= 2;
        xl %= 2;
        if(xr == y[i]){
            if(l < r)r--;
            else r++;
            continue;
        }
        if(xl != xr){
            xl ^= 1;
            cnt[l]++;
            ans.push_back(1);
        }
        swap(l,r);
        ans.push_back(i+1);
        cnt_all++;
        if(l < r)r--;
        else r++;
    }
    cout << ans.size() << " ";
    for(auto v: ans){
        cout << v << " ";
    }
    cout << endl;
}