Atcoder ABC167 A-DをPythonで

A. Registration

新しいidの$|S|-1$文字目までが同じであればYes、そうでなければNoを出力

ABC167a.py

a=input()
b=input()
s=len(a)
if b[:s]!=a:
    print("No")
else:
    print("Yes")

B. Easy linear programming

$k$が$a$よりも少なければ$a$のカードを$k$枚選ぶ。
$k$が$a+b$よりも少なければカードの和は$a$。
そうでなければカードの和は$a-(k-(a+b)))$

ABC167b.py

a,b,c,k=map(int,input().split())

if k<=a:
    print(k)
elif k<=a+b:
    print(a)
else:
    print(a-(k-(a+b)))

C. Skill up

コンテストの締切5分後にACでした。悔しい。
$N<12$なので、ビット全探索して条件を満たす最低価格を更新していけばいいです。

ABC167c.py

n,m,x=map(int,input().split())
l=[]

for i in range(n):
    a=list(map(int,input().split()))
    l.append(a)
ans=99999999
for i in range(2 ** n):
    bag = []
    for j in range(n):  #bit全探索
        if ((i >> j) & 1): 
            bag.append(l[j])  
    skill=[0]*m
    enough=[0]*m #各スキルにつき、xを超えているかどうかを判断
    money=0
    for sub in bag:
        money+=sub[0]
        for kk in range(1,m+1):
            skill[kk-1]+=sub[kk]
            if skill[kk-1]>=x:
                enough[kk-1]+=1
    if 0 not in enough: #全てのスキルがxを超えていたら価格を計算
        if ans>money:
            ans=money#最低価格を下回っていたら更新
if ans==99999999: #初期値からの変更がなければ-1を、そうでなければ最低価格を出力
    print(-1)
else:
    print(ans)

D. Teleporter

全てのテレポッドがどこかの街に行くので、高々$N$回以内にループに突入します。例えば例1では$1=>3=>4=>1...$, 例2では$1>=6=>2=>5=>3=>2...$といった具合に。ループに突入する前のテレポート回数を$t1$、突入した後のループ1回のテレポート回数を$t2$とすると、最後のテレポートの1つ前の位置は$(k-t1) mod t2$になります。あとはその場所の移動先を出力するだけです。行数も多いしコードも汚いので、もっと効率的な解き方があるのかもしれません。

ABC167d.py

n,k=map(int,input().split())

a=list(map(int,input().split()))

l=[1]
di={}
di[1]=1

for i in a:
    b=a[l[-1]-1]
    if b in di:
        x=b
        break
    l.append(b)
    di[b]=1
t1=0
for j in l:
    if j==x:
        break
    else:
        t1+=1

t2=len(l)-t1
if k<=t1:
    print(l[k])

else:
    aa=(k-t1)%t2
    print(l[t1+aa])

またDまでで時間を使い果たしてしまいました。来週こそは・・・