ABC374振り返り

前回の振り返り

今日はABC開催日だったので参加結果を振り返る

今週はA,B,C,Dの4完(0ペナ)

A

後ろ3文字がsanであるか判定

ソースコード

main.py

import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

def main():
    S = rS()
    
    ans = S[-3:] == "san"
    print("Yes" if ans else "No")
    
if __name__ == '__main__':
    main()

B

文字列が順番に違うか判定して、違ったらその位置、
短い方全部一致したら短い文字列の長さ+1

ソースコード

main.py

import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

def main():
    S = rS()
    T = rS()
    
    ans = 0
    for i,st in enumerate(zip(S,T),start=1):
        s,t = st
        if s != t:
            ans = i
            break
    else:
        if (s:=len(S)) != (t:=len(T)):
            ans = min(s,t)+1
    print(ans)
    
if __name__ == '__main__':
    main()

C

グループ全体の総和を求め
Aにいれるグループを求めたら全体からそれを引けばBにいれる人数
そのどちらか大きい方が答えだが、
どう組み合わせるかはNが20以下なのでbit全探索

ソースコード

main.py

import sys
from itertools import product
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

def main():
    N = rI()
    K = rLI()
    S = sum(K)
    
    ans = S
    for v in product([0,1],repeat=N):
        t1 = sum(K[i] for i in range(N) if v[i] == 1)
        t0 = S-t1
        t = max(t1,t0)
        ans = min(ans,t)
    print(ans)
    
if __name__ == '__main__':
    main()

D

Nが最大6なのでそれぞれの線をすべての順番で調べる
どっちかで始めるのかも自由なので、C,Dから書く場合も考慮するためフラグをbit全探索
つまり、順列全探索とbit全探索の合せ技

ソースコード

main.py

from math import sqrt
import sys
from itertools import permutations,product
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

def main():
    N,S,T = rLI()
    coords = [rLI() for _ in range(N)]

    ans = float("inf")
    for P in permutations(list(range(N)),N):
        for R in product([0,1],repeat=N):
            St = 0
            x,y=0,0
            for i in P:
                A, B, C, D = coords[i]
                if R[i] == 0:
                    s = sqrt((A-x)**2 + (B-y)**2)/S
                    t = sqrt((C-A)**2 + (D-B)**2)/T
                    x,y = C,D
                else:
                    s = sqrt((C-x)**2 + (D-y)**2)/S
                    t = sqrt((A-C)**2 + (B-D)**2)/T
                    x,y = A,B
                St += s+t
            ans = min(ans,St)
    print(ans)
    
if __name__ == '__main__':
    main()

E

各工程でW個製造するときにかかる最小のコストを計算する方法がわからなかった

F

Eに時間取られて考える余裕がなかった

G

求めたい値がよくわからなかった

まとめ

今回のC,Dは全探索する実装で解くことができた
制約数見ることは重要だと改めて認識

次はE問題を解けるようにしたい