AtCoder Beginners Contest 305 (ABC305) をPythonで解きました。
見やすいコードを書く練習も兼ねてます。
A - Water Station
問題ページ
考察
$0, 5, 10, ..., 100$ の$21$ 通りすべてで距離を求めます。
この$21$コの数は、次のようにして書きます。
for i in range(0, 101, 5):
range()の第3引数に増分を書いています。
また、距離など絶対値を求めるときは、abs(num) と書くとマイナスを取っ払ってくれて便利です。
コード
N = int(input())
ans = -1
min_dist = 300
for i in range(0, 101, 5):
dist = abs(N - i) # 絶対値
if dist < min_dist:
min_dist = dist
ans = i
print(ans)
B -ABCDEFG
問題ページ
考察
もしも問題文中のアルファベットA～Gが1～7だったら、次のコードだけで解けます。
A = [3, 1, 4, 1, 5, 9]
x, y = map(int,input().split())
ans = sum(A[x-1:y]) # x < y ってことにしてます。
print(ans)
なので、文字を数字に変える作業が必要です。
いろいろとやり方はあって、知ってるやり方を3つまとめてみました。
解答例はord関数をつかったコードにしました。
文字を数字に変える方法
以下では、$p, q$ は入力として受け取ってあるものとします。1つめに、ord関数をつかう方法があります。
"""ord関数
Pythonでは、ord('A')=65, ord('B')=66,...,ord('Z')=90になります。
"""
x = ord(p) - ord('A')
y = ord(q) - ord('A')
2つめに、indexメソッドをつかう方法があります。
ALP = "ABCDEFG"
x = ALP.index(p)
y = ALP.index(q)
今回はA～Gなので手打ちでABCDEFGと打てますが、A～Zだとしんどいです。
そんなときにつかえるのが、次の3つめの方法です。
import string
ALP = string.ascii_uppercase # ABCDEFGH...XYZ
x = ALP.index(p)
y = ALP.index(q)
コード
A = [3, 1, 4, 1, 5, 9]
p, q = input().split()
x, y = ord(p) - ord('A'), ord(q) - ord('A')
if x > y:
x, y = y, x
ans = sum(A[x:y])
print(ans)
C - Snuke the Cookie Picker
問題ページ
考察
クッキーのある長方形の領域は、「縦横2マス以上」だと書いてあります(ちなみに、問題文で太字にしてあるところは、めちゃくちゃ重要なことが多いです!!!!)。
どこのクッキーが食べられたのかはすぐに分からないですが、クッキーは1枚しか食べられてないので、縦横どこからどこまでがクッキーの置かれていた領域なのかは分かります(縦横2マス以上って書いてくれてたのがここできいてます!!)。
長方形が縦横どこからどこまでなのかが分かれば、その領域の中で「#」じゃなくなってるところを探せばいいです。
長方形がどこからどこまでなのかを探すのに$O(HW)$、
その長方形の中でクッキーがなくなってるところを探すのに$O(HW)$、
トータルでの計算量は$O(HW)$で十分間に合います。
コード
H, W = map(int, input().split())
S = [input() for _ in range(H)]
# 長方形の縦横がどこからどこまでかを探す。
min_i, max_i = 1000, -1
min_j, max_j = 1000, -1
for i in range(H):
for j in range(W):
if S[i][j] == '#':
min_i = min(min_i, i)
max_i = max(max_i, i)
min_j = min(min_j, j)
max_j = max(max_j, j)
# クッキーのあった長方形の中で、"."になってるところを探す。
for i in range(min_i, max_i + 1):
for j in range(min_j, max_j + 1):
if S[i][j] == '.':
print(i + 1, j + 1)
D -Sleep Log
問題ページ
考察
(下のコードも参考にしながら見てみてね。)
起きた時間と寝た時間が一緒になっていて、サンプル1の補足みたいに色でもついていれば人間でも直感的に分かりそうなんですが、分かりにくいので2つのリストwakeとsleepに分割しちゃいます。分けなくても解けるかもだけど、分けた方が考えがまとまりそうなのでこうしておきます。
$l$分後から$r$分後までの睡眠時間を求めるんですが、これは、(0分後から$r$分後までの睡眠時間) から、 (0分後から$l$分後までの睡眠時間)を引いたものになります。$l～r$のものを0始まりのものにおきかえるのはめちゃくちゃつかう方法です!!
たとえば入力例1の睡眠記録で、$t=1600$までの合計の睡眠時間がいくらか知りたくなったとします。
答えは$(1440-1320)+(720-240)=600$ です。
他にも試してみます。$t=2100$のときも計算してみます。
答えは$(2100-1800)+(1440-1320)+(720-240)=900$です。
今回は睡眠が最大でも3回しか出てきませんでしたが、$N$は$ 2×10^5 $未満なので、睡眠は多いときだと$10^5$回くらい出てきます。
クエリは$2×10^5$回くらい飛んでくるので、こんなのを毎回計算していられません。先ほどの計算を見返してみると、$(1440-1320)+(720-240) $は共通しています。
こういうのはクエリを処理していく前に、先に計算しておきます。
先に睡眠の累積和リストBをつくっておきます。
さっきの計算を見てみると、時刻$t$で起きているのか寝ているのかによって計算方法が少し変わっています。
どっちもいっぺんに考えるのは難しいので、とりあえず時刻$t$に起きているときのことを考えます。
sleepリストのなかで、時刻$t$がどこに入るのかを求めます。これは2分探索で求められます(bisect_left関数がめっちゃ便利です!!)。
この数値は、睡眠記録をとってから時刻$t$までで寝た回数になります。寝た回数が分かれば、睡眠時間の累積和Bから答えが出せます。
時刻$t$で寝ていたときも、sleepリストの中で時刻$t$がどこに入るのかを求めます。
いちばん直近で寝始めてから何分だけたったのかを計算します。残りの睡眠時間については、時刻$t$で起きていた時と同じ処理をします。
時刻$t$に起きているのか寝ているのかは、wakeリストとsleepリストの両方で2分探索をして判断します。
2つのインデックスが同じだったら、起床した回数と就寝した回数が同じなので、寝ていることになります。
起床した回数の方が1だけ多かったら、起きていることになります。
ひとこと
今回みたいにゴチャついた処理をする問題が出たときに、よくやっている手法をパッと書いてみました。
ゴチャついたときの進めかた
入力を受け取ってwakeリストとsleepリストをつくったあと、wakeリストとsleepリストを手元のコンソール画面に表示させておきます。 問題文にはないし、これを見ながら考察を進めることになりそうだからです。print(f'{wake=}') # f-stringで書くと、wake=[0,720,1440,2160]と書いてくれてうれしい！
print(f'{sleep=}')
時刻$t$までで寝た時間の合計を返す関数を作ります。
クエリの中で書いてもいいんですが、ネストが深くなると何をしてたかよく分からなくなってしまいがちです。
def total_sleep(t):
# 省略
実は2分探索はsleepリストだけでよくて、wakeリストではする必要はありません。
起床した回数は、就寝の回数と同じか、それに1だけ足した値にしかならなくて、場合分けで書けます。
場合分けがそんなに苦じゃない人はそれでいいです。それがしんどいよって人は、ちょっと実行時間を増やしてwakeリストでも2分探索しちゃっていいです。全体の計算量は変わらないし、だいたい通ります。
コード
from bisect import bisect_left
N = int(input())
A = list(map(int, input().split()))
wake, sleep = [], []
for i in range(N):
if i % 2 == 1:
sleep.append(A[i])
else:
wake.append(A[i])
B = [0]
for i in range(len(sleep)):
B.append(wake[i + 1] - sleep[i] + B[-1])
# 睡眠記録をとってからt分後までで寝た時間の合計
def total_sleep(t):
if t < sleep[0]:
return 0
w_idx = bisect_left(wake, t)
s_idx = bisect_left(sleep, t)
# 時刻tが起きている時間のとき
if s_idx + 1 == w_idx:
return B[s_idx]
# 時刻tが睡眠中のとき
if s_idx == w_idx:
return t - sleep[s_idx - 1] + B[s_idx - 1]
Q = int(input())
for _ in range(Q):
l, r = map(int, input().split())
ans = total_sleep(r) - total_sleep(l)
print(ans)
E - Art Gallery on Graph
問題ページ
考察
入力例1を紙に書いてみます。
頂点5にいる体力2の警備員に注目します。
この警備員は頂点1,3に行けて、体力1になります。
さらに頂点2にも行けて、体力0になります。体力0になったのでもう移動できません。
これを全部の警備員についてやりたいところなんですが、これだとTLEしてしまうのがこの問題の難しいところです。
体力が最も多い警備員を選んで、隣接している未到達の頂点に(今の体力-1)の体力の警備員を配置する。
↑実はこの手法で解けます。
これはダイクストラ法を知っていると出てくる考え方で、これを知らないで解くのはけっこう厳しいような気はします。
コード
from heapq import heappop, heappush
N, M, K = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
a, b = [int(t) - 1 for t in input().split()]
G[a].append(b)
G[b].append(a)
que = [] # 優先度付きキュー, (-体力,pos)を格納する
for _ in range(K):
p, h = map(int, input().split())
heappush(que, (-h, p - 1))
seen = set()
while que:
mh, pos = heappop(que)
h = -mh
if pos in seen:
continue
seen.add(pos)
if h == 0:
continue
for nv in G[pos]:
if nv in seen:
continue
heappush(que, (mh + 1, nv))
ans_list = list(seen)
ans_list.sort()
print(len(ans_list))
print(*[a + 1 for a in ans_list])
F - Dungeon Explore
問題ページ
考察
深さ優先探索で解きます。
頂点xとyを結ぶ辺を(x, y)とすると、例えばグラフが(1, N), (1, 2), (2, 3), (3, 4),...みたいな構造だったら$2N$回の移動でいけるし、
頂点2より下側が別にパスグラフじゃなくてもちょっと枝を追加してみたりしても$2N$回でできるのが実験してみると分かります。(分からなかったら、いったん手元の紙で実験の法則です！)
もときた道を記録しながら、行ったことのない頂点を訪れ続けます。
行ったことある頂点しかなかったら、もときた道を戻ります。
下のコードは再帰関数じゃないけど、慣れてる書き方で実装して大丈夫です。
コード
N, M = map(int, input().split())
C = [0] * N # つながってる頂点の数
P = [[] for _ in range(N)] # 見た頂点のリスト
par_list = [-1] * N # もときた道
now_v = 1 # 1-indexed
while True:
k, *v = map(int, input().split())
C[now_v - 1] = k
printed=False
for nv in v:
# 完全に探索済みで訪問しなくていい頂点
if C[nv - 1] > 0 and C[nv - 1] == len(P[nv - 1]):
continue
if C[nv - 1] == 0:
P[nv - 1].append(now_v)
P[now_v - 1].append(nv)
par_list[nv - 1] = now_v
now_v = nv
print(nv)
printed=True
if nv == N: # OKが返ってくるとき、プログラムを終了
_ = input()
exit()
break
if printed:
continue
now_v = par_list[now_v - 1]
print(now_v)