ABC290参戦記(A-E)

AtCoder Beginner Contest 290の参戦記です。

https://atcoder.jp/contests/abc290

# A - Contest Result
https://atcoder.jp/contests/abc290/tasks/abc290_a

**考察**
A[B[i] - 1]を足し合わせる

**コード**
<details><summary>ソースコードを表示（折りたたみ）</summary><div>

```python
#!/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()

```

</div></details>

# B - Qual B
https://atcoder.jp/contests/abc290/tasks/abc290_b

**考察**
`o`がKを超えるまではそのままでその後は全部`x`

**コード**
<details><summary>ソースコードを表示（折りたたみ）</summary><div>

```python
#!/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()

```

</div></details>

# C - Max MEX
https://atcoder.jp/contests/abc290/tasks/abc290_c

**考察**
とりあえず同じもの選んでも意味ないのでAの重複を削除
ソートして0からforで回してiと違うものが出てきたらそれが答。
Kを超えてたらKが答。

**コード**
<details><summary>ソースコードを表示（折りたたみ）</summary><div>

```python
#!/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()

```

</div></details>

# D - Marking
https://atcoder.jp/contests/abc290/tasks/abc290_d

**考察**
Kが10**9までで非常に大きいのであまりとか使うんだろうと思う。
とりあえず同じ数字に戻って来る回数考えよう。
`base = lcm(N, D) // D`が同じ数字に戻ってくる回数。
`K // base`が基本値。それに`K % base * D`を足すとよさそう。
逐一modを取るのを忘れずにやる。

**コード**
<details><summary>ソースコードを表示（折りたたみ）</summary><div>

```python
#!/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()

```

</div></details>

# E - Make it Palindrome
https://atcoder.jp/contests/abc290/tasks/abc290_e

**考察**
主客転倒だろうなぁと考えた。
自分より前のやつと何回比較するかを考えたときに

入力
```
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`が値となる
```python
# 全部違う場合
val = (i + 1) * i // 2
val -= (i - mx) * (i - mx + 1) // 2
```
ここから同じ場合を引けば良さそう。
`mx = min(i, N - i)`としてそれ以上の場合と、それ未満の場合に分けて引く。
未満の場合の分は累積和を使う。

**コード**
<details><summary>ソースコードを表示（折りたたみ）</summary><div>

```python
#!/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()

```

</div></details>


# コンテスト結果
https://atcoder.jp/users/lazylazy/history/share/abc290

# 感想

Cでfor回す回数失敗したり、EでNじゃなくて5とかサンプルにしか通用しないマジックナンバー使ってたりで2WA
ただ久々の青perfでした。