0
Help us understand the problem. What are the problem?

posted at

updated at

AtCoder Beginner Contest 252の復習, E問まで(Python)

ABC252に参加しました。復習用記事です。

ここで書く解は解説や他の人の提出を見ながら書いたものです。自分が実際に提出したものとは限りません。

A - ASCII code

英小文字の文字コード(番号)を文字に変換する問題です。

pythonでは変換用の関数が用意されています。

N = int(input())

print(chr(N))

B - Takahashi's Failure

数列Aの最大値となる要素の位置番号が数列Bに含まれているかを調べる問題です。

制約条件が緩いのでどうやってもいいです。

「配列A内で最大となるインデックスの配列」を作り、「配列B」との重複する要素をset型で取り出すのが綺麗でしょうか。

インデックスの値に1を加える必要があることに注意しましょう。(一敗)

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

max_v = max(A)

max_a = [i+1 for i, a in enumerate(A) if a == max_v]

if set(max_a)&set(B):
  print('Yes')
else:
  print('No')

C - Slot Strategy

スロットのN個のリールを任意の順番で止めていき、全てを同じ出目で揃えるための最小時間を答える問題です。ただし1秒ごとに押せるのは1個のボタンだけです。

制約が緩いため、全部のボタンを押し切るまでにかかる時間をシンプルにシミュレートできます。tを1ずつ増やしていき、0~9のどの目を揃えるのが最小か比べました。

N = int(input())
S = [input() for _ in range(N)]

min_t = 10**10

for n in range(10):
  t = 0
  s_index = [s.index(str(n)) for s in S]

  while s_index:
    if t%10 in s_index:
      s_index.remove(t%10)
    t += 1

  min_t = min(min_t, t-1)
print(min_t)

解説を見ると計算式の形で説明されていました。

$$ \min_{k=0,1,..9} (\max_{j=0,1,...9}(10\times(j番目に文字kがあるリールの個数-1)+ j))$$

「同時に複数のボタンを押せない」という制約のため、同じ位置に同じ文字が複数あることがボトルネックになります。そのためある文字$k$を揃えられる時間は$\max_{j=0,1,...9}(10\times(j番目に文字kがあるリールの個数)-1)+ j)$と求めることができます。全ての文字$k$に対して同様の計算を行い、その最小値を出すことで解答が得られます。

この手法で実装を行ってみたのが以下となります。

import collections

N = int(input())
S = [input() for _ in range(N)]

min_t = 10**10

for n in range(10):
  n_index = [s.index(str(n)) for s in S]
  count = collections.Counter(n_index)

  t = max([10*(v-1)+i+1 for i, v in count.items()])

  min_t = min(min_t, t-1)
print(min_t)

D - Distinct Trio

数列Aの中に相異なる値3つの組み合わせが何種類あるかを答える問題です。

例えば、$[1,1,1, 2,2,3,4]$という数列を得たとします。

まず、collections.Counterを用いてそれぞれの要素が何個ずつ入っているのかを数えました。

この場合は$1$が$3$個、$2$が$2$個、$3$が$1$個、$4$が$1$個あります。

ここから「条件を満たす」組み合わせの個数を計算するのは大変なので、「条件を満たさない」組み合わせの数を考えてみましょう。

1を3個選ぶ場合($_3C_3=1$通り)、1を2個とそれ以外の数字を選ぶ場合($_3C_2\times _4C_1=3\times4$通り)、2を2個とそれ以外の数字を求める場合($_2C_2\times _5C_1=1\times5$通り)。要素のカウント数を数列Bとして、計算式で表すと以下のようになります。

$\sum (B_i(B_{i}-1)(B_{i}-2)/6 +B_i(B_{i}-1)(N-B_i)/2)$

これを全体の組み合わせの数($_7C_3$)から引くことで求めることができます。実装したものが以下となります。

import collections
 
N = int(input())
A = list(map(int, input().split()))
 
c = collections.Counter(A)
 
sum_c = N*(N-1)*(N-2)//6
 
dup_c = sum([v*(v-1)*(v-2)//6 + v*(v-1)*(N-v)//2 for i, v in c.items()])
 
print(sum_c - dup_c)

これもまた解説では別の手法を行っていました。

まず、問題文を「$A_i<A_j<A_k$を満たす組の個数を求めよ」と読み替え、大小関係に注目します。ある$A_j$について、$(A_j未満の数字の個数×A_jより大きい数字の個数)$でとりうる組み合わせの種類を求めることができます。ここで$A_jより大きい数字の個数$は$全体の個数-A_{j}以下の個数$で求めることができます。
これを$j$を全探索して計算を行いましょう。

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

UPPER = 2*10**5

count = [0]*(UPPER+1)
for i, a in enumerate(A):
  count[a] += 1

for i in range(UPPER):
  count[i+1] += count[i]
print(sum([count[a-1] * (N-count[a]) for a in A]))

E - Road Reduction

N個の都市を繋ぐ道路を消していき、都市1から都市$i$まで移動するための距離$d_i$を最小化していきます。ダイクストラ法を用いて、都市1からの距離が最短となるルートを順番に確定させていきます。

heapqを用いて[地点vまでの距離, 地点v]を管理し、現在最短となる地点$v$をheappopで取り出します。(ここで取り出した値が最短データと一致しなければやり直し。)その周囲の道路を全て確かめ、暫定の最短距離より短い経路があればそれを更新し、heapqに追加します。
この作業を繰り返し、配列ansにそれぞれの最短を結ぶ最後の道路番号を記録し、出力すればOKです。

from heapq import heappush, heappop

N, M = map(int, input().split())

cities = [[] for _ in range(N)]


for i in range(M):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  cities[a].append([b, c, i+1])
  cities[b].append([a, c, i+1])


D = [10**18]*N
D[0] = 0

ans = [-1]*N

pq = [(0, 0)]

while pq:
  cost, v = heappop(pq)
  if D[v] != cost:
    continue
  for u, d, i in cities[v]:
    new_d = cost + d
    if D[u] > new_d:
      D[u] = new_d
      ans[u] = i
      heappush(pq, (new_d, u))

print(*ans[1:])

この記事はここまでとします。

Register as a new user and use Qiita more conveniently

  1. You can follow users and tags
  2. you can stock useful information
  3. You can make editorial suggestions for articles
What you can do with signing up
0
Help us understand the problem. What are the problem?