AtCoder Beginner Contest 119

python3

AtCoder Beginner Contest 119のふりかえり

atcoder.jp

結果はA、Bの二完 (AとBしか解けなかったけど緑にいけた)

C問題

やったこと

どうやるのか全く思いつかなかった。どの材料より短いやつは先にのけとく？？

解法

N < 8 なので全探索可能(!)。 たけの扱いは4通り。

  • 長さA の竹の “材料” とする

  • 長さ B の竹の材料とする

  • 長さ C の竹の材料とする

  • 使わない

この4N通りを全部試す。深さ優先探索で探索すれば良い。

N, A,B,C = map(int, input().split())
l = sorted([int(input()) for _ in range(N)])[-1::-1]

INF = 1e+10

def dfs(cur, a, b, c):
    if cur == N:
#         print("a:{}, b:{}, c:{}".format(a,b,c))
        # 材料が何も使われないことを防ぐ為にa=b=c=0の時INFを返す
        # 30は余分に数えているMP
        return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF
    # cur本めを使わない場合
    ret0 = dfs(cur + 1, a, b, c)
    # cur本めをAに使う場合
    ret1 = dfs(cur + 1, a + l[cur], b, c) + 10
    # cur本めをBに使う場合
    ret2 = dfs(cur + 1, a, b + l[cur], c) + 10
    # cur本めをCに使う場合
    ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10
    
    print("cur:{}, a:{},b:{},c:{},ret0:{}, ret1:{}, ret2:{}, ret3:{}".format(cur,a,b,c,ret0,ret1,ret2,ret3))
    return min(ret0, ret1, ret2, ret3)

print(dfs(0, 0, 0, 0))

D問題

やったこと

一番近い神社・寺をみて、それらからもっとも近い寺・神社までの距離を足す。その2つのうち短い方を先に訪れるという戦略をとったが、TLE。

import numpy as np
A,B,Q = map(int, input().split())

s_list = [int(input()) for _ in range(A)]
t_list = [int(input()) for _ in range(B)]
x_list = [int(input()) for _ in range(Q)]

# print("s : ",s_list)
# print("t : ",t_list)
# print("x : ",x_list)

s_nearest_t = []
t_nearest_s = []

for s in s_list:
    t_dis = [abs(s-t) for t in t_list]
    s_nearest_t.append(np.min(t_dis))
for t in t_list:
    s_dis = [abs(s-t) for s in s_list]
    t_nearest_s.append(np.min(s_dis))


def get_ans(s_list, t_list, x):
    s_res = [abs(s-x) for s in s_list]
    t_res = [abs(t-x) for t in t_list]
    s_nearest = np.min(s_res)
    t_nearest = np.min(t_res)
    
    s_nearest_idx = s_res.index(s_nearest)
    t_nearest_idx = t_res.index(t_nearest)
    
    if s_nearest_t[s_nearest_idx] + s_nearest < t_nearest_s[t_nearest_idx] + t_nearest:
        ans = s_nearest_t[s_nearest_idx] + s_nearest
    else:
        ans = t_nearest_s[t_nearest_idx] + t_nearest

    return ans
        
for x in x_list:
    print(get_ans(s_list, t_list, x))

解法

二分探索で挿入位置を探すと早い。pythonでは bisect という標準ライブラリがある。 bisect_right で挿入位置の一個右のインデックスを得られる。

import bisect
A,B,Q = map(int, input().split())

INF = 1e+18

s_list = [-INF] + [int(input()) for _ in range(A)] + [INF]
t_list = [-INF] + [int(input()) for _ in range(B)] + [INF]
x_list = [int(input()) for _ in range(Q)]

def get_ans(s_list, t_list, x):
    b, d = bisect.bisect_right(s_list, x), bisect.bisect_right(t_list, x)
    ans = INF
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            ans = min(ans, d1, d2)
    return ans
        
for x in x_list:
    print(get_ans(s_list, t_list, x))