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でした。