AtCoder Beginner Contest 060/AtCoder Regular Contest 073

atcoder

はい。
https://beta.atcoder.jp/contests/abc060

A - Shiritori

C++14

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int n,m;
    char a[10],b[10],c[10];
    scanf("%s %s %s",a,b,c);
    printf("%s\n",a[strlen(a)-1]==b[0] && b[strlen(b)-1]==c[0]?"YES":"NO");
    return 0;
}

末尾と先頭でしりとりになっているか確認。

B - Choose Integers

C++14

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    printf("%s\n",c%__gcd(a,b)==0?"YES":"NO");
    return 0;
}

__gcd()便利。

C - Sentou

Python3

n,t=map(int,input().split())
l=[int(i) for i in input().split()]
ans=[0]*3
for i in l:
    if i>=ans[2]:
        ans[0]+=t
        ans[1]=i
        ans[2]=i+t
    else:
        ans[0]+=i+t-ans[2]
        ans[1]=i
        ans[2]=i+t
print(ans[0])

tを先頭から確認する。いま何秒か、T秒後までお湯が出るというのを慎重に計算すれば大丈夫だと思う。。

D - Simple Knapsack

Python3

n,w=map(int,input().split())
d={}
p=0
for i in range(n):
    a,b=map(int,input().split())
    if a in d: d[a].append(b)
    else: d[a]=[b]
    p=max(p,a)
 
for i in range(4):
    if p-i in d:d[p-i].sort(reverse=True)
    else: d[p-i]=[0]
 
l={}
for i in d:
    t=0
    l[i]=[0]
    for j in d[i]:
        t+=j
        l[i].append(t)
ans=0
for ai,i in enumerate(l[p]):
    for bj,j in enumerate(l[p-1]):
        for ck,k in enumerate(l[p-2]):
            for em,m in enumerate(l[p-3]):
                x=ai*p+bj*(p-1)+ck*(p-2)+em*(p-3)
                if x<=w:
                    ans=max(ans,i+j+k+m)
print(ans)

各重さで使うのは価値が大きい方から累積和？を取っておく。サンプル2の入力だと、

[10]   #4
[7,13] #3
[1]    #2
[0]    #1

書き方にも拠るでしょうけど重さが4種類で各種には1つデータがあるはず想定している何も入ってないのがあるとエラーで落ちるか、ループ処理が途中で終わって調べたい全パターンが調べられなかったりすると思うので事前に注意しておく。 あとこれ4重ループにしてるんですけど4重にする意味はなくて、制限のw - 3重までの重さの総和 で追加可能な重さが定まるので4重目は回す意味無いです。多分。