AtCoder Beginner Contest 275の参戦記です。
個人的な精進の記録として書きます。
初の6完だったので嬉しくて書きました。
A - Find Takahashi
考察
Hの最大値のindexを取ればOK
コード
ソースコードを表示（折りたたみ）
def main():
N = int(input())
H = list(map(int, input().split()))
idx = H.index(max(H))
print(idx + 1)
B - ABC-DEF
考察
C++だったら毎回modで割らないといけないけど、pythonだったらそのままでよさげ
コード
ソースコードを表示（折りたたみ）
def main():
A, B, C, D, E, F = map(int,input().split())
ans = A * B * C % mod2
ans -= D * E * F % mod2
ans %= mod2
print(ans)
C - Counting Squares
考察
斜めの正方形めんどくさくね？
原点周りの回転を求めるrotate関数あるからそれ使って、2点全探索したあと反時計回りに残りの2点決めたらいいか。
同じ正方形は4回数えるから最後に4で割ろう。
コード
ソースコードを表示（折りたたみ）
def rotate(p, theta):
x, y = p
ret = [0, 0]
ret[0] = x * math.cos(theta) - y * math.sin(theta)
ret[1] = x * math.sin(theta) + y * math.cos(theta)
ret[0] = round(ret[0])
ret[1] = round(ret[1])
return ret
def main():
S = [input() for _ in range(9)]
ans = 0
for i in range(9):
for j in range(9):
if S[i][j] != "#":
continue
for k in range(9):
for l in range(9):
if S[k][l] != "#":
continue
if i == k and j == l:
continue
m, n = rotate((k - i, l - j), math.radians(-90))
m += i
n += j
if m < 0 or 9 <= m or n < 0 or 9 <= n:
continue
o, p = rotate((i - k, j - l), math.radians(90))
o += k
p += l
if o < 0 or 9 <= o or p < 0 or 9 <= p:
continue
if S[m][n] == S[o][p] == "#":
ans += 1
print(ans // 4)
D - Yet Another Recursive Function
考察
・・・メモ化再帰？
コード
ソースコードを表示（折りたたみ）
def main():
memo = {}
memo[0] = 1
def f(x):
if x in memo:
return memo[x]
ret = f(x // 2) + f(x // 3)
memo[x] = ret
return ret
N = int(input())
print(f(N))
E - Sugoroku 4
考察
DPだな。
dp[i][j]:i回ルーレットを回したときのjにいる確率
として計算すれば行けそう。確率はMで割る代わりにMの逆元かければOK。
Nについたときにそれ以降進める必要はないから、jは0～N-1で回して最後に全部足そう。
コード
ソースコードを表示（折りたたみ）
#!/usr/bin/env python3
dpos4 = ((1, 0), (0, 1), (-1, 0), (0, -1))
dpos8 = ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1))
mod1 = 10**9 + 7
mod2 = 998244353
from math import inf
def main():
N, M, K = map(int, input().split())
# i回回したときにjにいる確率
dp = [[0] * (N + 1) for _ in range(K + 1)]
dp[0][0] = 1
mod_inv = pow(M, mod2 - 2, mod2)
for i in range(K):
for j in range(N):
for k in range(1, M + 1):
if j + k <= N:
dp[i + 1][j + k] += dp[i][j] * mod_inv % mod2
dp[i + 1][j + k] %= mod2
else:
dp[i + 1][N - (j + k - N)] += dp[i][j] * mod_inv % mod2
dp[i + 1][N - (j + k - N)] %= mod2
ans = 0
for i in range(K + 1):
ans += dp[i][N]
ans %= mod2
print(ans)
if __name__ == "__main__":
main()
F - Erase Subarrays
考察
Aの要素を使ってできる数値は
dp[i][j]:i番目までを使ってjができるかどうか。中身はbool
でできるからこれ使ってできないかな。
・・・boolじゃなくて操作回数を入れればいいんじゃない？
操作回数が増えるのってi-1番目の要素を使っててi番目の要素を使わないときにしか増えないような気がする
ということで
dp[i][j][k]:i番目まで使ってjができるとき（k=0:i番目を使わない k=1:i番目を使う）の操作回数
初期化
dp[0][0][1] = 0
計算量は3000*3000*2*4くらいなんだからPypyで出せば通るやろ。
コード
ソースコードを表示（折りたたみ）
#!/usr/bin/env python3
dpos4 = ((1, 0), (0, 1), (-1, 0), (0, -1))
dpos8 = ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1))
mod1 = 10**9 + 7
mod2 = 998244353
from math import inf
def main():
N, M = map(int, input().split())
A = list(map(int, input().split()))
# i番目まででjができたときの操作回数
dp = [[[inf] * 2 for _ in range(M + 1)] for _ in range(N + 1)]
dp[0][0][1] = 0
ans = [inf] * (M + 1)
for i in range(N):
a = A[i]
for j in range(M + 1):
if dp[i][j][0] != inf:
dp[i + 1][j][0] = min(dp[i + 1][j][0], dp[i][j][0])
if j + a <= M:
dp[i + 1][j + a][1] = min(dp[i + 1][j + a][1], dp[i][j][0])
if dp[i][j][1] != inf:
dp[i + 1][j][0] = min(dp[i + 1][j][0], dp[i][j][1] + 1)
if j + a <= M:
dp[i + 1][j + a][1] = min(dp[i + 1][j + a][1], dp[i][j][1])
for i in range(1, M + 1):
ans = min(dp[-1][i])
if ans == inf:
ans = -1
print(ans)
if __name__ == "__main__":
main()
結果
TLE
いけると思ったけど甘かった。
枝刈りとかちゃんとすれば通るんだろうけどわからんからC++で書き直すか・・・
コード(C++)
ソースコードを表示（折りたたみ）
#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
// using namespace atcoder;
using ll = long long;
const ll MOD1 = 1000000007LL;
const ll MOD2 = 998244353LL;
using namespace std;
const vector<pair<int, int>> dpos4 = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
// const vector<pair<int, int>> dpos8 = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
template <typename T>
bool chmax(T &a, const T &b) {
if (a < b) {
a = b; // aをbで更新
return true;
}
return false;
}
template <typename T>
bool chmin(T &a, const T &b) {
if (a > b) {
a = b; // aをbで更新
return true;
}
return false;
}
int main() {
int N, M;
cin >> N >> M;
vector<int> A(N);
rep(i, N) cin >> A[i];
vector<vector<vector<ll>>> dp(N + 1, vector<vector<ll>>(M + 1, vector<ll>(2, 1e18)));
dp[0][0][0] = 1;
dp[0][0][1] = 0;
for(int i = 0; i < N; i++){
int a = A[i];
for(int j = 0; j <= M; j++){
chmin(dp[i + 1][j][0], dp[i][j][0]);
chmin(dp[i + 1][j][0], dp[i][j][1] + 1);
if(j + a <= M){
chmin(dp[i + 1][j + a][1], dp[i][j][0]);
chmin(dp[i + 1][j + a][1], dp[i][j][1]);
}
}
}
for(int i = 1; i <= M; i++){
ll ans = min(dp[N][i][0], dp[N][i][1]);
if(ans >= 100000) ans = -1;
cout << ans << '\n';
}
return 0;
}
結果
無事AC
コンテスト結果
感想
Cの実装めんどくさいからDよりDif高そう。
EのDPは典型的なDPで逆元知ってるかどうかが問題な気がする。
Fの考察できちんとDPかけたのがだいぶ嬉しい。
そして初の6完。
枕を高くして眠れそうです。