Cまで届かなかった。前日飲みすぎてダルかったので今後は酒を控えたい所存。
A. On the Way
Pythonでやった。
A, B, C = [int(i) for i in input().split()]
min_n = min(A, B)
max_n = max(A, B)
if min_n < C and max_n > C:
print("Yes")
else:
print("No")
B. *e**** ********e* *e****e* ****e**
文字列走査するならC++かなと思ってC++でやった。
#include <bits/stdc++.h>
using namespace std;
int main(void){
int N, K;
string S;
cin >> N >> S >> K;
char target;
target = S.at(K-1);
for (int i = 0; i < S.size(); i++) {
if (S.at(i) == target) {
cout << target;
} else {
cout << '*';
}
}
cout << endl;
}
C. Stones
(分割してカウントするんだよな…)と思ってこういうの書いてしまっていた。
N = int(input())
S = input().strip()
def stone_cnt(idx):
return S[:idx].count("#") + S[idx:].count(".")
left = 0
right = len(S)
ans = min([stone_cnt(i) for i in range(N+1)])
print(ans)
O(N²)なのでもちろんTLEだ。「境界を動かしたらカウントがどうなるか」に注目すればO(N)で解けるというのは冷静に考えれば分かりそうだったのに、冷静ではなかった。酒を飲んではいけない。
C++版の回答。
#include <bits/stdc++.h>
using namespace std;
int main(void){
int N;
string S;
cin >> N >> S;
int lb = 0;
int rw = count(S.begin(), S.end(), '.');
int ans = lb + rw;
for (int i = 0; i < N; i++) {
if (S.at(i) == '.') {
rw--;
} else {
lb++;
}
ans = min(ans, lb + rw);
}
cout << ans << endl;
}
Python版の回答。
N = int(input())
S = input().rstrip('#')
lb = 0
rw = S.count('.')
ans = lb + rw
for i in range(len(S)):
if S[i] == '.':
rw -= 1
else:
lb += 1
ans = min(ans, rw + lb)
print(ans)
D. Three Colors
解説だけ読んでもよく分からなくて、他の人の回答を見てやっと理解できた。
Python版。TLEになる。他の人の回答を見ると少し最適化すれば通るっぽい。
ちなみにAtCoderのPyPyにはNumPyが無いっぽいので、そのままPyPy3に切り替えるという手は使えない。NumPy外してPyPy使ってみたりもしたけど私の能力ではやっぱりTLEだった。
import numpy as np
import math
MOD = 998244353
N = int(input())
a = np.array([int(input()) for _ in range(N)])
S = sum(a)
dp1 = np.zeros((N + 1, S + 1))
dp1[0, 0] = 1
dp2 = np.zeros((N + 1, S + 1))
dp2[0, 0] = 1
for i, x in enumerate(a):
dp1[i+1, :] += dp1[i, :] * 2 % MOD
dp1[i+1, x:] += dp1[i, :-x] % MOD
dp2[i+1, :] += dp2[i, :] % MOD
dp2[i+1, x:] += dp2[i, :-x] % MOD
pat = 3 ** N % MOD
s1 = 3 * sum(dp1[N, math.ceil(S / 2):]) % MOD
s2 = 3 * dp2[N, S // 2] % MOD if S % 2 == 0 else 0
print(int(pat - s1 + s2) % MOD)
C++版。これは通る。通るが、結構ハマりどころがあったので(%
が負数を返すパターンへの対処とか多次元配列の合計のとり方とか)もう少し練習しないと本番の時間内では実装できない感じがある。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;
ll mod(ll n, ll m) {
ll res = n % m;
if (res < 0) res += m;
return res;
}
ll modpow(ll a, ll n, ll mod) {
ll res = 1;
while (n > 0) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
int main(void){
ll N;
cin >> N;
vector<ll> a(N);
for (int i = 0; i < N; i++) {
cin >> a.at(i);
}
ll S = accumulate(a.begin(), a.end(), 0);
vector<vector<ll>> dp1(N+1, vector<ll>(S+1, 0));
vector<vector<ll>> dp2(N+1, vector<ll>(S+1, 0));
dp1.at(0).at(0) = 1;
dp2.at(0).at(0) = 1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < S; j++) {
dp1.at(i+1).at(j) += dp1.at(i).at(j) * 2 % MOD;
dp2.at(i+1).at(j) += dp2.at(i).at(j) % MOD;
}
for (int j = a.at(i); j < S+1; j++) {
dp1.at(i+1).at(j) += dp1.at(i).at(j-a.at(i)) % MOD;
dp2.at(i+1).at(j) += dp2.at(i).at(j-a.at(i)) % MOD;
}
}
ll pat;
pat = modpow(3, N, MOD);
ll s1 = 0;
ll s2 = 0;
if (S % 2 == 0) {
for (int i = S/2; i < S+1; i++) {
s1 += 3 * dp1.at(N).at(i);
s1 %= MOD;
}
s2 = 3 * dp2.at(N).at(S / 2);
} else {
for (int i = S/2+1; i < S+1; i++) {
s1 += 3 * dp1.at(N).at(i);
s1 %= MOD;
}
}
cout << mod(pat - s1 + s2, MOD) << endl;
}