AtCoder Beginner Contest 290の参戦記です。
A - Contest Result
考察
A[B[i] - 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
inf = 1 << 60
def main():
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = 0
for b in B:
ans += A[b-1]
print(ans)
if __name__ == "__main__":
main()
B - Qual B
考察
oがKを超えるまではそのままでその後は全部x
コード
ソースコードを表示（折りたたみ）
#!/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
inf = 1 << 60
def main():
N, K = map(int, input().split())
S = input()
ans = []
cnt = 0
for s in S:
if s == "x":
ans.append("x")
else:
if cnt >= K:
ans.append("x")
else:
cnt += 1
ans.append("o")
print(''.join(ans))
if __name__ == "__main__":
main()
C - Max MEX
考察
とりあえず同じもの選んでも意味ないのでAの重複を削除
ソートして0からforで回してiと違うものが出てきたらそれが答。
Kを超えてたらKが答。
コード
ソースコードを表示（折りたたみ）
#!/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
inf = 1 << 60
def main():
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(set(A))
B.sort()
cnt = 0
for i in range(len(B)):
if i != B[i]:
print(i)
return
if cnt == K:
print(cnt)
return
cnt += 1
print(max(B) + 1)
if __name__ == "__main__":
main()
D - Marking
考察
Kが10**9までで非常に大きいのであまりとか使うんだろうと思う。
とりあえず同じ数字に戻って来る回数考えよう。
base = lcm(N, D) // Dが同じ数字に戻ってくる回数。
K // baseが基本値。それにK % base * Dを足すとよさそう。
逐一modを取るのを忘れずにやる。
コード
ソースコードを表示（折りたたみ）
#!/usr/bin/env python3
from collections import defaultdict
from math import gcd
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
inf = 1 << 60
def lcm(a, b):
return a * b // gcd(a, b)
def main():
T = int(input())
for _ in range(T):
N, D, K = map(int, input().split())
K -= 1
D %= N
base_cnt = N // gcd(N, D)
ans = K // base_cnt
ans += K % base_cnt * D % N
ans %= N
print(ans)
if __name__ == "__main__":
main()
E - Make it Palindrome
考察
主客転倒だろうなぁと考えた。
自分より前のやつと何回比較するかを考えたときに
入力
5
5 2 1 2 2
0番目の5は自分より前のやつがいないので0
1番目の2は5と1回だけ
2番目は5と1回、2と2回
3番目は5と1回、2と2回、1と2回
4番目は5と1回、2と1回、1と1回、2と1回
基本となるのが1,2,3,...という等差数列で、N - iとの最大値と比較してminが値となる
# 全部違う場合
val = (i + 1) * i // 2
val -= (i - mx) * (i - mx + 1) // 2
ここから同じ場合を引けば良さそう。
mx = min(i, N - i)としてそれ以上の場合と、それ未満の場合に分けて引く。
未満の場合の分は累積和を使う。
コード
ソースコードを表示（折りたたみ）
#!/usr/bin/env python3
from bisect import bisect_left
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
inf = 1 << 60
def main():
N = int(input())
A = list(map(int, input().split()))
indexes = [[] for _ in range(N + 1)]
arr = [[0] for _ in range(N + 1)]
ans = 0
for i in range(N):
mx = min(i, N - i)
# 全部違う場合
val = (i + 1) * i // 2
val -= (i - mx) * (i - mx + 1) // 2
# mx 未満の個数
idx = bisect_left(indexes[A[i]], mx)
# mx 以上の個数にmxをかけて引く
val -= (len(indexes[A[i]]) - idx) * mx
# mx 未満の場合は累積和を使う
val -= arr[A[i]][idx]
ans += val
indexes[A[i]].append(i)
arr[A[i]].append(arr[A[i]][-1] + (i + 1))
print(ans)
if __name__ == "__main__":
main()
コンテスト結果
感想
Cでfor回す回数失敗したり、EでNじゃなくて5とかサンプルにしか通用しないマジックナンバー使ってたりで2WA
ただ久々の青perfでした。