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

[ABC252](https://atcoder.jp/contests/abc252)に参加しました。復習用記事です。



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

## [A - ASCII code](https://atcoder.jp/contests/abc252/tasks/abc252_a)

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

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

```py
N = int(input())

print(chr(N))
```

## [B - Takahashi's Failure](https://atcoder.jp/contests/abc252/tasks/abc252_b)

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

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

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

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

```python
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](https://atcoder.jp/contests/abc252/tasks/abc252_c)

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

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

```python
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$に対して同様の計算を行い、その最小値を出すことで解答が得られます。

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

```py
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](https://atcoder.jp/contests/abc252/tasks/abc252_d)

数列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$)から引くことで求めることができます。実装したものが以下となります。

```python
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$を全探索して計算を行いましょう。

```python
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 ](https://atcoder.jp/contests/abc252/tasks/abc252_e)

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

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

```py
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:])

```

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