AtCoder Beginner Contest 054

atcoder

はい。
https://atcoder.jp/contests/abc122

A - One Card Poker

Python3

a,b=map(int,input().split())
print('Draw' if a==b else 'Alice' if b!=1 and (a==1 or a>b) else 'Bob')

強弱、引き分けを判定して出力。

B - Template Matching

Python3

n,m=map(int,input().split())
master,sub=[],[]
for i in range(n):
    master.append(input())
for j in range(m):
    sub.append(input())
def chk(a,b,y,x):
    t=len(b)
    for i in range(t):
        if a[y+i][x:x+t]!=b[i]:
            return 0
    return 1
 
for i in range(n-m+1):
    for j in range(n-m+1):
        if master[i][j:j+m]==sub[0]:
            if chk(master,sub,i,j):
                print('Yes')
                exit()
print('No')

全部調べる。

C - One-stroke Path

Python

import itertools
 
n,m=map(int,input().split())
path={i+1:[] for i in range(n)}
for i in range(m):
    u,v=map(int,input().split())
    path[u].append(v)
    path[v].append(u)
chk=[i for i in range(2,n+1)]
ans=0
for way in list(itertools.permutations(chk)):
    now=1
    if way[0] in path[now]:
        f=1
        for j in way:
            if j in path[now]:
                now=j
                f+=1
            else:
                break
        if f==n: ans+=1
print(ans)

覚えてないです。。でも過去にこれコンテスト中にACしたようです。謎。

D - Mixing Experiment

Python3

mod=1777777777
n,ma,mb=map(int,input().split())
d=[[mod for j in range(100)] for i in range(100)]
for i in range(n):
    a,b,c=map(int,input().split())
    for j in range(100-a-1,-1,-1):
        for k in range(100-b-1,-1,-1):
            d[j+a][k+b]=min(d[j+a][k+b],d[j][k]+c)
    d[a][b]=min(d[a][b],c)
ans=mod
for i in range(100):
    if i%ma==0 and mb*i//ma<100:
        ans=min(ans,d[i][mb*i//ma])
 
print([ans,-1][ans==mod])

各薬品の在庫が1なので要注意。問題文はよく読みましょう。DPかな。配列の大きさをどれくらい確保すればいいかよくわからなくて適当です。d[100][100]で確保して。d[タイプAグラム][タイプBグラム]=コストの値を入れる。入力を受け取りながら更新した。更新は重い方から。軽い方から更新するとaグラム、bグラムを既に追加したものに対しても追加しようとする気がします。問題文はよく読みましょう。