AtCoder Beginners Contest 325 (ABC325) をPythonで解きました。
見やすいコードを書く練習も兼ねてます。
A - Takahashi san
問題
Takahashi Chokudai さんには、Takahashi san と呼んであげてね。
考察
名字 $S$ に (スペース)とsanをくっつけた文字列を出力します。
print(S, "san") としてもいいですし、 print(S + " san") としてもいいです。
コード
S, T = input().split()
print(S + " san")
B - World Meeting
問題
世界中いろんなところに会社があるから、なるべくたくさんの人が会議に参加できる時間を求めてね。
考察
問題では会議に参加する人数を聞かれていますが、いったん次の問題が出されたときを考えてみます。
世界標準時で 0:00 に会議が始まるとき、会議に参加する人数を出力してください。
この問題は、次のコードで解けます。
N = int(input())
wx = [list(map(int, input().split())) for _ in range(N)]
cnt = 0 # 会議に参加する人数
for w, x in wx:
time = (x + t) % 24
if 9 <= time <= 17:
cnt += w
print(cnt)
これを0:00だけではなく、1:00, 2:00, ..., 23:00 でも計算していきます。その中で最も多かった参加人数を出力すればいいです。
先ほどのコードを関数にしてしまってmax()関数で最大値を取ると、コードが簡潔になっていいかなと思います。
コード
# 世界標準時 t:00 に会議を開始するときの、会議の参加人数
def f(t):
cnt = 0 # 会議に参加する人数
for w, x in wx:
time = (x + t) % 24
if 9 <= time <= 17:
cnt += w
return cnt
N = int(input())
wx = [list(map(int, input().split())) for _ in range(N)]
ans = max(f(t) for t in range(24))
print(ans)
C - Sensors
問題
上下左右斜めに隣接してるセンサを全部くっつけて1つのセンサにしちゃいます、全体でいくつのセンサがあることになりますか？
考察
いろいろな解き方があります。(別解もいくつか書いてあります)
幅優先探索BFSを利用して解いてみます。
左上から右下へ、順番にマスを見ていきます(下の表のような順番です)。
| 0 | 1 | 2 | 3 |
| 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 |
| 12 | 13 | 14 | 15 |
そして、センサのあるマス (# のマス) だったとき、そのマスを起点にして、「上下左右斜めの $8$ 方向に行ける」「 # のマスにだけ行ける」の $2$ つの条件で幅優先探索BFSをします。
これで、連動しているセンサをすべて探し出せます。
ただし、すでにBFSで探索済みのセンサを起点としてBFSをしてはいけません(下の図の青色の丸のマスからBFSはしません)。
すでに赤丸のマスからBFSをして、連動しているセンサとして数えられているからです。
この問題は、探索済みのマスをsetに格納して判定したり、2次元リストseenを用意してseen[i][j]=Trueのときは探索済みだとして判定したりすればokです。
コード
from collections import deque
def bfs(si, sj):
que = deque()
que.append((si, sj))
while que:
oi, oj = que.popleft()
for ni, nj in neighbor8(oi, oj):
if not seen[ni][nj] and S[ni][nj] == '#':
seen[ni][nj] = True
que.append((ni, nj))
# 隣接する8頂点のリスト
def neighbor8(i, j):
lst = []
for di in [-1, 0, 1]:
for dj in [-1, 0, 1]:
if di == dj == 0: continue
if 0 <= i + di < H and 0 <= j + dj < W:
lst.append((i + di, j + dj))
return lst
H, W = map(int, input().split())
S = [input() for _ in range(H)]
seen = [[False] * W for _ in range(H)] # 探索済みのマスならTrue
ans = 0
for i in range(H):
for j in range(W):
if not seen[i][j] and S[i][j] == '#':
bfs(i, j)
ans += 1
print(ans)
別解
UnionFindをつかった解法
頂点やマスを連結させるとき、UnionFindをつかえることが多いです。この問題でもUnionFindをつかって解いてみます。
2次元だとUnionFindが使えないです。なので、こんな感じで各マスに番号を振って、1次元チックにしてみます。
| 0 | 1 | 2 | 3 |
| 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 |
| 12 | 13 | 14 | 15 |
そして、センサのあるマスについて、周囲 $8$ マスの中でセンサがあるところと結合します。
(イメージ図)
気分的には、len(uf.groups())でかたまりの個数を数えたいんですが、ドット(.)のマスがたくさんあるせいでそれができません。
なので、勝手にドット専用の頂点を1つつくって、その頂点とすべてのドットの頂点をくっつけます。
これで、uf.groups() の中身は、ドットのグループが $1$ つと、センサのグループがいくつかあるような状態になりました。
ドットのグループはカウントしないので、答えは len(uf.groups()) - 1 になります。
"""UnionFindをつかった解答例コード"""
from atcoder.dsu import DSU
def pos(i, j):
return i * W + j
# 隣接する8頂点のリスト
def neighbor8(i, j):
lst = []
for di in [-1, 0, 1]:
for dj in [-1, 0, 1]:
if di == dj == 0: continue
if 0 <= i + di < H and 0 <= j + dj < W:
lst.append((i + di, j + dj))
return lst
H, W = map(int, input().split())
S = [input() for _ in range(H)]
uf = DSU(H * W + 1)
dot = H * W # ドット専用の頂点
for i in range(H):
for j in range(W):
if S[i][j] == '.':
uf.merge(pos(i, j), dot)
continue
# S[i][j]='#' のとき
for i2, j2 in neighbor8(i, j):
if S[i2][j2] == '#':
uf.merge(pos(i, j), pos(i2, j2))
ans = len(uf.groups()) - 1
print(ans)
深さ優先探索DFSをつかった解法
先に書いておきますが、Pythonは再帰がめちゃくちゃに遅いです。
幅優先探索BFSやUnionFindなど、他にも解き方があるのが分かっていたら、なるべく深さ優先探索DFSはつかわないようにした方がいいです。
ほぼBFSのときと同じ解き方です。
左上から右下へと順にマスを見ていって、未探索のセンサのあるマスにぶつかったとき、そのマスを起点にしてDFSをします。
DFSをするときは、コードの最初にこれをつけるようにしましょう。
"""再帰関数のときのセット"""
import sys
import pypyjit
sys.setrecursionlimit(10 ** 7)
pypyjit.set_param('max_unroll_recursion=-1')
また、再帰の回数が多くてしんどいだけのときは、pypyjit の部分を消して、CPythonで提出したほうがはやいケースも多いです。そのあたりはコードの中身と都度相談しながらどれで提出するか決めましょう。
import sys
import pypyjit
sys.setrecursionlimit(10 ** 7)
pypyjit.set_param('max_unroll_recursion=-1')
def dfs(si, sj):
for vi, vj in vec:
ni, nj = si + vi, sj + vj
if not (0 <= ni < H and 0 <= nj < W):
continue
if not seen[ni][nj] and S[ni][nj] == '#':
seen[ni][nj] = True
dfs(ni, nj)
vec = []
for di in [-1, 0, 1]:
for dj in [-1, 0, 1]:
if not di == dj == 0:
vec.append((di, dj))
H, W = map(int, input().split())
S = [input() for _ in range(H)]
seen = [[False] * W for _ in range(H)] # 探索済みのマスならTrue
ans = 0
for i in range(H):
for j in range(W):
if not seen[i][j] and S[i][j] == '#':
seen[i][j] = True
dfs(i, j)
ans += 1
print(ans)
D - Printing Machine
問題
いろんなタイミング・速さで印字機に商品が流れ込んでくるから、なるべくたくさんの商品に印字してね。
考察
天下り的ですが、印字機の中にある商品のうち、印字機から出る時刻が最もはやいものから印字していくのが最適です。「区間スケジューリング問題」とよばれていて、よく出る典型的な考え方です。
- 印字機から出る時刻が最もはやいものを取り出したい。
- 印字機の中にある商品は刻一刻と変化する
この $2$ つの状態で活躍するのが、優先度付きキュー(ヒープキュー)です。
時刻 $1$ 、時刻 $2$ 、 $\cdots$ と順番に見ていきたいですが、制約を見ると印字機に入る時刻と入っている時間は $10^{18}$ が最大値らしいので、順番には見ていけません。
それに比べて、商品の数は最大でも $2 \times 10^5$ とそこまで大きくないです。新たに商品が印字機に入るわけでもなく、商品に印字するわけでもないような時間が大量にあることになるので、その時間は効率よくスキップしたいです。
印字する商品がないときは、次に商品が入ってくる時間までスキップすることにします。
優先度付きキューは、要素の挿入や取り出しが $1$ 回あたり $O(logN)$ なので、全体として $O(NlogN)$ で解けます。
コード
from collections import defaultdict
from heapq import heappop, heappush
'''
tatyamさん作の、SortedSetです。
使わせていただき、ありがとうございます！
https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.py
・使い方(個人的まとめ)
s=SortedSet()
s.a: SortedSetの中身を返す。
len(s), x in s, x not in s: リストと同じ要領で使える。
s.add(x): xを追加してTrueを返す。ただしxがすでにs内にある場合、xは追加せずにFalseを返す。
s.discard(x): xを削除してTrueを返す。ただしxがs内にない場合、何もせずにFalseを返す。
s.lt(x): xより小さい最大の要素を返す。もし存在しないなら、Noneを返す。
s.le(x): x 以下の 最大の要素を返す。もし存在しないなら、Noneを返す。
s.gt(x): xより大きい最小の要素を返す。もし存在しないなら、Noneを返す。
s.ge(x): x 以上の 最小の要素を返す。もし存在しないなら、Noneを返す。
s.index(x): xより小さい要素の数を返す。
s.index_right(x): x以下の要素の数を返す。
・使い方URL
https://github.com/tatyam-prime/SortedSet
'''
# (ながいので、SortedSet省略。上のURLからコピペしてね。)
N = int(input())
td = [list(map(int, input().split())) for _ in range(N)]
P = [(t, t + d) for t, d in td] # (入る時刻, 出る時刻)のタプル
ss = SortedSet()
dic = defaultdict(list)
for t, e in P:
dic[t].append(e)
ss.add(t)
que = []
t = 0
ans = 0
while True:
if t in dic:
for el in dic[t]:
heappush(que, el)
popped = False # 時刻tで商品に印字したらTrue, 印字する商品がなかったらFalse
while que:
e = heappop(que)
if t <= e:
popped = True
ans += 1
t += 1
break
if not popped:
t = ss.ge(t)
if t is None:
break
print(ans)
E - Our clients, please wait a moment
問題
工夫して、都市 $1$ から都市 $N$ まで移動してね。電車にのったら社用車には乗れないから気をつけてね。
考察
問題文より、社用車と電車を交互にいつでも行き来できるわけではなく、電車→社用車 はできないです。
つまり同じ都市であっても、社用車に乗っている状態と、電車に乗っている状態で、扱いを変えないといけません。
こういう、同じ頂点なのに性質が違うものがあるとき、頂点 $A$ と頂点 $A´$ みたいに $2$ つの頂点に分けて別々の頂点として扱うと解きやすくなることがあります。「頂点倍加」とよばれたりします。
(イメージ図)
(本当はもっと矢印があるんですが、ごちゃついちゃうので省略しました)
このグラフで、都市 $1$ から都市 $N$ までの最短経路を求めたいです。
これはダイクストラ法で求められます。
ダイクストラ法の具体的な説明は、長くなるので省略します。(インターネット上にいい記事がたくさんあります！)
下のコードでは、社用車に乗っている状態の都市を頂点 $0$ ～ $N-1$に、電車に乗っている状態の都市を頂点 $N$ ～ $2N-1$ にしています。
コード
from heapq import heappop, heappush
N, A, B, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(N)]
que = []
dist = [1 << 60] * (N * 2)
heappush(que, (0, 0)) # (time, city) のタプルを入れる
dist[0] = 0
while que:
time, city = heappop(que)
if dist[city] < time:
continue
# 社用車で移動する
if city < N:
for next_city in range(N):
next_time = dist[city] + D[city][next_city] * A
if next_time < dist[next_city]:
dist[next_city] = next_time
heappush(que, (next_time, next_city))
# 電車で移動する
for next_city in range(N, N * 2):
next_time = dist[city] + (D[city % N][next_city % N] * B + C)
if next_time < dist[next_city]:
dist[next_city] = next_time
heappush(que, (next_time, next_city))
print(min(dist[N - 1], dist[N * 2 - 1]))
F - Sensor Optimization Dilemma
問題
いろんな長さの区間があって、$2$ つあるセンサをうまく配置して全部の区間を監視してね。
センサをつくるのにお金がかかるから、お金をあまり払わなくていいようにうまく配置してね。
考察
「センサ $1$ をつかった数」と「センサ $2$ をつかった数」の $2$ つの数を管理しながらDPしたくなりますが、センサの数の最大値はどちらも $10^3$ なので、状態だけで $10^6$ 個、$1$ つの状態からの遷移もだいたい $10^6$ 個あって、区間の数は $100$ 個あって。どう考えてもTLEします。
なので、どうにか工夫したいです。
たとえば、$(センサ1をつかった数, センサ2をつかった数)=(2,3)$ の状態がありえたとして、$(2,5)$ や $(2,8)$ の状態は考える必要がありません。
つまり、センサ $1$ をつかった数に対して、センサ $2$ をつかった数はたくさん見なくてよさそうです。
$$dp[u1] = センサ1の使用量がu1のときの、センサ2の使用量の最小値$$
となるリストを用意して、動的計画法でとけばokです。
コード
N = int(input())
dist = list(map(int, input().split()))
l1, c1, k1 = list(map(int, input().split()))
l2, c2, k2 = list(map(int, input().split()))
dp = [1 << 30] * (k1 + 1)
dp[0] = 0
for d in dist:
# dp: 前回までの分 ep: 前回までの分+今回の区間でつかうセンサの数
ep = [1 << 30] * (k1 + 1)
# 前回までのセンサの使用量 (u1, u2)
for u1 in range(k1 + 1):
u2 = dp[u1]
# このターンで使うセンサの使用量 (n1, n2)
for n1 in range(k1 - u1 + 1):
length = d - n1 * l1
n2 = (length + l2 - 1) // l2 if length > 0 else 0
tot1, tot2 = u1 + n1, u2 + n2 # このターンまでの合計のセンサの使用量
if tot1 <= k1 and tot2 <= k2:
ep[tot1] = min(ep[tot1], tot2)
dp = ep
if min(dp) == 1 << 30:
print(-1)
exit()
ans = min(u1 * c1 + u2 * c2 for u1, u2 in enumerate(dp))
print(ans)