AtCoder Beginners Contest 317 (ABC317) をPythonで解きました。
見やすいコードを書く練習も兼ねてます。
A - Potions
問題ページ
考察
左のキズぐすりから順番に見ていって、 $H+(キズぐすりの回復値) \geq X$ になったらそのキズぐすりの番号を出力して処理を打ち切ります。
コーナーケース(=一般的ではない特殊なケース)として、そのようなキズぐすりがなくて何も出力できない場合も考えないといけません。たまたま今回はそういう入力は与えられないと問題文に書いてあるので、コーナーケースも気にしなくてよさそうです。
コード
N, H, X = map(int, input().split())
P = list(map(int, input().split()))
for i in range(N):
if H + P[i] >= X:
print(i + 1)
break
別解
二分探索をつかった解法(ABC-Cレベルです)
キズぐすりの回復値が小さいとダメで、大きくしていくとどこかでokになって、そこから先どれだけ大きくしてもokのままです。 このようなつくりのときは二分探索が使えます。from bisect import bisect_left
N, H, X = map(int, input().split())
P = list(map(int, input().split()))
idx = bisect_left(P, X - H)
ans = idx + 1
print(ans)
B - MissingNo.
問題ページ
考察
入力でもらったリストをソートします。本来は隣り合った2つの数の差は1のはずですが、どこか1か所だけ差が2になっているところがあります。
たとえば、入力でもらったリストが $[3,1,4,5]$ のとき、昇順にソートして $[1,3,4,5]$ として、隣同士の差が2になっているところを探します。この場合は $[1,3]$ の部分があてはまり、その間の数である $2$ が答えです。
コード
N = int(input())
A = list(map(int, input().split()))
A.sort()
for i in range(N - 1):
if A[i] + 1 != A[i + 1]:
print(A[i] + 1)
break
C - Remembering the Days
問題ページ
考察
順列全探索とよばれる方法で解きます。
ここでは「街3 → 街1 → 街2 → 街4」のルートを通ることを $(3,1,2,4)$ と表記することにします。 これは、itertoolsの中にあるpermutationsをつかうと全通り列挙できます。 また、たとえばサンプル1では「街2 → 街4」のルートはないですが、存在しないルートを見に行った時点でこのルートの探索を打ち切ることにします。つまり、「街3 → 街1 → 街2」のルートでの総距離が $(3,1,2,4)$ での総距離だとみなすことにします。
サンプル1だと街の数は $4$ つなので、 $(1,2,3,4)$ の並び替えである $(3,1,2,4)$ や $(2,4,3,1)$ など全部で $4! = 24$ 通りのルートについて距離を計算して、最も距離の長かったものを答えとします。
街の数は最大でも $10$ で、 $(1,2,3,4,5,6,7,8,9,10)$ の並び替えは全部で $10! = 3628800 \lt 4 \times 10^6$ 通りです。どのルートも、見ないといけない街の数は最大で $10$ なので、最悪でも $4 \times 10^7$ 回程度の探索ですみます。街の数が $N$ のとき、この解き方の計算量は $O(2^N \times N)$ です。
itertools.permutations について
1～N の整数の並び替えは、Pythonだと次のように書けます。
from itertools import permutations
N = int(input())
for perm in permutations(range(N)):
print(perm)
たとえば、 $N=3$ を入力すると、次のように出力されます。
(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)
順列全探索の問題はよく見かけるので、itertools.permutationsは覚えておいた方がいい気がします！
コード
from itertools import permutations
N, M = map(int, input().split())
dist = [[-1] * N for _ in range(N)]
for _ in range(M):
a, b, c = map(int, input().split())
a, b = a - 1, b - 1
dist[a][b] = c
dist[b][a] = c
ans = 0
for perm in permutations(range(N)):
cost = 0
for i in range(N - 1):
prev_town = perm[i]
next_town = perm[i + 1]
if dist[prev_town][next_town] == -1:
break
cost += dist[prev_town][next_town]
ans = max(ans, cost)
print(ans)
別解
再帰関数をつかう解法
「今いる頂点の番号」「通ってきた頂点」「総移動距離」の3つを管理しながら、深さ優先探索DFSをすることでも解けます。
詳細は下のコードに譲ります。
import sys
import pypyjit
sys.setrecursionlimit(10 ** 7)
pypyjit.set_param('max_unroll_recursion=-1')
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
a, b, c = map(int, input().split())
a, b = a - 1, b - 1
G[a].append((b, c))
G[b].append((a, c))
ans = 0
# dfs(現在いる頂点, 通った頂点を格納したset, 総移動距離)
def dfs(v, seen, score):
global ans
if ans < score:
ans = score
for nv, d in G[v]:
if nv not in seen:
dfs(nv, seen | {nv}, score + d)
for i in range(N):
dfs(i, {i}, 0)
print(ans)
bitDPをつかう解法(ABC-Eレベル)
$$dp[S][v]: 訪れた頂点集合S, 最後に訪れた頂点vの状態になるための総移動距離の最大値$$
を定義して、この2次元リストを埋めることでもACできます。
from collections import deque
INF = 1 << 60
N, M = map(int, input().split())
dic = dict()
for _ in range(M):
a, b, c = map(int, input().split())
a, b = a - 1, b - 1
dic[(a, b)] = c
dic[(b, a)] = c
dp = [[-INF] * N for _ in range(1 << N)]
que = deque()
for i in range(N):
dp[1 << i][i] = 0
que.append((1 << i, i))
ans = -1
while que:
state, ov = que.popleft()
ans = max(ans, dp[state][ov])
for nv in range(N):
nex_state = state | (1 << nv)
if nex_state == state:
continue
if (ov, nv) not in dic:
continue
nex_cost = dp[state][ov] + dic[(ov, nv)]
if dp[nex_state][nv] == -INF:
dp[nex_state][nv] = nex_cost
que.append((nex_state, nv))
elif dp[nex_state][nv] < nex_cost:
dp[nex_state][nv] = nex_cost
print(ans)
D - President
問題ページ
考察
たとえば、サンプル2はこのような入力でした。
$2$
$3,6,2$
$1,8,5$
$(3,6,2)$ は、「高橋くんに $3$ 票、青木くんに $6$ 票入っていて、勝っている方に $2$ 議席が入る」という意味でした。
この場合、青木くんの票 $2$ つを高橋くんのものにすると、「高橋くん $5$ 票、青木くん $4$ 票」になって、この $2$ 議席は高橋くんのものになります。
票を移動しなくても高橋くんの票の方が多い場合は、なんの処理もせずに $0$ を出力してしまって大丈夫です。 ここからは、高橋くんの票の方が少なかった場合について考えていきます。
票を移動させる前に、 $dist =(青木くんの票) - (高橋くんの票)$ を計算しておきます。
ここからは、移動する票を「コスト」、変化する議席数を「スコア」と呼ぶことにします(たぶんその方が分かりやすい)。
つまり、$(3,6,2)$ はコスト $2$ でスコア $4$ が得られます。
$(1,8,5)$ はコスト $4$ でスコア $10$ が得られます。
ここにはないですが、たとえば $(8,3,6)$ は票を移動させる前から青木くんの勝ちなので、これは $dist$ の計算のみにつかいます。
こうすることで、議席の問題は次の問題に言い換えられます。
整数 $dist$ が与えられます。
また、 $M$ 個のタプルがとんできます。タプルは以下の形式です。
$(c,s)$ : コスト $c$ を支払うことで、スコア $s$ を獲得できる。
目的は $dist$ 以上のスコアを獲得することです。そのために必要なコストの最小値を求めてください。
この問題は、つぎの2次元リストを用意して動的計画法で解くことができます。
$$dp[i][x]: タプルを左からi個だけ見たとき、スコアをxだけ獲得するのに必要なコストの最小値$$
初期値は $dp[0][0]=0$ です。
問題の入力で与えられる $z$ (=議席の数) の総和は $10^5$ 以下だと問題文にあるので、$dist \leq 10^5$ です。また $N \leq 100$ の制約もあるので、この2次元リストdpは、 $dist \times N \leq 10^5 \times 100 = 10^7$ 個のマスです。
マスそれぞれについて、「コストを支払わない場合」「コストを支払ってスコアを得る場合」の2通りしかなく、これならTLEせずに間に合いそうです。
コード
INF = 1 << 60
N = int(input())
takahashi, aoki = 0, 0
P = []
for _ in range(N):
x, y, z = map(int, input().split())
if x < y:
mid = (x + y) // 2 + 1
P.append((mid - x, z * 2))
aoki += z
else:
takahashi += z
dist = aoki - takahashi
if dist < 0:
print(0)
exit()
# dp[i][score]: 左からi個目まで見て、scoreを獲得するのに必要なコストの最小値
dp = [[INF] * (dist + 1) for _ in range(len(P) + 1)]
dp[0][0] = 0
for i in range(len(P)):
cost, score = P[i]
for j in range(dist + 1):
# コストを支払わない場合
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
# コストを支払ってスコアを得る場合
nj = j + score
if nj > dist:
nj = dist
dp[i + 1][nj] = min(dp[i + 1][nj], dp[i][j] + cost)
print(dp[len(P)][dist])
E - Avoid Eye Contact
問題ページ
考察
サンプル1の説明にある画像がヒントです。
もしあの画像と同じ入力だったら、通れるマスと通れないマスが明確なので、スタートのマスから幅優先探索BFSをすることでゴールまでの距離が分かります。
ただ、入力では人の視線がかかっているマスに '!' が入っていません。なので、人それぞれについて、視線の先が通れるマスである限り '!' に変換してしまいたくなります。
たとえば上向きor下向きの人については、行の数 $H$ をつかうと、その人の影響で '!' となるマスの数は $O(H)$ です。左向きor右向きの人も同様に、その人の影響で '!'となるマスの数は $O(W)$ です。
問題文には人の数に制限はなかったので、人の数は $O(HW)$ 。全体として計算量は $O(HW(H+W))$ となりそうです。 $2 \leq H,W \leq 2000$ の制約でこれはTLEしてしまいます。
...となりそうですが、実は計算量はそこまで大きくありません。
右向きの人しかいないときを考えてみます。 それぞれの人について、視線の先が通れるマスである限り '!' に変換してみます。変更するマスの数に注目すると、その数は $O(HW)$ となります。これは他の3つの向きでも同じく $O(HW)$ です。
なので、「それぞれの人について視線の先が通れるマスである限り '!' にして、通れないマスになったら打ち切る」とすれば、全体としてマスを見る回数は $O(HW)$ です。
あとは、通れるマスと通れないマスが分かっているので、幅優先探索BFSをすることでスタート地点からゴール地点までの距離が求められます。
コード
from collections import deque
dic = {
'<': (0, -1),
'>': (0, 1),
'^': (-1, 0),
'v': (1, 0)
}
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
si, sj, gi, gj = -1, -1, -1, -1
for i in range(H):
for j in range(W):
match A[i][j]:
case a if a in dic: # 上下左右のどれかの向きの人
vi, vj = dic[a]
ni, nj = i, j
while True:
ni, nj = ni + vi, nj + vj
if not (0 <= ni < H and 0 <= nj < W):
break
if A[ni][nj] not in '.!':
break
A[ni][nj] = '!'
case 'S':
si, sj = i, j
case 'G':
gi, gj = i, j
A[gi][gj] = '.' # ゴールマスも普通のマスだと思ってBFSして、(gi,gj)の位置までの距離を見ることにする。
que = deque()
que.append((si, sj))
dist = [[-1] * W for _ in range(H)]
dist[si][sj] = 0
while que:
oi, oj = que.popleft()
for ni, nj in [(oi, oj + 1), (oi, oj - 1), (oi + 1, oj), (oi - 1, oj)]:
if not (0 <= ni < H and 0 <= nj < W):
continue
if A[ni][nj] != '.' or dist[ni][nj] != -1:
continue
dist[ni][nj] = dist[oi][oj] + 1
que.append((ni, nj))
print(dist[gi][gj])