eijit's blog

AtCoder Beginner Contest 137 参加

AtCoder Beginner Contest 137 に参加した。今回は ABC 3 完答 の 1885 位でパフォーマンスは 974 だった。

以下のコードは PyPy3 (2.4.0) で AC を確認している。

問題 A

\(A + B, A - B, A \times B\) の最大値を表示せよという問題なので、そのまま計算した。

A, B = map(int, input().split())
print(max(A + B, A - B, A * B))

問題 B

設問の制約から黒石が左右の端に到達することを考えなくても良い。

  • 黒石が最も左に伸びるのは X が右端であった場合
  • 黒石が最も右に伸びるのは X が左端であった場合

なのでその時の左右とその間の座標の数字を空白区切りで出力すれば良い。

K, X = map(int, input().split())
LR = range(X - K + 1, X + K)
print(' '.join(map(str, LR)))

問題 C

2 つの文字列がアナグラムとして一致するかどうかを判定するには、両方の文字列をソートしてから比較すれば良い。例えば問題文に例示されている greenbin と beginner をソートすればともに beeginnr となり一致を容易に判定できる。

解説よりややこしくなっているがコンテスト中は下記のように考えた。

  1. 各入力文字列 \(s_i\) をソートする
  2. S = [\(s_1\), \(s_2\), ..., \(s_N\)] をソートする
  3. 一致する要素の個数を数え上げる

最初は雑に二重ループを回して TLE を食らった。一致する要素がある間はカウントアップして、値が変わったらカウンタをリセットする方針で実装して通した。なお個数の数え上げについては、一致するものの個数が \(c\) の場合に \(1\) から \(c - 1\) の総和となる。

N = int(input())
S = []
for i in range(N):
    S.append(input())
# print(N, S)

for i in range(len(S)):
    s = S[i]
    t = list(s)
    t.sort()
    S[i] = ''.join(t)

S.sort()
# print(S)

ans = 0
count = 0
for i in range(N - 1):
    si = S[i]
    sj = S[i + 1]
    if si != sj:
        ans += count * (count + 1) // 2
        count = 0
    else:
        count += 1
        if i == N - 2:
            # 最後の足し忘れ防止
            ans += count * (count + 1) // 2

print(ans)

問題 D

コンテスト中に AC できず。最初は、初日から考えて受取可能なもののうちで報酬の高いものから埋めていく方針で考えたが、サンプルケースが通るので意気揚々と提出したものの WA を食らった。今度は逆に最終日から埋めていく方針にしたが、日数と報酬のどちらを優先してソートしてもうまく行かず時間切れとなった。解説を読みつつ理解したが、やはり日数の制約の中で最も報酬の高いものを調べて選ぶ必要があった。

コンテスト後に改めて実装して AC した。方針は優先度付きキューを 2 つ使って

  1. 日付優先で 1 つ目のキューに入力を貯める
  2. 残日数が少ない方から考える
  3. 残日数内のものを 1 つ目のキューから取り出して、報酬優先 (高いものが先頭に来るように -1 倍している) で 2 つ目に追加する
  4. 2 つ目のキューから取り出して得られる報酬に加算する

という方針で実装した。

import heapq

N, M = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    heapq.heappush(AB, (a, b))

# print(N, M, AB)

ans = 0
work = []
for i in range(M):
    remain = i + 1
    # print('remain={}, AB={}, ans={}'.format(remain, AB, ans))
    while len(AB) > 0:
        ab = heapq.heappop(AB)
        if ab[0] > remain:
            heapq.heappush(AB, ab)
            break
        heapq.heappush(work, (-ab[1], ab[0]))
    if len(work) == 0:
        continue
    v = heapq.heappop(work)
    ans -= v[0]
    # print('work={}'.format(work))
print(ans)

Published

Category

Programming

Tags

Contact