【Python3】【ABC137】AtCoder Beginner Contest 137 参加記録 (Dまで)

最近 AtCoder に割く時間を全く取れず、成績もどんどん下がってしまっています。。忙しくても 1 日 1 AC くらいはキープしていきたい気持ち。

さて、今回は ABC 137 を解きました。コンテスト中には D の TLE を解消できず 3 完という悲惨な感じでしたが、復習を通して heapq という便利な概念を新しく習得したのでそれのまとめもしながら振り返っていきます。

ABC137 A – +-x

整数 \(A, B\) があります。 \(A+B,  A−B,  A×B\) の中で最大の数を出力してください。

https://atcoder.jp/contests/abc137/tasks/abc137_a

そのままですね。

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

ABC137 B – One Clue

数直線上に \(2000001\) 個の石が置かれています。これらの石の座標は −1000000, −999999, −999998, …, 999999, 1000000 です。
これらの石のうち、ある連続する \(K\) 個の石が黒で塗られており、それ以外の石は白で塗られています。
また、座標 \(X\) にある石は黒で塗られていることが分かっています。
黒で塗られている石が置かれている可能性のある座標をすべて、小さい順に出力してください。

https://atcoder.jp/contests/abc137/tasks/abc137_b

要するに [X - K + 1, X + K - 1] の区間を出力すればいいわけです。あとは出力方法だけ気をつけて書けば OK です。

サトゥー

僕は list に全部入れてから join して空白区切りで出力しました、もっと賢い方法がありそう

K, X = map(int, input().split())
ans = []
for i in range(X - K + 1, X + K):
        ans.append(i)
print(" ".join(map(str, ans)))

ABC137 C – Green Bin

文字列 \(a\) に含まれる文字を何らかの順序で並べることで得られる文字列を \(a\) の アナグラム と呼びます。
例えば、"greenbin" は "beginner" のアナグラムです。このように、同じ文字が複数回現れるときはその文字をちょうどその回数だけ使わなければなりません。
\(N\) 個の文字列 \(s_1,s_2,…,s_N\) が与えられます。それぞれの文字列は長さが \(10\) で英小文字からなり、またこれらの文字列はすべて異なります。二つの整数 \(i,j (1 \leq i < j \leq N)\) の組であって、\(s_i\) が \(s_j\) のアナグラムであるようなものの個数を求めてください。

https://atcoder.jp/contests/abc137/tasks/abc137_c

とりあえずめんどくさそうなので文字列は全部ソートしておくと、アナグラムの判定は文字列が一致するかどうかを見ればよくなります。

python の collections モジュールの collections.Counter を利用して、同じ文字列の出現回数を記録し、その回数 \(n\) ごとに \( _n C_2\) を足していけば答えが得られますね。

import collections
N = int(input())
s = ["".join(sorted(input())) for _ in range(N)]
c = collections.Counter(N)
ans = 0
for si in set(s):
    n = c[si]
    ans += n * (n-1) // 2
print(ans)

ABC137 D – Summer Vacation

\(N\) 件の日雇いアルバイトがあり、\(i\) 件目の日雇いアルバイトを請けて働くと、その \(A_i\) 日後に報酬 \(B_i\) が得られます。
あなたは、これらの中から \(1\) 日に \(1\) 件まで選んで請け、働くことができます。
ただし、請けたことのある日雇いアルバイトは選べません。
今日から \(M\) 日後まで(\(M\) 日後を含む)に得られる報酬の合計の最大値を求めてください。
なお、日雇いアルバイトは今日から請けて働くことができます。

https://atcoder.jp/contests/abc137/tasks/abc137_d

選べる仕事の選択肢は後半になるほど制約が厳しくなっていくことがわかります。こういうときに前から見ていくとあとでつらくなるので、制約の強い後ろから見ていくことにします。

すると、次のように考察できます。

• \(M – i\) 日後（ \(1 \leq i \leq M\) ）には、 \(A_j \leq i\) となるバイトしか出来ないとみなしても良い
• つまり、 \(A_j \leq i\) となる \(j\) の中で、 \(B_j\) が最大になるものを取り出して考えていけば良い

候補の追加と最大値の取り出しを繰り返し行う実装になるはずなので、Python の heapq というモジュールを利用することでうまくいきます。

今回利用した heapq についてはこちらに調べた内容をメモしました。

Python の heapq について調べたのでメモ【AtCoder】【Python3】

先日の ABC137 の D 問題を解く際に、 Python の heapq について軽く調べたのでメモを残し…

blog.satoooh.com

from heapq import heappop, heappush
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])
hq = []
ans, j = 0, 0
for i in range(1, M + 1):  # M - i 日後にするバイトを考える
    while (j < N) and (X[j][0] <= i):
        heappush(hq, -X[j][1])  # 候補の追加
        j += 1
    if len(hq):
        ans += -heappop(hq)  # 候補があるとき、候補から最大値を取り出す
print(ans)