ABC378参加記録 by Python

リアルタイムに解けた問題

A - Pairing

問題文

４個のボールがあり、$i$個目のボールの色は$A_{i}$です。
同じ色のボールは２つ選び両方捨てるという操作を最大何回行えるか求めてください。

制約

• $A_{1},A_{2},A_{3},A_{4}$はそれぞれ１以上４以下の整数

アルゴリズム

リストの要素が1種類であれば、同じ色のボールを捨てる処理を2回行えるので、2を出力。for文で各要素を確認し、重複する値があれば、countを1増やす。最後にcountの数値を出力。

ソースコード

A = list(map(int, input().split()))

count = 0

if len(set(A)) == 1:
  print(2)
  exit()

for i in range(4):
  if count == 2:
    break
  
  num_count = 0
  for a in A:
    if i+1 == a:
      num_count += 1
  
  if num_count >= 2:
    count += 1
    
print(count)

B - Garbage Collection

問題文

AtCoder市では、$N$種類のゴミを定期的に収集しています。$i(=1,2,...,N)$種類目のゴミは、日付を$q_{i}$で割ったあまりが$r_{i}$の日に収集されます。

$Q$個の質問に答えてください。$j(=1,2,...,Q)$番目の質問では、$d_{j}$日に$t_{j}$種類目のゴミが出ときに、次にそれが収集される日を答えてください。

ただし、$i$種類目のゴミが出た日が、$i$種類目のゴミが回収される日であった場合、そのゴミは同じ日に収集されるとします。

制約

• $1 \leq N \leq 100$
• $0 \leq r_{i} < q_{i} \leq 10^{9}$
• $1 \leq Q \leq 100$
• $1 \leq t_{j} \leq N$
• $1 \leq d_{j} \leq 10^{9}$
• 入力はすべて整数

アルゴリズム

$q$日周期で$r$日目から始まる収集に対し、指定日(day)がちょうど収集日なら当日を、そうでなければ$(day//q)*q+r$で同じ期間内の収集日を計算し、それが過去なら次の周期(+q)を返す。

ソースコード

N = int(input())
QR = []
for _ in range(N):
  q, r = map(int, input().split())
  QR.append((q, r))

Q = int(input())
TD = []
for _ in range(Q):
  t, d = map(int, input().split())
  TD.append((t - 1, d))

answers = []
for garbage_type, day in TD:
  q, r = QR[garbage_type]
  
  if day % q == r:
    answers.append(day)
    continue
  
  current_period = (day // q) * q + r
  
  if current_period <= day:
    current_period += q
  
  answers.append(current_period)
  
for answer in answers:
  print(answer)

C - Repeating

問題文

長さ$N$の正数列$A=(A_{1},A_{2},...,A_{N})$が与えられます。以下では定義される長さ$N$の数列$B=(B_{1},B_{2},...,B_{N})$を求めてください。

• $i = 1,2,...,N$について、$B_{i}$を次のように定義する：
  　- $A_{i}$と等しい要素が$i$の直前に出現した位置を$B_{i}$とする。そのような位置が存在しなければ$B_{i}=-1$とする。
  　 より正確には、正整数$j$であって、$A_{i}=A_{j}$となる$j<i$が存在するならば、そのうち最大の$j$を$B_{i}$とする。そのような$j$が存在しなければ$B_{i}=-1$とする。

制約

• $1 \leq N \leq 2 × 10^{5}$
• $1 \leq A_{i} \leq 10^{9}$
• 入力はすべて整数

アルゴリズム

辞書(key)を使って各数値の最後に出現した位置を記録し、数値が既に辞書にあればその位置を出力して更新、なければ-1を出力して新規登録。

ソースコード

N = int(input())

A = list(map(int, input().split()))

key = {}

for i in range(N):
  if str(A[i]) in key:
    print(key[str(A[i])], end=' ')
    key[str(A[i])] = i + 1
  else:
    print(-1, end=" ")
    key[str(A[i])] = i + 1
    
print()