AtCoder Beginner Contest 167の感想

AtCoder

2020.05.112020.05.12

ABC167に参加した。

AtCoder Beginner Contest 167 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A – Registration

文字列の長さと、1文字前までが一致しているか判定。

s = input()
t = input()

if len(s) + 1 == len(t) and s == t[:-1]:
    print('Yes')
else:
    print('No')

B – Easy Linear Programming

最大値を求める問題なので、点数が高くなるようA、B、Cの順にカードを取っていく。

残り枚数に注意しながら場合分け。

a, b, c, k = map(int, input().split())

ans = 0
if k < a:
    ans += k
else:
    ans += a
    k -= a
    if k >= b:
        k -= b
        if k > c:
            ans -= c
        else:
            ans -= k

print(ans)

C – Skill Up

N<12なので、全ての参考書を使う、使わないの2^12=4096通り全探索しても間に合う。

全か無かなのでbit全探索が適応できる。

import numpy as np

n, m, x = map(int, input().split())
ca = np.array([list(map(int, input().split())) for _ in range(n)])

pattern = []
for i in range(2 ** n):
    temp = [0] * n
    for j in range(n):
        if (i >> j) & 1:
            temp[j] = 1
    pattern.append(temp)

ans = 10 ** 10
for p in pattern:
    check = [0] * (m + 1)
    for i in range(n):
        if p[i] == 1:
            check += ca[i]
    flag = True
    for a in check[1:]:
        if a < x:
            flag = False
            break
    if flag:
        ans = min(ans, check[0])

print(ans) if ans != 10 ** 10 else print(-1)

D – Teleporter

どこかでループが発生するので、ループの開始場所と、ループの長さを求める。

kが膨大な数になっても、ループの長さで割って余り分だけ移動すればよく、計算量は余裕で間に合う。

最初のwhileでループの有無の判定。

2番めのwhileでループ開始場所の特定。

最後のwhileで実際に移動する。

今見返すと、最初のwhileは不要で、単にnとkの大小関係を比較すればいいのかもしれない。

n, k = map(int, input().split())
a = list(map(int, input().split()))

visited = [0] * (n + 1)
now = 1
check = 2 * n
loop_start = 1
while check > 0:
    if visited[now - 1] == 1:
        loop_start = now
        break
    else:
        visited[now - 1] += 1
        now = a[now - 1]
        check -= 1

visited = [0] * (n + 1)
now = loop_start
check = n
loop = 0
while check > 0:
    if visited[now - 1] == 1:
        break
    else:
        visited[now - 1] += 1
        now = a[now - 1]
        check -= 1
        loop += 1

now = 1
while k > 0:
    if now == loop_start:
        k %= loop
        if k == 0:
            break
    now = a[now - 1]
    k -= 1

print(now)

ABC過去問のC埋めも半分程終わり、茶色の折り返し地点である600に到達できた。