接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

AtCoder Beginner Contest 189(ABC189)

atcoder.jp

A - Slot

$ C_1 \neq C_2 $ かつ $ C_2 \neq C_3 $ のときWon
それ以外の場合Lost
提出コード

void solve(){
    char c1, c2, c3;
    cin >> c1 >> c2 >> c3;
    if(c1 == c2 and c2 == c3) cout << "Won" << endl;
    else cout << "Lost" << endl;
}

B - Alcoholic

誤差があるので整数同士での比較にする
$ i $番目のアルコールを飲んだ時に$ V_1 P_1 + V_2 P_2 + ... + V_i P_i \gt 100X $
となる$ i $を出力すればいい
提出コード

void solve(){
    int N;
    ll X;
    cin >> N >> X;
    ll cur = 0;
    X *= 100;
    REP(i,N){
        ll V, P;
        cin >> V >> P;
        cur += V * P;
        dump(cur);
        if(cur > X){
            cout << i + 1 << endl;
            return;
        }
    }
    cout << -1 << endl;
}

C - Mandarin Orange

$ \mathcal{O}(N^2) $が通るので全ての区間について計算すればいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];
    ll ans = 0;
    REP(i,N){
        ll mi = LINF;
        for(int j=i;j<N;j++){
            chmin(mi, A[j]);
            chmax(ans, mi * (j-i+1));
        }
    }
    cout << ans << endl;
}

D - Logical Expression

$ dp[i][j] := i $番目を見ているときにその状態が$ j $のときの場合の数としてdpをする
$ j = 0 $のときFalse $ j = 1 $のときTrueとすると$ dp[N][1] $が答え
提出コード

void solve(){
    int N;
    cin >> N;
    vector<string> S(N);
    REP(i,N){
        cin >> S[i];
    }
    vector dp(N+1, vector(2, 0LL));
    dp[0][0] = dp[0][1] = 1;
    REP(i,N){
        if(S[i] == "OR"){
            // trueを選ぶ
            dp[i+1][1] += dp[i][0];
            dp[i+1][1] += dp[i][1];
            // falseを選ぶ
            dp[i+1][1] += dp[i][1];
            dp[i+1][0] += dp[i][0];
        }
        else{
            // true
            dp[i+1][1] += dp[i][1];
            dp[i+1][0] += dp[i][0];
            // false
            dp[i+1][0] += dp[i][0];
            dp[i+1][0] += dp[i][1];
        }
    }
    cout << dp[N][1] << endl;
}

E - Rotate and Flip

各操作を変換行列で表すと予め累積積を求めておくことで$ M $回目の操作ついて$ \mathcal{O}(1) $で求められる
操作$ i $の変換行列を$ A_i $とすると各変換行列は以下のようになる
$$ A_1 = \left( \begin{array}{ccc} 0 & 1 & 0 \\ -1 & 0 & 0 \\ 0 & 0 & 1 \end{array} \right) $$ $$ A_2 = \left( \begin{array}{ccc} 0 & -1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{array} \right) $$ $$ A_3 = \left( \begin{array}{ccc} -1 & 0 & 2p \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right) $$ $$ A_4 = \left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & -1 & 2p \\ 0 & 0 & 1 \end{array} \right) $$ $ i $回目までの変換行列の積を$ B_i $とすると$ j $の$ i $回目の操作後の座標は $$ B_i \left( \begin{array}{c} X _j \\ Y _j \\ 1 \end{array} \right) $$ で求められる
提出コード

mat mul(mat& A,mat& B){
    mat C(A.size(), vec(B[0].size()));
    for(int i=0;i<A.size();i++){
        for(int j=0;j<B[0].size();j++){
            for(int k=0;k<A[0].size();k++){
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return C;
}

void solve(){
    int N;
    cin >> N;
    vector<mat> a(N, vector(3, vector(3, 0LL)));
    REP(i,N){
        int X, Y;
        cin >> X >> Y;
        a[i] = mat(3, vector(3, 0LL));
        a[i][0][0] = X;
        a[i][1][0] = Y;
        a[i][2][0] = 1;
    }
    int M;
    cin >> M;
    vector<mat> op(M+1, vector(3, vector(3, 0LL)));
    REP(i,M){
        int q;
        cin >> q;
        if(q == 1){
            op[i][0][1] = 1;
            op[i][1][0] = -1;
            op[i][2][2] = 1;
        }
        if(q == 2){
            op[i][0][1] = -1;
            op[i][1][0] = 1;
            op[i][2][2] = 1;
        }
        if(q == 3){
            ll p;
            cin >> p;
            op[i][0][0] = -1;
            op[i][0][2] = 2*p;
            op[i][1][1] = 1;
            op[i][2][2] = 1;
        }
        if(q == 4){
            ll p;
            cin >> p;
            op[i][0][0] = 1;
            op[i][1][1] = -1;
            op[i][1][2] = 2*p;
            op[i][2][2] = 1;
        }
    }
    REP(i,M-1) op[i+1] = mul(op[i+1], op[i]);
    int Q;
    cin >> Q;
    REP(i,Q){
        ll A, B;
        cin >> A >> B;
        --A, --B;
        if(A == -1){
            cout << a[B][0][0] << " " << a[B][1][0] << endl;
            continue;
        }
        auto tmp = mul(op[A], a[B]);
        cout << tmp[0][0] << " " << tmp[1][0] << endl;
    }
}

F - Sugoroku2

解説AC
$ dp[i] := $ マス$ i $からゴールまでに必要な回数の期待値とすると
$$ dp[i] = \begin{cases} \frac{dp[i+1] + dp[i+2] + \cdots + dp[i+M]}{M} + 1 & (マスiが振り出しじゃない) \\ dp[0] & (マスiが振り出し) \end{cases} $$ 求めたい答えを変数に置き換えると$( dp[0] = x )$
$ x = ax + b $の1次式で表すことが出来る
これを解くことで$ x = \frac{b}{1-a} $となり、$ dp[0] $を求めることが出来る
ただし、$ a = 1 $の時答えは-1となる
提出コード

void solve(){
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> A(N+10);
    REP(i,K){
        int a;
        cin >> a;
        A[a] = 1;
    }
    vector<pair<double, double>> dp(N+10);
    pair<double, double> sum = {0.0, 0.0};
    for(int i=N-1;i>=0;i--){
        if(A[i]) dp[i] = {1.0, 0};
        else{
            dp[i].first += sum.first / M;
            dp[i].second += sum.second / M + 1.0;
        }
        sum.first += dp[i].first;
        sum.second += dp[i].second;
        if(i + M <= N){
            sum.first -= dp[i+M].first;
            sum.second -= dp[i+M].second;
        }
    }
    if(dp[0].first + EPS > 1.0) cout << -1 << endl;
    else cout << setprecision(15) << dp[0].second / (1 - dp[0].first) << endl;
}