ABC82 メモ

A - Round Up the Mean

$a$と$b$を足して2で割った計算結果を切り上げる。

これは$a+b+1$を2で割って切り捨てたものと等しい。

82A.py

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

ans = (a+b+1)//2
print(ans)

B - Two Anagrams

$s$と$t$を一度リストにして、$s$を昇順、$t$を降順にそれぞれ並び替え、文字列に戻す。

文字列同士の比較演算は、辞書順で比較されるため、問題文通りそのまま比較。

82B.py

s = input()
t = input()

s = list(s)
t = list(t)

s.sort()
t.sort(reverse=True)

s = ''.join(s)
t = ''.join(t)

ans = 'No'

if s < t:
    ans = 'Yes'

print(ans)

C - Good Sequence

$x$が$x$個含まれない場合、全て取り除く必要があり、$x$個以上含まれている場合、その差分だけ取り除けば良い。そのためには$x$が何個含まれているかを数える必要がある。

ここで、$1\leq x \leq 10^9$より、リストで管理すると大きくなり過ぎてしまうので、辞書で管理する。

82C.py

N = int(input())
alst = list(map(int, input().split()))

d = dict()
for i in range(N):
    a = alst[i]
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

ans = 0

for i in d.keys():
    if d[i] >= i:
        ans += (d[i]-i)
    else:
        ans += d[i]

print(ans)

D - FT Robot

まず、与えられた文字列を、移動と方向転換に分割する。つまり、Fの連続する数だけ進む移動を、Tで区切る、と考える。

例えば、"FFTFFFTFTTFFF"であれば、[2, 3, 1, 0, 3]と移動する。

移動を観察すると、偶数回目の移動においては$y$軸方向にしか移動できず、奇数回目の移動は$x$軸方向にしか移動できないことがわかる。また、$x$軸方向の移動は$y$軸方向の移動に制約を与えないので、$x$軸方向に$x$に到達できるか、$y$軸方向に$y$に到達できるかを独立に考えて、両方が可能である場合、指定された座標に到達可能である。

また、$x$軸方向への移動について、1回目の移動は$x$軸方向正の向きしか行えないが、2回目以降は、正の向き、負の向きをそれぞれ自由に選択できることがわかる。$x$軸方向に移動できる歩数のリストについて、合計を$S$とする。正の向きに移動するとしたものをリストからいくつか選択し、その時の合計を$A$とする。このとき、$A$だけ正の向きに移動し、$S-A$だけ負の向きに移動することがわかる。このとき、最終的な座標は$A-(S-A)=2A-S$より、$2A-S$であるとわかる。これが指定された$x$と一致するようなAが存在すれば良い。

つまり、「各軸方向の移動の数列について、うまく部分和をとることで、与えられた座標に到達できるか」と言い換えることができる。

部分和の計算はDPを用いて計算量が$O(|s|^2)$であり、今回の制約では間に合う。

(計算量の見積もりはあっているのかわからないです。)

82D.py

def calc(lst, s):
    S = sum(lst)
    dp = []

    for i in range(len(lst)+1):
        tmp = [0]*(S+1)
        dp.append(tmp)

    dp[0][0] = 1
    for i in range(len(lst)):
        n = lst[i]
        for j in range(S+1):
            if dp[i][j]:
                dp[i+1][j] = 1
                if j+n < S+1:
                    dp[i+1][j+n] = 1


    if (S+s)%2 or S < s or -S > s:
        return False
    else:
        return dp[-1][(S+s)//2]

s = input()
x, y = map(int, input().split())

lst = list(s.split('T'))
x -= len(lst[0])

Xlst = []
Ylst = []

for i in range(1, len(lst)):
    if i%2:
        Ylst.append(len(lst[i]))
    else:
        Xlst.append(len(lst[i]))

ans = 'No'

if calc(Xlst, x) and calc(Ylst, y):
    ans = 'Yes'

print(ans)