エクサウィザーズ 2019

C - Snuke the Wizard

https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_c

方針

全てのゴーレムは、他のゴーレムと同じ座標に来ることはありますが、追い越すことはありません。したがって残るゴーレムを O, 消えるゴーレムを X であらわすと、

XXXX OOOOO XX

のように、「あるゴーレムより左は左側で消える」「あるゴーレムより右は右側で消える」という境界が出来ます。この境界をそれぞれ2分探索で求めれば残るゴーレムの数がわかります。あるゴーレムが落ちるか否かの判定は 回の呪文すべてを辿ればよく、計算量は となります。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int N, Q;
string s;
vector<char> t, d;

bool vanish(int n, int m){
    // 初期位置 n のゴーレムが消えるか否かを判定。
    //  m=0：左で消えるとき true, それ以外のときfalse
    //  m=1：右で消えるとき true, それ以外のときfalse

    int x = n-1;  // 文字列 s は 0-indexed なので調整する
    int L = s.length();
    for(int i=0; i<Q; i++){
        if(t[i]==s[x]){
            x += (d[i]=='R' ? 1:-1);
            // ゴーレムが左か右にはみ出たらループを抜ける
            if(x==-1 || x==L) break;
        }
    }

    if(x==-1 && m==0){
        return true;
    }else if(x==L && m==1){
        return true;
    }else{
        return false;
    }
}

int main(){    
    cin >> N >> Q >> s;
    t = vector<char>(Q);
    d = vector<char>(Q);
    for(int i=0; i<Q; i++) cin >> t[i] >> d[i];

    // 左で消えるゴーレムの境界を求める
    int l1 = 0, r1 = N+1;    
    while(r1 - l1 > 1){
        int mid = l1 + (r1 - l1)/2;
        if(vanish(mid, 0)){
            l1 = mid;
        }else{
            r1 = mid;
        }
    }

    // 右で消えるゴーレムの境界を求める
    int l2 = 0, r2 = N+1;
    while(r2 - l2 > 1){
        int mid = l2 + (r2 - l2)/2;
        if(vanish(mid, 1)){
            r2 = mid;
        }else{
            l2 = mid;
        }
    }
    
    if(l2 >= r1){
        cout << l2 - r1 + 1 << endl;
    }else{
        cout << 0 << endl;
    }
}

D - Modulo Operations

https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_d

方針

　　 = はじめ黒板に書かれた整数が だったとき、 で題意の操作を行って得られる 個の値の和
とします。求めるものは です。

まず を昇順にソートしておきます。 です。
次に がわかっているときに がどのように求められるかを考えます。ここで の順列の中に を挿入すると考えます。

(1) を一番最初に挿入するとき
黒板に最初に書く整数を として、 で題意の操作をした場合と同じ結果になります。このような の並び方の数は 通りあり、求める和は です。

(2) それ以外の時
であることを利用します。 を先頭以外のどこに挿入する場合も、 は で割ったあまりを取る直前の時点で よりも小さな値になっています (すでに より小さい他の で割ったあまりを取られているため)。よってこのとき「 で割ったあまりを取る」という操作で は変化しません。

このような の並び方の数は 通りあります。 の場合の 個の値の和は で、 通りある の挿入箇所のいずれも結果に影響しないので、求める和は です。

以上より
　　
となり、この漸化式を用いることで で答えを求められます。

ソースコード

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    int mod = 1e9+7;
    int N, X;
    cin >> N >> X;
    vector<int> S(N+1);
    for(int i=1; i<=N; i++) cin >> S[i];
    sort(S.begin(), S.end());

    vector<vector<ll>> dp = vector<vector<ll>>(X+1, vector<ll>(N+1, 0));
    for(int x=0; x<=X; x++){
        dp[x][1] = x%S[1];
    }
    
    for(int n=1; n<N; n++){
        for(int x=0; x<=X; x++){
            dp[x][n+1] = (dp[x%S[n+1]][n] % mod + dp[x][n] * n % mod) % mod;
        }
    }
    cout << dp[X][N] << endl;
}