目次
AtCoder Beginner Contest 119 A,C,D問題メモ
A - Still TBD
問題
'YYYY/MM/DD' 形式の文字列 $S$ が与えられる- 2019年4月30日以前なら
'Heisei'、以後なら'TBD' と出力せよ
解法
多くの言語では、桁数がゼロ埋めで揃えられている数値文字列の比較は、文字列のまま比較が出来る。
ちなみにTBD = To Be Determined(未確定) らしい。果たして年号はDeterminedなのかPublishedなのか。
s = input()
if s <= '2019/04/30':
print('Heisei')
else:
print('TBD')
C - Synthetic Kadomatsu
問題
- $N$ 本の竹があり、長さは $l_1,l_2,...,l_N$
- これらを使って、長さが $A,B,C$ である3本の竹を作りたい
- 以下の3通りの操作ができる
- コスト1MP: 1本の竹の長さを1増やす
- コスト1MP: 1本の竹の長さを1減らす（長さ1の竹を選ぶことは出来ない）
- コスト10MP: 2本の竹を接いで1本にする。長さは2本の合計となる
- 最小コストを求めよ
- $3 \le N \le 8$
解法
$N$ が小さいので、全探索。どうやって全探索するかにちょっと手間取る。
1本の竹につき、考えられる使い方は4通り。
- 長さ $A$ の竹を作るのに使う
- 長さ $B$ の竹を作るのに使う
- 長さ $C$ の竹を作るのに使う
- 使わない
$N$ 本のそれぞれで4通りなので、$4^N \le 4^8=65536$。多くともこの数のパターンを調べればよい。
あるパターンのコストは、$A～C$ について使う竹を全て接ぐためのコストと、接いだ後に目標との差分だけ1ずつ増減させるコストの合計となる。
状態の列挙は、ビットで表現する。
N=5
0100101110
↓ 2桁ごと区切る
01 00 10 11 10
~~ ~~ ←1本目の竹の使い方
↑2本目の竹の使い方
00: 使わない
01: Aの竹を作るのに使う
10: Bの竹を作るのに使う
11: Cの竹を作るのに使う
これで、0から $4^N-1$ までをイテレートすると、全ての状態を列挙できる。
それぞれのコストを計算し、最小値が答え。$A,B,C$ がいくら短くとも、最低1本の竹は使っていないといけない点に注意。
n, a, b, c = list(map(int, input().split()))
lll = [int(input()) for _ in range(n)]
ans = 10 ** 9
for i in range(4 ** n):
ta, tb, tc = 0, 0, 0
tmp = 0
for j in range(n):
k = (i >> (2 * j)) & 3
if k == 1:
if ta > 0:
tmp += 10
ta += lll[j]
elif k == 2:
if tb > 0:
tmp += 10
tb += lll[j]
elif k == 3:
if tc > 0:
tmp += 10
tc += lll[j]
if ta == 0 or tb == 0 or tc == 0:
continue
tmp += abs(a - ta) + abs(b - tb) + abs(c - tc)
ans = min(ans, tmp)
print(ans)
D - Lazy Faith
問題
- 東西一直線の道路に、西端から $1,2,...$ と座標が振られている
- 道路沿いに $A$ 社の神社と $B$ 軒の寺が建っている
- $i$ 社目の神社は座標 $s_i$ の地点にある
- $i$ 軒目の寺は座標 $t_i$ の地点にある
- クエリが $Q$ 個与えられるので、全てに答えよ
- $x_i$ の地点から出発して道路上を自由に移動する
- 少なくとも神社と寺を1軒ずつ訪れたい
- 必要な最小移動距離を求めよ
- $1 \le A,B \le 10^5$
- $1 \le Q \le 10^5$
- $1 \le s_i,t_i,x_i \le 10^{10}$
- $s_i,t_j,x_k$ は全て異なる
解法
事前処理と二分探索
まず、取るべき行動は、以下のいずれかになる。各 $x_i$ について、以下の最小値を求めればよい。
- $x_i$ から西に最も近い神社に行き、そこから最も近い寺に行く
- $x_i$ から東に最も近い神社に行き、そこから最も近い寺に行く
- $x_i$ から西に最も近い寺に行き、そこから最も近い神社に行く
- $x_i$ から東に最も近い寺に行き、そこから最も近い神社に行く
たとえば1番目の行動で神社に着く前に既に寺を通過していた場合は、そこからさらに寺に行く必要は無くて無駄な移動になるが、その場合の最適な行動は3番目でフォローされている。
まずクエリを効率的に処理するため、以下を事前計算する。
- 各神社について、最も近い寺までの距離
- 各寺について、最も近い神社までの距離
二分探索を用いる方法がある。
座標 20 24 30 35
index 1 2 3
神社 ⛩ ⛩ ⛩
↑
i番目の寺 卍
Pythonでは bisect で二分探索が行える。 神社の列の中に座標24の寺を挿入する際、挿入すべきindexが返される。つまり、上の場合は'2'となる。 よって、$i$ 番目の寺から最も近い神社は1番目か2番目の神社なので、2社との距離を計算して小さい方が「$i$ 番目の寺について、最も近い神社までの距離」となる。
事前計算が済んだらクエリを順に処理する。これも同様にして、$x_i$ にとって西・東で最も近い神社・寺との距離を二分探索で求められる。
import bisect
import sys
a, b, q = list(map(int, input().split()))
lines = sys.stdin.readlines()
sss = list(map(int, lines[:a]))
ttt = list(map(int, lines[a:a + b]))
xxx = list(map(int, lines[a + b:]))
nearest_temples = [0] * a
nearest_shrines = [0] * b
for i, s in enumerate(sss):
ti = bisect.bisect(ttt, s)
nt = 10 ** 11
if ti > 0:
nt = min(nt, abs(s - ttt[ti - 1]))
if ti < b:
nt = min(nt, abs(s - ttt[ti]))
nearest_temples[i] = nt
for i, t in enumerate(ttt):
si = bisect.bisect(sss, t)
ns = 10 ** 11
if si > 0:
ns = min(ns, abs(t - sss[si - 1]))
if si < a:
ns = min(ns, abs(t - sss[si]))
nearest_shrines[i] = ns
buf = []
for x in xxx:
si = bisect.bisect(sss, x)
ti = bisect.bisect(ttt, x)
ans = 10 ** 11
if si > 0:
ans = min(ans, x - sss[si - 1] + nearest_temples[si - 1])
if si < a:
ans = min(ans, sss[si] - x + nearest_temples[si])
if ti > 0:
ans = min(ans, x - ttt[ti - 1] + nearest_shrines[ti - 1])
if ti < b:
ans = min(ans, ttt[ti] - x + nearest_shrines[ti])
buf.append(ans)
print('\n'.join(map(str, buf)))
二分探索時の端の処理分けが煩雑なのは、番兵置いたらもっとスッキリ書ける。ただ、置いて問題ないかなかなかパッと判断できないね。
import bisect
import sys
SENTINEL = 10 ** 12
a, b, q = list(map(int, input().split()))
lines = sys.stdin.readlines()
sss = [-SENTINEL] + list(map(int, lines[:a])) + [SENTINEL]
ttt = [-SENTINEL] + list(map(int, lines[a:a + b])) + [SENTINEL]
xxx = list(map(int, lines[a + b:]))
nearest_temples = [SENTINEL] + [0] * a + [SENTINEL]
nearest_shrines = [SENTINEL] + [0] * b + [SENTINEL]
for i, s in enumerate(sss[1:-1], start=1):
ti = bisect.bisect(ttt, s)
nearest_temples[i] = min(ttt[ti] - s, s - ttt[ti - 1])
for i, t in enumerate(ttt[1:-1], start=1):
si = bisect.bisect(sss, t)
nearest_shrines[i] = min(sss[si] - t, t - sss[si - 1])
buf = []
for x in xxx:
si = bisect.bisect(sss, x)
ti = bisect.bisect(ttt, x)
ans = min(x - sss[si - 1] + nearest_temples[si - 1],
sss[si] - x + nearest_temples[si],
x - ttt[ti - 1] + nearest_shrines[ti - 1],
ttt[ti] - x + nearest_shrines[ti])
buf.append(ans)
print('\n'.join(map(str, buf)))
