【ABC342】緑コーダーの競プロ参加記録 #5
ふわふわした解説を目指しています。
今回はAtCoder Beginner Contest ABC342。使用言語はPythonです。
A問題 - Yay!
コンテスト中の提出
https://atcoder.jp/contests/abc342/submissions/50560529
文字列$${S}$$が与えれられる。
$${S}$$は1文字を除いて全て同じ文字からなる。
他の文字と異なる1文字は何文字目か出力してね。
いい感じの解法が思いつかなかったので、「これが分かればよい」を順番に求める解き方をします。流れとしては次のようになります。
文字の種類ごとに個数をカウントする。
1文字のみの文字の位置を特定する。
まず入力を受け取ります。入力は文字列$${S}$$の1つなのでinput関数から受け取るだけでよいです。
""" 入力を受け取る """
S = input()文字の種類ごとに個数をカウント
文字(str)と個数(int)を対応させるため辞書型 (dict) を使います。forループで１つずつ文字列$${S}$$に含まれる文字をカウントしていきます。
dictはキーが割り当てられていない値に対して演算を行おうとするとエラーになるのでキーの存在をチェックします。
""" 入力を受け取る """
S = input()
""" 文字の個数をカウント (dict) """
Cnt = {}
for s in S:
if not s in Cnt:
Cnt[s] = 1
else:
Cnt[s] += 1ところで、dictにキーが割り当てられているかを判定しつつカウントするのは面倒です。標準ライブラリのcollectionsモジュールからdefaultdictを使うと、デフォルト値をもったdictを扱うことができます。
次のコードではintのデフォルト値、すなわち 0 を指定しています。
from collections import defaultdict
""" 入力を受け取る """
S = input()
""" 文字の個数をカウント (defaultdict) """
Cnt = defaultdict(int)
for s in S:
Cnt[s] += 1この一連の処理を1行で済ませられるのがcollections.Counterです。
from collections import Counter
""" 入力を受け取る """
S = input()
""" 文字の個数をカウント (Counter) """
Cnt = Counter(S)1文字のみの文字の位置を特定
文字列$${S}$$の各文字をキーとしたdictの値が 1 であるとき、それが何番目かを答えとして出力します。0-indexを1-indexに直して答えることに注意しましょう。
from collections import Counter
""" 入力を受け取る """
S = input()
""" 文字の個数をカウント (Counter) """
Cnt = Counter(S)
""" 1文字のみの文字の位置を特定 """
N = len(S)
ans = 0
for i in range(N):
if Cnt[S[i]] == 1:
ans = i + 1
break
""" 答えを出力 """
print(ans)enumerateを使うとforループ周辺のコードが少しスッキリします。
""" 1文字のみの文字の位置を特定 """
ans = 0
for i, s in enumerate(S):
if Cnt[s] == 1:
ans = i + 1
break難しかったです。
B問題 - Which is ahead?
コンテスト中の提出
https://atcoder.jp/contests/abc342/submissions/50564618
$${N}$$人が一列に並んでいる。
前から$${i}$$番目は人$${P_i}$$。
$${Q}$$個のクエリが与えられる。
人$${A_i}$$と人$${B_i}$$で前の方に並んでいる人を出力してね。
「$${Q}$$個のクエリが与えられる。」
この形式を見たときはまず制約を確認して、問題文の通りに処理を行ったとき計算量がどうなるか考えます。
$${N \leq 100, Q \leq 100}$$なのでクエリごとに全ての人をチェックしても$${O(NQ)}$$で 2 sec に余裕で間に合います。
クエリとして人$${A_i}$$と人$${B_i}$$を与えられるたびに数列$${P}$$を前から全探索して、先に現れた人の番号を出力すればよいです。
""" 入力受け取り """
N = int(input())
P = list(map(int, input().split()))
Q = int(input())
""" クエリ処理 """
for _ in range(Q):
a, b = map(int, input().split())
for p in P:
if p in {a, b}:
print(p)
break$${N , Q \leq 100}$$であればこの方法で解けますが、C問題で同様の問題が出るとすれば$${N, Q \leq 2\times10^5}$$になるはずです。$${O(NQ)}$$だとTLEになります。
ここで、数列$${P}$$のもつ「前から$${i}$$番目$${\rArr}$$人$${P_i}$$」という情報を反転した「人$${p}$$$${\rArr}$$前から$${A_p}$$番目」を表す数列$${A}$$をあらかじめ作っておくと、各クエリの処理が$${O(1)}$$で済みます。
""" 入力受け取り """
N = int(input())
P = list(map(int, input().split()))
Q = int(input())
""" A[k]: 人 k の位置 """
A = [0] * (N + 1)
for i, p in enumerate(P):
A[p] = i
""" クエリ処理 """
for _ in range(Q):
a, b = map(int, input().split())
if A[a] < A[b]:
print(a)
else:
print(b)上のコードのように前計算をすることで$${O(NQ) \rarr O(N + Q)}$$となり計算量を改善できました。
B問題では計算量を落とさなくても解ける問題も多く出題されます。自分にとって時間がかからなさそうな実装方法を選べるとよいですね。
C問題 - Many Replacement
コンテスト中の提出
https://atcoder.jp/contests/abc342/submissions/50570235
長さ$${N}$$の文字列$${S}$$が与えられる。
$${Q}$$個のクエリが与えられる。
クエリ: $${S}$$に含まれる文字$${c_i}$$を$${d_i}$$に変える。
最終的な$${S}$$を出力してね。
「$${Q}$$個のクエリが与えられる。」
計算量を確認しましょう。素直に従うと$${O(NQ)}$$でTLEになりそうです。
ここで、求められているのは最終的な$${S}$$なので途中の$${S}$$のことは無視して良さそうです。
「文字列$${S}$$の$${i}$$文字目が最終的にどの文字になるか」の情報が必要に思えますが、同じ文字はすべて同じ変化をしますので「文字列$${S}$$に含まれる各文字が最終的にどの文字になるか」さえ分かればよいです。
そうなると文字列$${S}$$にこだわる必要もなく、クエリによる各アルファベットの変化を追うだけで済みます。
アルファベットの文字数は26文字なのでクエリごとに全てのアルファベットをチェックしても 2 sec に間に合います。
from string import ascii_lowercase
""" 入力受け取り """
N = int(input())
S = input()
Q = int(input())
""" 文字管理用のdict初期化 """
D = {}
for a in ascii_lowercase:
D[a] = a
""" クエリ処理 """
for _ in range(Q):
c, d = input().split()
for a in ascii_lowercase:
if D[a] == c:
D[a] = d
ans = ''.join([D[s] for s in S])
print(ans)D問題 - Square Pair
コンテスト中の提出
https://atcoder.jp/contests/abc342/submissions/50589814
長さ$${N}$$の非負整数列$${A}$$が与えられる。
$${A_i \times A_j}$$が平方数になる$${(i, j)}$$の組み合わせの個数を出力してね。
この手の問題ではある数をそのままの形で考えるのではなく、約数にバラして考えると見通しがよくなります。特に素因数分解をすると数の表現が一意に定まります。
たとえば$${48}$$は$${48 = 4 \times 12}$$とも$${48 = 6 \times 8}$$とも書けますが素因数分解すると$${48 = 2^4 \times 3^1}$$の1パターンです。
$${A_i \times A_j}$$について素因数分解を考えたとき、出てくる素因数$${p}$$について全てが$${p^{2k}}$$の形になっていてほしいです。
$${A_i, A_j}$$に含まれる素因数$${p}$$について、$${A_i}$$では$${p^a}$$、$${A_j}$$では$${p^b}$$という形で存在していた場合、$${A_i \times A_j}$$では$${p^{(a+b)}}$$の形で現れます。
$${a+b}$$が偶数になるためには$${a}$$の偶奇と$${b}$$の偶奇が一致している必要があります。
「$${a}$$の偶奇」について考えるとき「$${a}$$を2で割った余りの偶奇」を考えるのと同様に、$${A_i}$$に含まれる素因数$${p}$$について$${p^{2s+t} \rarr p^t (t = 0,1)}$$となるように$${A_i}$$を置き換えても問題ありません。
よって最初から余分な数を除算してやります。$${A_i}$$をある素因数$${p}$$について$${p^2}$$で割れるだけ割っておきます。
ある数$${K}$$の素因数分解は$${O(\sqrt{K})}$$で実現できます。
from math import isqrt
N = int(input())
A = list(map(int, input().split()))
""" 素因数分解 """
for i in range(N):
for p in range(2, isqrt(A[i]) + 1):
while A[i] % (p * p) == 0:
A[i] //= p * pそうすると、例えば$${84 = 2^2 \times 3 \times 7}$$と$${189 = 3^3 \times7 }$$はともに$${21 = 3 \times 7}$$になります。同じ数でグループ分けをすると、各グループは同じパターンの素因数の積で表現できる数の集まりと呼ぶことができ、2つの数の積が平方数になるためには同じグループ内から2つの数を選ぶ必要があります。
$${n}$$個の要素の中から2つを選ぶ組み合わせ数は$${_nC_2 = \frac{n(n-1)}{2}}$$です。各グループの要素の個数をnとすればよいです。
""" 数え上げ """
from collections import Counter
D = Counter(A)
ans = 0
for k, v in D.items():
ans += v * (v - 1) // 2
これで問題を解けました。
と、言いたいのですが厄介なことに$${A_i = 0}$$が認められています。ある数と0の積は0で平方数です。つまり0はすべての数と平方数を作れるヤツなんですね。これを過不足なくカウントしなければなりません。
0のグループを計算した場合
数え方はいろいろありますが、上でグループごとの組み合わせを計算したときに0のグループも計算した場合は「$${A_i, A_j}$$の両方が 0 」の場合をすでにカウント済みなので、「$${A_i, A_j}$$のどっちか片方のみ 0 」の場合の組み合わせを追加で考える必要があります。
$${A}$$に含まれる 0 の個数を$${Z}$$とすると、 0 でない数は$${N - Z}$$個あります。$${Z}$$個のグループから1つ、$${N-Z}$$個のグループから1つ要素を取り出すので、その取り出し方は$${Z(N - Z)}$$個です。これを答えに加算します。
""" 数え上げ """
D = Counter(A)
ans = 0
for k, v in D.items():
ans += v * (v - 1) // 2
ans += D[0] * (N - D[0])
print(ans)0のグループを計算していない場合
グループごとの組み合わせを計算したときに0のグループを計算しなかった場合は「$${A_i, A_j}$$の少なくともどっちか片方が 0 」の場合の組み合わせを追加で考える必要があります。
これは余事象を考えればよく「2つの数の選び方全て」から「2つとも 0 でない選び方」を引いたものを答えに加算すればよいです。
つまり$${_NC_2 - _{N-Z}C_2}$$を加算します。
""" 数え上げ """
D = Counter(A)
ans = 0
for k, v in D.items():
if k != 0:
ans += v * (v - 1) // 2
ans += (N * (N - 1) // 2) - ((N - D[0]) * (N - D[0] - 1) // 2)
print(ans)他にも、「0 と他の任意の数の選び方」から重複分の「2つとも 0 である選び方」を引く考え方もよいです。
つまり$${Z(N - 1) - _ZC_2}$$を答えに加算します。
""" 数え上げ """
D = Counter(A)
ans = 0
for k, v in D.items():
if k != 0:
ans += v * (v - 1) // 2
ans += D[0] * (N - 1) - (D[0] * (D[0] - 1) // 2)
print(ans)
E問題 - Last Train
コンテスト中の提出
https://atcoder.jp/contests/abc342/submissions/50605834
駅が$${N}$$個あり、ダイヤの情報が$${M}$$個与えられる。
情報1 : 駅$${A_i}$$から駅$${B_i}$$に向かう電車がある
情報2 : 各電車は時刻$${l_i}$$から$${d_i}$$分おきに$${k_i}$$本ある。
情報3 : 駅$${A_i}$$から駅$${B_i}$$まで$${c_i}$$分かかる。
駅$${N}$$に行くための、各駅での終電の出発時刻を出力してね。
何から考えるべき？
変数が多すぎて分かりづらいです。図で整理します。
駅$${A \rarr B}$$と移動するとき、駅$${A}$$をなるべく遅く出発するためには「駅$${B}$$での終電に間に合うか？」を考える必要があります。ここで「終電」とは「駅$${N}$$に到着できる最も出発時刻の遅い電車」のことをいい、必ずしも駅$${B}$$から出発する最後の電車であるとは限りません。
「駅$${B}$$での終電」の発車時刻はまた次の駅での終電について知っていなければ分かりません。これをくり返すと結局は駅$${N}$$（の隣駅）の終電の発車時刻を知る必要があります。
つまり、終点である駅$${N}$$のほうから考えます。駅$${N}$$の終電時刻は$${+\infin}$$です。
最も遅い時刻に乗れる電車はどれ？
駅$${B}$$での終電の出発時刻が$${Q}$$であったとします。
駅$${A \rarr B}$$と移動するとき、移動に$${c}$$分かかるので時刻$${Q - c}$$には駅$${A}$$を出発していなければいけません。
駅$${A}$$では時刻$${l}$$から$${d}$$分おきに1本ずつ、合計$${k}$$本の電車が発車します。よって
$$
l + k'd \leq Q - c (0 \leq k' \leq k - 1)
$$
を満たす$${k'}$$のうち最大の$${k'}$$を選べばよさそうです。この$${k'}$$を$${k_{last}}$$とします。
$$
k_{last} = \lfloor \frac{Q - c - l}{d} \rfloor
$$
です。ただし、$${k_{last} < 0}$$の場合は乗る電車が存在せず、$${k - 1 < k_{last}}$$である場合は$${k}$$本目の電車に乗るしかありません。
乗る電車が分かった後は？
駅$${A \rarr B}$$と移動するときの乗る電車が分かると、駅$${A}$$の最終出発時刻が判明します。これを出発の遅い順に決めていきます。
駅を頂点とみなし、電車を辺、時間をコストと考えると、グラフの問題として捉えられそうです。コストがすべての辺で等しいとは限らず、かつ負のコストがないのでダイクストラ法の出番です。
通常ダイクストラ法では優先度付きキューを用いて実装しますが、今回はコストの重い順に処理を進めていくので、探索候補をキューに追加するときにはコストを負の値に変換します (Pythonの場合) 。
""""""
from heapq import *
inf = 1 << 60
def dijkstra(start):
seen = [False] * (N + 1)
dp = [-inf] * (N + 1)
dp[start] = inf
hq = [(0, start)]
while hq:
_, nxt = heappop(hq)
if seen[nxt]:
continue
seen[nxt] = True
for curr, l, d, k, c in D[nxt]:
if seen[curr]:
continue
k_last = (dp[nxt] - l - c) // d
if k_last < 0:
continue
k_last = min(k - 1, k_last)
if dp[curr] < l + k_last * d:
dp[curr] = l + k_last * d
heappush(hq, (-dp[curr], curr))
return dp
N, M = map(int, input().split())
D = [[] for _ in range(N + 1)]
for _ in range(M):
l, d, k, c, a, b = map(int, input().split())
D[b].append((a, l, d, k, c))
dp = dijkstra(N)
for i in range(1, N):
if dp[i] == -inf:
print('Unreachable')
else:
print(dp[i])【余談】
まったく関係ないですが、knotlampのLast Train好きです。
あとがき
今回のコンテストの結果はABCDE5完、順位は1356位、1430 perfでした。
D問題の早解きができそうで焦った結果4ペナを積み重ねてしまったり、E問題も$${N}$$と$${M}$$を間違えてて2REを出したりもったいなさもありつつ、久々の5完 + 水パフォで嬉しいです。
レートも1000目前になりました。
ではまた～。
この記事が気に入ったらサポートをしてみませんか？