AtCoder Beginner Contest 261の感想

リアルタイムで参加した。

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

A – Intersection

両端を求めて差を取るだけ。

距離を求めるので、計算結果がマイナスになったら0し忘れないようにする。

l1, r1, l2, r2 = map(int, input().split())

ans = min(r1, r2) - max(l1, l2)
ans = max(ans, 0)

print(ans)

計算量はO(1)

B – Tournament Result

愚直に実装。条件分岐に注意。

if分に二次元配列の添字を毎回かくのは面倒なので、一度xやyなどの変数に入れておくと記述が楽。

n = int(input())

a = [input() for _ in range(n)]

for i in range(n):
    for j in range(n):
        x = a[i][j]
        y = a[j][i]
        if (x == 'W' and y != 'L') or (x == 'L' and y != 'W') or (x == 'D' and y != 'D'):
            print('incorrect')
            exit()

print('correct')

計算量はO(N^2)

C – NewFolder(1)

文字列のカウントを辞書に格納しておき、フォーマット文字列（f文字列）を使って出力。

n = int(input())

table = {}
for _ in range(n):
    s = input()

    if s in table:
        print(f'{s}({table[s]})')
        table[s] += 1
    else:
        print(s)
        table[s] = 1

計算量はO(N)。

すべての文字列が異なる場合はメモリもO(N)必要。

D – Flipping and Bonus

値を更新しながら最大値を求める問題なので、貪欲やDPを疑う。

手書きで実験してみると、コインを投げた回数とカウンタ数の二次元表で値を更新出来ることに気づくので、DPで実装していく。

ボーナスの辞書とDPの配列を用意し、初期値を設定。

カウントは0〜nのn＋1通りあるので配列の数に注意する。

1つ前のコイントスの結果によって次のコイントスの結果が変わるので、コイントス1回目のケースで初期化。

カウント1でもボーナスがある場合があるので、別途条件分岐。

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

bonus = {c: y for c, y in cy}

dp = [[0] * (n + 1) for _ in range(n)]
dp[0][1] = x[0]
if 1 in bonus:
    dp[0][1] += bonus[1]

コイントスとカウント数でDPを行う。

もし今のカウントが0だった場合、1つ前までのコイントスの最大値から再スタートすることとになる。

カウントが1以上の場合、1つ前のコイントスとカウントから値を更新し、さらにボーナスがあれば加算する。

全部のコイントスが終わった時の最大値が答え。

for coin in range(1, n):
    for count in range(coin + 2):
        if count == 0:
            dp[coin][0] = max(dp[coin - 1])
        else:
            dp[coin][count] = dp[coin - 1][count - 1] + x[coin]
            if count in bonus:
                dp[coin][count] += bonus[count]

ans = max(dp[n - 1])

print(ans)

E – Many Operations

同じ処理を繰り返していくのでandやorを合成して行きたいが、結合法則が成り立たないので別の方法を考える必要がある。

bitごとに独立した計算が可能（bit wise）なので、xx桁目の0が1になって、xx桁目の1はそのまま…のように各桁ごとに考える。

0がどう変化していくのか、1がどう変化していくのかを記録する変数を用意する。

全部の桁が1になる数はnot 0（~0）で表わせられる。

n, c = map(int, input().split())
x = c

zero = 0
one = ~0

zeroとoneをクエリ毎に計算させていき、最後にxを出力する。

xが1の桁だけ取り出したい時はone & xで求まり、0になっている桁は zero & not xで求まる。

これらの結果をorで繋いだものが求める答え。

for i in range(n):
    t, a = map(int, input().split())

    if t == 1:
        zero &= a
        one &= a
    elif t == 2:
        zero |= a
        one |= a
    else:
        zero ^= a
        one ^= a

    x = (one & x) | (zero & ~x)

    print(x)

計算量はO(N)。