AtCoder Beginner Contest 137 参戦記

ABC137A - +-x

2分半で突破. 書くだけ.

a, b = map(int, input().split())
print(max(a + b, a- b, a * b))

ABC137B - One Clue

4分で突破. 座標 X が右端のパターンと、左端のパターンを考えて、後は -k とか + k が突き抜けていないかを気にするだけ.

k, x = map(int, input().split())
l = max(-1000000, x - k + 1)
r = min(1000000, x + k - 1)
for i in range(l, r + 1):
  print(i)

ABC137C - Green Bin

26分半もかかってしまった上に、TLE×2, WA×1. WA は一回 // で書いた後、>> 1 にしようかと思いつつ、結局 // に戻した時に誤って / と書いたという凡ミス、泣く.
各文字列をアルファベティカルオーダーでソートすれば良いのは1秒で分かるので、後は2重 for で == な場合だけ += 1 するナイーブなコードを書いたが、PyPy でも TLE.
しょうがないので dict で各アナグラムの数を素直に数え上げて、_nC₂ を計算して合計して回答.

n = int(input())
s = [input() for _ in range(n)]
for i in range(n):
  s[i] = ''.join(sorted(s[i]))
t = {}
for i in range(n):
  if s[i] in t:
    t[s[i]] += 1
  else:
    t[s[i]] = 1
print(sum(t[k] * (t[k] -1) // 2 for k in t))

ABC137D - Summer Vacation

敗退. 見た瞬間にナップサックだ、DP だ、予習しててよかったと言いながら、EDP のときのコードを持ってきて打ち込んで WA を食らってから、入出力例を読んでナップサックじゃないことに気づく orz. その後は、思いつきで TLE だらけになるコードを書き上げて時間切れになったけど、TLE にならなかったら WA になるような気もする.

考え方としては

M - 1 日は、A_i = 1 の中で、B_i が最大の日雇いアルバイトをやる.
M - 2 日は、M -1 日のときの残りと、A_i = 2 の中で、B_i が最大の日雇いアルバイトをやる.
...

でいいはずなので、その通りにコードを組んでみたが、TLE だらけ. 毎回候補となる日雇いアルバイト全部を嘗めて最大の B_i を探索しているのがまずいんだろうなあと思って、B の値の最大をキャッシュするようにしたら PyPy3 で通った. (Python3 は TLE 2個)

n, m = map(int, input().split())
d1 = {}
for _ in range(n):
  a, b = map(int, input().split())
  if a in d1:
    d1[a].append(b)
  else:
    d1[a] = [b]
result = 0
d2 = {}
maxb = -1
for i in range(1, m + 1):
  if i in d1:
    for j in d1[i]:
      if j not in d2:
        d2[j] = 0
      d2[j] += 1
      if j > maxb:
        maxb = j
  else:
    if len(d2) == 0:
      continue
  result += maxb
  if d2[maxb] == 1:
    del d2[maxb]
    if len(d2) == 0:
      maxb = 0
    else:
      maxb = max(d2.keys())
  else:
    d2[maxb] -= 1
print(result)

過去、main 関数を作ってコードをその中に入れ呼ぶようにすると、変数がローカル変数になるため、1割～2割程度高速化していたのだが、今回は不思議なことに遅くなってしまった. 要研究. あと、Python3 では AC なのに、PyPy3 では WA になるのを初めてみた. PyPy3 の秘孔をついてしまったか.

追記: カツカツに最適化しても Python3 の TLE は一つも消えず困ったなあと思っていたが、解説で使うことになっている順序付きキューが最小のしか Python のビルトインにはなく、使えなくどうしようって感じだったけど、マイナスで突っ込んで、取り出したらマイナスして戻すという使い方をするということを知って、実装したらサクッと通った.

from heapq import heappush, heappop
n, m = map(int, input().split())
jobs = {}
for _ in range(n):
  a, b = map(int, input().split())
  if a > m:
    continue
  if a in jobs:
    jobs[a].append(b)
  else:
    jobs[a] = [b]
result = 0
candidates = []
for a in range(1, m + 1):
  if a in jobs:
    for b in jobs[a]:
      heappush(candidates, -b)
  else:
    if len(candidates) == 0:
      continue
  result += -heappop(candidates)
print(result)