ABC223のA-E問題の解説。
目次
A - Exact Price
B - String Shifting
C - Doukasen
D - Restricted Permutation
A - Exact Price
解説
100円の硬貨しかない状態で、x円がある状態を作れるかという問題。
つまり、xが100で割り切れれば、この問題は正解できる。
しかし、硬貨は1枚以上である点に注意する。
コード
def main():
x = int(input())
if x % 100 == 0 and x != 0: # 1以上であることに注意
print('Yes')
else:
print('No')
if __name__ == '__main__':
main()
B - String Shifting
解説
与えられた文字列Sに対して、文字を一つずらしてできる文字列の中で、辞書順で最小のものと最大のものを求める問題。
辞書順というのは、あ、愛、アイス、アイスクリームといったように、アルファベットa, b, c, ..., zの並びにおいて、できる順番のことである。Pythonを用いた辞書順は、list.sort()、もしくは、sorted(list)を用いることで実装ができる。
問題文では、左シフト、右シフトとあるが、実際は、すべて見る必要があるので、どちらか一方で構わない。例えば、左シフトならば、スライスを用いてS[1:] + S[0]とやることで、前の文字を後ろにつけることができる。これをforを用いて、全通り試し、並び替えしたものの最初と最後の値を出力してあげれば答えとなる。
コード
def main():
s = input()
result = []
for _ in range(len(s)):
result.append(s)
s = s[1:] + s[0] # すべてのsに対して左シフト
result.sort() # 辞書順にソート
print(result[0])
print(result[-1])
if __name__ == '__main__':
main()
C - Doukasen
解説
$N$本の導火線があり、$i$番目の導火線は長さ$A_i$cmで$B_i$cm/秒の速さで燃える。これを一本にした導火線に、左右から火をつけて、2つの火がぶつかる場所を求める問題。
まず2つの火がぶつかる時間についてだが、これは1つにつながった導火線をすべて燃やすときの時間の半分の時間である。左から、右から、どちらも火を付けると、全長の半分の時間しかかからないことは明白である。したがって、これを時間tで管理する。
次に、すべての導火線について、左からみていく。"i本目の導火線の長さが時間tのうちに燃えきる"、または、"時間tで導火線がすべて燃えきらない"のどちらか、長さの短い方を選択し、ループごとに値を合計していく。
また、時間tについては、"i本目の導火線を燃やすのにかかった時間"、または、すべての導火線が燃えきっているのであれば、t-tで0にする。
これで求めた長さの値を出力すればAC。
コード
def main():
n = int(input())
alist = []
blist = []
for i in range(n):
a, b = map(int, input().split())
alist.append(a)
blist.append(b)
t = 0 # 時刻
ans = 0
for i in range(n):
# N本の導火線をすべて通るのにかかる時間
t += alist[i] / blist[i]
t /= 2 # 2つの火がぶつかる時刻
for i in range(n):
# "i本目の導火線の長さ"が燃えきるなら前者
# 残り時間tで導火線がすべて燃えきらないなら後者を選択
ans += min(alist[i], t * blist[i])
# "i本目の導火線を燃やすのにかかった時間"
# もしくは
# すべて燃えきっているのならt-tで0にする
t -= min(alist[i] / blist[i], t)
print(ans)
if __name__ == '__main__':
main()
D - Restricted Permutation
解説
$A_i$->$B_i$の順番で現れる数列に対して、辞書順で最小のものを求めるという問題。
結論から述べると、トポロジカルソートで問題を解くことができる。
トポロジカルソートとは、ある頂点から出た矢印はある頂点には戻ってこないという性質を持つグラフ、有向非巡回グラフにおいて、矢印を$R(u, v)$（u, vはそれぞれの頂点）としたとき、uがvよりも際に現れるように頂点を並び変えることである。
ここでは、入次数と出次数という言葉が用いられる。
入次数とは、ある頂点に入る矢印の数を示しており、出次数とは、ある頂点から出る矢印の数を示している。
Pythonでトポロジカルソートを実装する場合、優先度付きキュー(heap)を用いることでうまく実装ができる。コードの解説は、以下で行っているので、デバッグしながらひとつひとつの動きを確認していただきたい。
また、優先度付きキューについては、こちらの記事で解説しているので、「あまりよくわからないない」「不安だな」と思う方は、参照していただきたい。
コード
def main():
from heapq import heappush, heappop
n, m = map(int, input().split())
indeg = [0] * (n+1) # 入次数
out = [[] for _ in range(n+1)]
for _ in range(m):
a, b = map(int, input().split())
indeg[b] += 1
out[a].append(b)
heap = []
# 入次数が0の数字を探す
for i in range(1, n+1):
# 入次数が0ならば
if indeg[i] == 0:
heappush(heap, i)
ans = []
while heap: # すべての数字を見るまで続行
# 辞書順で最小
# つまり、数字が小さいものから取り出す
now = heappop(heap)
ans.append(now)
# 次の数字はどこへ向かうか
for to in out[now]:
indeg[to] -= 1
# 入次数が0の数字をheapに追加
if indeg[to] == 0:
heappush(heap, to)
if len(ans) == n:
print(*ans)
else:
print(-1)
if __name__ == '__main__':
main()
編集後記
優先度付きキューの解説は以前したものの、トポロジカルソートを知らなかったので、解けなかった悔しい。