ABC374 感想まとめ

キーエンスプログラミングコンテスト2024（AtCoder Beginner Contest 374） - AtCoder

今回はリアルタイムでは不参加だったので、翌日にのんびり復習しました。A-Dまではノーヒントで解けた感じです。

A - Takahashi san 2

キーエンスでは、役割や年齢、立場の違いに関係なく「さん」付けして呼ぶという文化があります。

最近は外国でも「さん」をつけるケースもあるらしい。「〜さん」は老若男女問わず使えるので、便利でいいですよね。

pythonでは文字列の末尾を endswith() で判定します。

S = input()

if S.endswith('san'):
    print('Yes')
else:
    print('No')

B - Unvarnished Report

キーエンスでは良いことも悪いこともありのままに報告するという文化があります。

なるほど...。

「一致するとき・途中のi文字目が違うとき・文字数が違うとき」を場合分けして、求めました。

S = input()
T = input()

# 同じ時
if S == T:
    print(0)
    exit()

min_len = min(len(S), len(T))
for i in range(min_len):
    # i文字目が違うとき
    if S[i] != T[i]:
        print(i+1)
        exit()

# 文字数だけ違うとき
print(min_len+1)

C - Separated Lunch

DPのような考え方で、K[i] グループのどちらかに選ぶか・選ばないかのパターンを探索していく。
選ぶ・選ばないのパターンをすべて作っても、2^20=1048576 通りなので充分間に合いそうである。
全パターンをだして、最終的に「Kの全合計の半分」を超える最も小さい数が答えになる。

N = int(input())
K = list(map(int, input().split()))

# K の半数
border = (sum(K) + 1) // 2

answer_list = []

# 各 K[i] について
for i in range(N):
    p = K[i]

    # 既存の値に K[i] を足した配列を作る
    append_list = []
    for i in range(len(answer_list)):
        append_list.append(answer_list[i] + p)

    # 既存の配列 + 既存の値に K[i] を足した配列
    for i in range(len(append_list)):
        answer_list.append(append_list[i]) 

    # 0 から K[i] だけを加えたものを、配列に足す
    answer_list.append(p)

# 2分探索のためにソートしておく
answer_list = sorted(answer_list)

# answer_list の中で border 以下の最大値を2分探索で求める
index = bisect.bisect_left(answer_list, border)
print(answer_list[index])

D - Laser Marking

通る線分の順番を、順列全探索する(6!=720とおり)
各線分の始点→終点 or 終点→始点方向に描画...をbit全探索する(2^6=64とおり)

と、意外と少ないパターン数なので、全探索で制限時間内に収まりそうである。

N, S, T = map(int, input().split())
ABCD = []
for _ in range(N):
    A, B, C, D = map(int, input().split())
    ABCD.append((A, B, C, D))

# N! とおりの順列を考える
line_list = []
for i in range(N):
    line_list.append(i)

answer = 10**18

# lineの順列を全探索    
for line in itertools.permutations(line_list):

    # 各ラインの始点(AB)からか、終点(CD)からかを考える
    for bit in itertools.product((0, 1), repeat=N):

        position = (0, 0)
        time = 0
        # 各ラインの始点(AB)==1からか、終点(CD)から==0か
        for i in range(N):
            A, B, C, D = ABCD[line[i]]
            if bit[i] == 1:
                # (AB)まで移動（描画なし）
                time += math.sqrt((position[0] - A)**2 + (position[1] - B)**2) / S
                # (CD)まで描画しながら移動
                time += math.sqrt((A - C)**2 + (B - D)**2) / T
                position = (C, D)
            else:
                # (CD)まで移動（描画なし）
                time += math.sqrt((position[0] - C)**2 + (position[1] - D)**2) / S
                # (AB)まで描画しながら移動
                time += math.sqrt((C - A)**2 + (D - B)**2) / T
                position = (A, B)
        answer = min(answer, time)

print(answer)