競プロ初心者の復習用記事です。
ここで書く解は解説や他の人の提出を見ながら書いたものです。自分が実際に提出したものとは限りません。
A - Sheep and Wolves
S匹の羊とW匹の狼、勝つのはどちらか聞かれる問題です。
SがWより多いなら羊は襲われません。
S, W = map(int, input().split())
if S > W:
print('safe')
else:
print('unsafe')
B - Battle
体力Aで攻撃力Bと体力Cで攻撃力Dの二つが殴りあうとどちらが勝つか答える問題です。
高橋くん、青木くんそれぞれ必要な攻撃回数は$C/B$, $A/D$それぞれを切り上げた数になります。数が少ないほうの勝ち。また、数が同数なら先に殴れる高橋君が有利です。
以上の考えで実装しました。切り上げ処理にはmath.ceil()を使用しました。(C+(B-1))//Bみたいな書き方をすればライブラリはいらないと思います。
import math
A, B, C, D = map(int, input().split())
if math.ceil(C/B) <= math.ceil(A/D):
print('Yes')
else:
print('No')
C - gacha
N回入力される文字列$S_i$が何種類あるか数える問題です。
set型オブジェクトに入れて長さを数えました。
N = int(input())
S = [input() for _ in range(N)]
print(len(set(S)))
D - Multiple of 2019
入力される数字Sを任意の区間で切り出した時に、2019で割り切れる数は何個作れるか答える問題です。
これの類題だと考え、以下のようなコードを書きました。(実際には思い間違いがあったり、時短ができなかったりして、コンテスト中にはできませんでした。)
import collections
S = input()
N = len(S)
M = [0]
mod = 0
ten = 1
for s in S[::-1]:
mod += (int(s) * ten) % 2019
mod %= 2019
M.append(mod)
ten *= 10
ten %= 2019
count = collections.Counter(M)
print(sum([c*(c-1)//2 for c in count.values()]))
この処理は、例えば1234567という数字があったら7と67と567と4567と34567と234567と1234567の余剰を計算し、余剰の一致する桁数があったらその区間が割り切れる、というものです。
実際の処理としてはこまめに分割して余剰計算を行うことで計算時間の節約をしています。
数学的に細かい解説は前に書いた記事のE問を見てください。
E - Two Currencies
駅1から全ての駅までの最短経路を求める問題です。ただし、電車を使用するには銀貨が必要になり、各駅ごとに異なる時間をかけて両替する必要があります。
今までABCはE問までしかやってきていませんが、しっかりしたグラフ問題はほぼ初めてです。全然わからず諦めました。
解説やら他の解答やらいろいろ見ました。
まず、$2\leq N\leq 50$, $1\leq A_i\leq 50$という制限があることから、この系全体で所持しうる銀貨の総枚数は$49\times50 = 2450$枚です。(この枚数は実際のN, Aの値次第でもっと減らせますが、便宜上この枚数で説明します)
「駅nで銀貨をcoins枚持っている時の最小時間$T$」を以下の配列に格納します。
T[n][coins]
以下のように作成できます。初期値として十分に大きい値を入れておきましょう。
T = [[10**18 for _ in range(2451)] for _ in range(N)]
それぞれの駅について存在しうる行動パターンは「コストcost枚、時間$t$を使用して隣接している駅$m$に向かう」「時間$t$を使用して同じ駅で金貨を-cost枚に両替する($m=n$に移動して負のcost枚消費したと考える)」しかありません。この行動をタプルとして扱います。
(m, cost, t)
このタプルをそれぞれの駅$n$について配列として保存します。
act[n] = [(行動1), (行動2), (行動3), ....]
入力された値をこれらに格納するまでを以下のコードで行います。
N, M, S = map(int, input().split())
act = [[] for _ in range(N)]
for i in range(M):
U, V, A, B = map(int, input().split())
U -= 1
V -= 1
act[U] += [(V, A, B)]
act[V] += [(U, A, B)]
for i in range(N):
C, D = tuple(map(int, input().split()))
act[i] += [(i, -C, D)]
ここから探索を行うため、探索元となる状態を優先度付きキューに保存していきます。一つの状態をタプルとして扱います。現在の時間$currentT$、現在の駅$n$、所持銀貨の枚数$coins$を以下のように表します。
(currentT, n, coins)
優先度付きキューの初期状態はこうなります。
que = [(0, 0, S)]
このキューからtが小さい順に取り出して探索を行い、二次元配列Tを埋めていきます。最後にT[n]内の最小の値を取り出せば、それが駅nにたどり着くまでの最小時間を表します。
では、通しで書いたコードは以下のようになります。
from heapq import *
N, M, S = map(int, input().split())
T = [[10**18 for _ in range(2451)] for _ in range(N)]
act = [[] for _ in range(N)]
for i in range(M):
U, V, A, B = map(int, input().split())
U -= 1
V -= 1
act[U] += [(V, A, B)]
act[V] += [(U, A, B)]
for i in range(N):
C, D = tuple(map(int, input().split()))
act[i] += [(i, -C, D)]
que = [(0, 0, S)]
while que:
(currentT, n, coins) = heappop(que)
for m, cost, t in act[n]:
# もし「払える金額で」「最小時間T[移動先][所持金]を更新できるとき」に値を更新、キューに状態を追加。
# 両替の結果2450枚を超えるなら2450枚として扱って問題なし。
if coins >= cost and currentT + t < T[m][min(2450, coins - cost)]:
T[m][min(2450, coins - cost)] = currentT + t
heappush(que, (currentT + t, m, min(2450, coins - cost)))
for i in range(1, N):
print(min(T[i]))
ダイクストラ法というアルゴリズムだそうです。E問にしては凶悪に難しい問題に感じましたが、最終的な探索部分のアルゴリズムが極めて簡単に書けてびっくりしました。
この記事はここまでとします。