AtCoder Beginner Contest 173の感想

AtCoder

2020.07.06

ABC173に参加した。

AtCoder Beginner Contest 173 - AtCoder

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

A – Payment

1000で割った余りを1000から引く。

余り0だったら答えが1000になるのを避けるためにもう一度余りを取る。

n = int(input())
ans = 1000 - n % 1000
ans %= 1000
print(ans)

B – Judge Status Summary

xと×を間違えない。

Counterを使っても良かったが、思考停止で全部手書きした。

n = int(input())
s = [input() for _ in range(n)]

print('AC x ' + str(s.count('AC')))
print('WA x ' + str(s.count('WA')))
print('TLE x ' + str(s.count('TLE')))
print('RE x ' + str(s.count('RE')))

C – H and V

１<= H, W <= 6なのでO(2^n)が間に合うなーという気持ちになる。

行、列を選ぶか選ばないかの二択なので、bit全探索が使える。

全パターンを列挙できたら総当り。

import copy

h, w, k = map(int, input().split())
c = [list(input()) for _ in range(h)]

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

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

ans = 0
for hp in hpattern:
    for wp in wpattern:
        cc = copy.deepcopy(c)
        for i in range(h):
            for j in range(w):
                if hp[i] == 1:
                    cc[i][j] = -1
                if wp[j] == 1:
                    cc[i][j] = -1

        black = sum([l.count('#') for l in cc])
        if black == k:
            ans += 1

print(ans)

D – Chat in a Circle

まずはソートする。

直感的に、最後の人は心地よさに貢献しない。

一人目のフレンドリーさは二人目の心地よさにしか貢献しない。

以上より、1〜n-1の範囲で考える。

フレンドリーが高い人の両隣に順番に入っていけば心地よさを最大化できる。

両隣に人が割り込んでいった場合、フレンドリーAiを２回心地よさに加えることが可能なので、上から順番に２個ずつ加算していけばOK。

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)

ans = a[0]
for i in range(1, n - 1):
    ans += a[-(-i//2)]

print(ans)

レートが上がったり下がったりで中々緑に上がれない。