超微減
— ボンド@競プロ (@bond_cmprog) January 23, 2021
Bondo416さんのAtCoder Beginner Contest 189での成績：1207位
パフォーマンス：1428相当
レーティング：1432→1431 (-1) :(#AtCoder #ABC189 https://t.co/ghKU7XwNH4
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; }
