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:])
この記事はここまでとします。