久しぶりに全AC。。よかった。
Nの数から全数え上げをする問題、とすぐに気が付いたが、ある竹がAに取られたとき、B、Cには使えないという表現をどう数え上げるのに苦労した。
すべての竹に対し、A,B,Cあるいはいずれにも使われないという4パターンを渡せばよいと気が付く。 48 = 216 < 10万と計算量も見積もったうえで実装。これはpythonではitertoolsのproductを使えばループが可能。
for p in product("ABCD", repeat=N):
これを使うと、N=8の時、以下のような配列が手に入る。これを数え上げればよい。
AAAAAAAA AAAAAAAB AAAAAAAC ・ ・
from itertools import product def solve(N, A, B, C, Ls): ans = 10000 for p in product("ABCD", repeat=N): if "A" not in p or "B" not in p or "C" not in p: continue As = sum(Ls[i] for i in range(N) if p[i] == "A") Bs = sum(Ls[i] for i in range(N) if p[i] == "B") Cs = sum(Ls[i] for i in range(N) if p[i] == "C") tans = abs(As - A) + abs(Bs - B) + abs(Cs - C) + \ (p.count("A") - 1) * 10 + (p.count("B") - 1) * 10 + (p.count("C") - 1) * 10 ans = min(ans, tans) return ans assert (solve(3, 1, 1, 1, [1, 1, 1]) == 0) assert (solve(3, 1, 1, 1, [2, 2, 2]) == 3) assert (solve(3, 1, 1, 1, [2, 2, 4]) == 5) assert (solve(3, 2, 1, 1, [2, 2, 4]) == 4) assert (solve(3, 1, 1, 2, [2, 2, 4]) == 4)
ある地点から一番近い地点を探す。二分探索であることはすぐに気が付く。
2か所をたどるが、ある地点からたどって左右のそれぞれの神社、寺の合計4か所をたどることを考えればよく、 以下の4パターンのみである。ただし左右に分かれる場合には、戻ることになることに注意。
左神社、左寺 右神社、右寺 左神社、右寺 右神社、左寺
import bisect def solve(A, B, Q, Ss, Ts, Xs): ans = [] Ss.append(10 ** 21) Ss.insert(0, -10 ** 21) Ts.append(10 ** 21) Ts.insert(0, -10 ** 21) for x in Xs: s_right = bisect.bisect_right(Ss, x) s_left = max(s_right - 1, 0) t_right = bisect.bisect_right(Ts, x) t_left = max(t_right - 1, 0) s_right = Ss[s_right] s_left = Ss[s_left] t_right = Ts[t_right] t_left = Ts[t_left] d_s_right = abs(s_right - x) d_s_left = abs(s_left - x) d_t_right = abs(t_right - x) d_t_left = abs(t_left - x) tans = 10 ** 35 if x <= s_right and x <= t_right: tans = min(tans, max(d_t_right, d_s_right)) if s_left <= x and t_left <= x: tans = min(tans, max(d_s_left, d_t_left)) tans = min(tans, min(d_s_right, d_t_left) * 2 + max(d_s_right, d_t_left)) tans = min(tans, min(d_t_right, d_s_left) * 2 + max(d_t_right, d_s_left)) ans.append(str(tans)) return "\n".join(ans) assert (solve(1, 1, 1, [2], [0], [10]) == "10") assert (solve(1, 1, 1, [200], [0], [10]) == "210") assert (solve(1, 1, 1, [200], [0], [220]) == "220") assert (solve(2, 2, 1, [2, 100], [0, 4], [3]) == "3") assert (solve(2, 2, 1, [2, 100], [0, 4], [124]) == "120") assert (solve(2, 2, 1, [2, 100], [0, 4], [0]) == "2") assert (solve(2, 2, 1, [2, 100], [0, 4], [5]) == "3") if __name__ == "__main__": A, B, Q = tuple(map(int, input().split(" "))) Ss = [int(input()) for _ in range(A)] Ts = [int(input()) for _ in range(B)] Xs = [int(input()) for _ in range(Q)] print(solve(A, B, Q, Ss, Ts, Xs))
pythonのbisectで返されるindexは、探索対象の配列のレンジに収まらないことがある。
bisect.bisect_right([0, 1], 2) => 2 bisect.bisect_right([0, 1], -10) => 0
ここの境界条件にかなり時間を食ったが、一番最初と一番最後に絶対に使わないデータを入れておくことにより、 境界を気にせずにコードを書くことができる。
また、変数の名前の付け方が悪く扱いに苦労した。。左右ぐらいはきちんと変数名に入れよう。
