AtCoder Beginner Contest 046/AtCoder Regular Contest 062

atcoder

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

A - AtCoDeerくんとペンキ / AtCoDeer and Paint Cans

C++14

#include<bits/stdc++.h>
 
using namespace std;
 
int main(){
    int a,b,c;
    scanf("%d",&a);
    scanf("%d",&b);
    scanf("%d",&c);
    if (a-b-c==-a && b==c) {
        printf("1\n");
    } else if (a==b || a==c || b==c) {
        printf("2\n");
    } else {
        printf("3\n");
    }
    return 0;
}

a,b,cのいずれかで等しい数があるかを確認する。

B - AtCoDeerくんとボール色塗り / Painting Balls with AtCoDeer

C++14

#include<bits/stdc++.h>
 
using namespace std;
 
int main(){
    int mod=1000000007;
    int n,k;
    long long tmp=1;
    scanf("%d %d",&n,&k);
    for (int i=0;i<n-1;i++) {
        tmp*=k-1;
    }
    printf("%lld\n",tmp*k);
    return 0;
}

1個目はk色使える、2個目以降はk-1色使える。

C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report

Python3

#!/usr/bin/env python3
 
n=int(input())
 
x,y=map(int, input().split())
for i in range(n-1):
    t,a=map(int, input().split())
    if (x<=t and y<=a):
        x=t
        y=a
    else:
        tmp=0
        k=max(x//t,y//a)
        tk=t*k
        ak=a*k
        while 1:
            if x<=tk+(tmp*t) and y<=ak+(tmp*a):
                x=tk+(tmp*t)
                y=ak+(tmp*a)
                break
            tmp+=1
print(x+y)

C++14

#include<bits/stdc++.h>

using namespace std;

int main(){
    long long x,y;
    int n,t,a;
    scanf("%d",&n);
    scanf("%lld %lld",&x,&y);
    for (int i=1;i<n;i++) {
        scanf("%d %d",&t,&a);
        if (x<=t && y<=a) {
            x=t;
            y=a;
        } else {
            x=t*max((x+t-1)/t,(y+a-1)/a);
            y=a*max((x+t-1)/t,(y+a-1)/a);
        }
    }
    printf("%lld\n",x+y);
    return 0;
}

得票数の比のt,aのどちらかがそれまでの得票数より少ない場合はそれぞれを得票数/比の大きいと比の積で何かした。forループで沢山票数増やして探すようなこと書かなくてもすぐに票数決められるようだ。解説pdfはmax()の計算の時に端数繰り上げのことに触れてないけど多分端数繰り上げ必要じゃないかなー、と思う。よくわかってないけど。。。

D - AtCoDeerくんと変なじゃんけん / AtCoDeer and Rock-Paper

C++14

#include<bits/stdc++.h>
 
using namespace std;
 
int main(){
    char s[100001];
    int ans=0;
    scanf("%s",s);
    for (int i=0;i<strlen(s);i++) {
        if (i%2==0) ans+=(s[i]=='g'?0:-1);
        if (i%2 && s[i]=='g') ans++;
    }
    printf("%d\n",ans);
    return 0;
}

自分の手は常にgpgp...想定でいい気がする。ggpp...とか入出力例2のコメントとかのようにずらしてでも偶然最高点になることはあるけども出し方を変えても単純なgpの繰り返しより点数が大きくなることはないはず。証明はしないですけど。。