Help us understand the problem. What is going on with this article?

AtCoder Beginner Contest 137 参戦記

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 で各アナグラムの数を素直に数え上げて、nC2 を計算して合計して回答.

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 日は、Ai = 1 の中で、Bi が最大の日雇いアルバイトをやる.
  • M - 2 日は、M -1 日のときの残りと、Ai = 2 の中で、Bi が最大の日雇いアルバイトをやる.
  • ...

でいいはずなので、その通りにコードを組んでみたが、TLE だらけ. 毎回候補となる日雇いアルバイト全部を嘗めて最大の Bi を探索しているのがまずいんだろうなあと思って、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)
c-yan
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした