'YYYY/MM/DD' 形式の文字列 $S$ が与えられる'Heisei'、以後なら'TBD' と出力せよ多くの言語では、桁数がゼロ埋めで揃えられている数値文字列の比較は、文字列のまま比較が出来る。
ちなみにTBD = To Be Determined(未確定) らしい。果たして年号はDeterminedなのかPublishedなのか。
s = input()
if s <= '2019/04/30':
print('Heisei')
else:
print('TBD')
$N$ が小さいので、全探索。どうやって全探索するかにちょっと手間取る。
1本の竹につき、考えられる使い方は4通り。
$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)
事前処理と二分探索
まず、取るべき行動は、以下のいずれかになる。各 $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)))