ABC216 参加記録

• 5完1ペナ 92分でした

A - Signed Difficulty

. で分離して取得するのが簡単です。 また、小数 で必ず小数部分の があるので例外処理など書かずに安心して取得できます。

出力に文字（ - や + ）を含める必要があるので、 は文字列として扱います。

X, Y = map(int, input().split('.'))
if Y <= 2: print(str(X)+'-')
elif Y <= 6: print(str(X))
else: print(str(X)+'+')

B - Same Name

誰が誰と重複したかなどは考えずに答えられそうです。

順に名前を取得していき、前に一致するものがあったら Yes として出力します。全て格納できたら No です。

また姓名の両方が一致している場合なので、特に分けて保存する必要もありません。

N = int(input())
nameset = set()
for _ in range(N):
    name = input()
    if name in nameset: 
        print('Yes')
        return
    else: nameset.add(name)
print('No')

C - Many Balls

よく出る典型の問題の易しめ版ですね。

から 0 にしていくことを考えます。今回は最短の方法が直感的にもわかりやすく、奇数だったら 1 を引く、偶数だったら 2 で割る、とすれば良いです。

行った操作を記録して、最終的に出力するときには逆順にして出せばOKです。

N = int(input())
ans = []
while N > 0:
    if N%2 == 0:
        N //= 2
        ans.append('B')
    else:
        N -= 1
        ans.append('A')
ans.reverse()
print(''.join(ans))

D - Pair of Balls

実装問題でした。

本の筒は全体で持っておいて、実際に取り出すシミュレーションをする方針にしました。ちなみに取り出す順番は特に関係なく、見つけた順に取り出してしまって良いはずです（ダメな例を作れなかったという消極的な理由でした） 。

それぞれの筒の一番上のボールにおいて、どの色が同じになるか？を 以下で見つける必要があります。 私はどの色が何番めの筒にあるか？を辞書型で持っておき、取り出した後の色から取得できるようにしました。こうすることで筒の上のボールを探索することなく、この辞書から直接参照することができます。

ということで、シミュレーションは で実行できました。 各配列で、何もないのに取り出そうとするエラーには注意して実装します。

提出コード

from collections import deque
import sys

input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    colormap = dict()
    field = []
    checker = [0] * (N+1)
    que = deque([])
    for k in range(M):
        _ = int(input())
        C = list(map(int, input().split()))
        checker[C[0]] += 1
        if checker[C[0]] == 2: que.append(C[0])
        for c in C:
            if c not in colormap: colormap[c] = [k]
            else: colormap[c].append(k)
        C.reverse()
        field.append(C)
    
    # 同じ数字が同じ筒に入っていないかチェック
    for a, b in colormap.values():
        if a == b:
            print('No')
            return

    while que:
        # que を取り出す
        p = que.popleft()
        
        # 取り出した que から map を見て、pop する
        checker[p] -= 2
        j = colormap[p]
        field[j[0]].pop()
        field[j[1]].pop()
        # 次も同じ値なら一回入れてスキップ
        if len(field[j[0]]) > 0 and len(field[j[1]]) > 0:
            if field[j[0]][-1] == field[j[1]][-1]:
                que.append(field[j[0]][-1])
                checker[field[j[0]][-1]] += 2
                continue
        # そうじゃない場合
        for i in range(2):
            if len(field[j[i]]) > 0:
                a = field[j[i]][-1]
                checker[a] += 1

                # 筒のボールのチェックをする. 当たりならqueに入れる
                q, r = colormap[a]
                if q == j[i]: s = r
                else: s = q
                if field[s][-1] == a: que.append(a)

    # 残数チェック
    for l in field:
        if len(l) > 0:
            print('No')
            return
    print('Yes')


if __name__ == "__main__":
    main()

E - Amusement Park

の制約を見ておらず、heapq で実装して TLE もらいました。

ですね。愚直に は確かめられないので、もっと短縮できないか考えます。

この問題は単純に楽しさの大きい方からアトラクションに乗れば良いですが、乗った後楽しさは 1 ずつ減るので、いずれ他のアトラクションと同じになるときがきます。そこから先は、乗るアトラクションの選択肢が増えていきながら楽しさが全体で小さくなっていくような形です。

次のアトラクションと同じ楽しさになるまでは等差数列なので、簡単に和を求められます。アトラクションが増えていっても、やることは同じです。

問題は、途中で乗る回数が を超えてしまう場合です。この時は、同じ楽しさになっているアトラクションの数との商とあまりから、後どのくらい楽しめるか求められます。

ということで、アトラクションの数 に依存した計算方法なので で計算できます。 実装時の工夫としては、最初に楽しさ 0 のアトラクションをダミーで追加しておくと、例外処理がやりやすいです。

提出コード

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split())) + [0]
    A.sort()
    bf = A.pop()

    ans = 0; k = 1
    while K > 0:
        if len(A) > 0:
            af = A.pop()
        # 差分を加算
        if (bf - af)*k < K:
            ans += (((bf + af+1)*(bf-af))//2)*k
            K -= (bf - af)*k
            k += 1
        else:
            divK = K//k
            af = bf - divK
            ans += (((bf + af+1)*(bf-af))//2)*k
            remK = K%k
            ans += af*remK
            K -= divK*k + remK
        bf = af
        if bf == 0:
            break
    print(ans)


if __name__ == "__main__":
    main()