【初級編：競プロを始めよう】を消化

atcoder

はい。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】
進捗 完了しました！
全探索　14/14

AtCoder Beginner Contest 144 B - 81
PyPy3

n=int(input())
d=set([i*j for i in range(1,10) for j in range(1,10)])
print("Yes" if n in d else "No")

C++

#include<bits/stdc++.h>
using namespace std;
 
#define sc1(a)  scanf("%d",&a)
 
int main(){
    int mod=1000000007;
    int n,ans;
    sc1(n);
    for (int i=1;i<10;i++)  for (int j=i;j<10;j++) {
        if (i*j==n) {
            printf("Yes\n");
            return 0;
        }
    }
    printf("No\n");
    return 0;
}

Pythonはちょっと遊び要素込みで。C++は真面目に全探索。

AtCoder Beginner Contest 150 B - Count ABC
PyPy3

n=int(input())
s=input()+"XXX"
ans=0
for i in range(n):
    if s[i]+s[i+1]+s[i+2]=="ABC": ans+=1
print(ans)

C++

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int mod=1000000007;
    int n,ans=0;
    char s[55];
    scanf("%d",&n);
    scanf("%s",s);
    for (int i=0;i<n;i++) if (s[i]=='A' && s[i+1]=='B' && s[i+2]=='C') ans++;
    printf("%d\n",ans);
    return 0;
}

どちらも先頭から真面目に全部見てます。末尾は調整が面倒なので適当に付け足してます。

AtCoder Beginner Contest 122 B - ATCoder
PyPy3

s=input()
ans=chk=0
for i in s:
    if i in "ACGT": chk+=1
    else: chk=0
    ans=max(ans,chk)
print(ans)

C++

#include<bits/stdc++.h>
using namespace std;
 
#define rep(i,n)  for(int i=0;i<n;++i)
 
int main(){
    int ans=0,chk=0;
    char s[15];
    scanf("%s",s);
    rep (i,10) {
        if (s[i]=='A' || s[i]=='C' || s[i]=='G' || s[i]=='T') {
            chk++;
        } else {
            chk=0;
        }
        ans=max(ans,chk);
    }
    printf("%d\n",ans);
    return 0;
}

C++だと文字列問題書く時になんかスムーズでない気がするので練習が足りないのでしょう。

AtCoder Beginner Contest 136 B - Uneven Numbers
PyPy3

n=int(input())
ans=0
for i in range(1,n+1):
    if len(str(i))%2: ans+=1
print(ans)

#print(len([i for i in range(1,int(input())+1) if len(str(i))%2]))

C++

#include<bits/stdc++.h>
using namespace std;
 
#define sc1(a)  scanf("%d",&a)
 
int main(){
    int n,ans=0;
    sc1(n);
    for (int i=n;i>0;i--) {
        if (i/100000>0) false;
        else if (i/10000>0) ans++;
        else if (i/1000>0) false;
        else if (i/100>0) ans++;
        else if (i/10>0) false;
        else ans++;
    }
    printf("%d\n",ans);
    return 0;
}

C++だと文字列問題書く時になんかスムーズでない気がするので練習が足りないのでしょう。前回と同じコメントになります。。
あと分岐の書き方もよくわかりません。
解説pdfでは文字列に変換して長さを見るとあったのでPythonでは大体解説通りな感じだと思います。あとちょっと違う書き方で1行で出来たりします。

AtCoder Beginner Contest 106 B - 105
PyPy3

n=int(input())
ans=chk=0
for i in range(1,n+1,2):
    chk=0
    for j in range(1,i+1):
        if i%j==0: chk+=1
    if chk==8: ans+=1
print(ans)

C++

#include<bits/stdc++.h>
using namespace std;
 
#define sc1(a)  scanf("%d",&a)

int main(){
    int n,ans=0,chk;
    sc1(n);
    for (int i=1;i<=n;i++) {
        chk=0;
        for (int j=1;j<=i;j++) {
            if (i%j==0) chk++;
        }
        i++;
        if (chk==8) ans++;
    }
    printf("%d\n",ans);
    return 0;
}

8になるものがかなり限られるらしいのですけども練習のお題としては全探索なのでこうなります。。

AtCoder Beginner Contest 120 B - K-th Common Divisors
PyPy3

a,b,k=map(int,input().split())
l=[]
for i in range(1,max(a,b)+1):
    if a%i==0 and b%i==0: l.append(i)
print(l[-k])

C++

#include<bits/stdc++.h>
using namespace std;

#define sc3(a,b,c)  scanf("%d %d %d",&a,&b,&c)

int main(){
    int a,b,k,n,m,ans;
    sc3(a,b,k);
    for (int i=100;i>0;i--) {
        if (a%i==0 && b%i==0) k--;
        if (k==0) {
            printf("%d\n",i);
            return 0;
        }
    }
    return 0;
}

単純な考察というかK番目に大きいとは何ぞやにちょっと引っかかりました。PythonとC++でちょっと方針が違うのはK番目～の影響です。

AtCoder Beginner Contest 057 C - Digits in Multiplication
PyPy3

n=int(input())
ans=1000
for i in range(1,100001):
    if n%i==0:
        ans=min(ans,len(str(max(n//i,i))))
print(ans)

C++

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    long long a=1000,b,n,p,x,ans=1000;
    scanf("%lld",&n);
    for (long long i=1;i<100001;i++) {
        if (n%i==0) {
            a=1;
            b=1;
            p=max(i,n/i);
            for (long long j=1;j<12;j++)  {
                if (p/b>0) a=j;
                b*=10;
            }
            ans=min(ans,a);
        }
    }
    printf("%lld\n",ans);
    return 0;
}

C++は練習が足りていないので盛大に時間を溶かしました。探索数を減らすのは N=A×B が成立するものを探すのに、Nが最大の1010のときでも105で大丈夫なはずでそれならTLEしないことがわかればできればいいのかなと。

AtCoder Beginner Contest 095 C - Half and Half
PyPy3

a,b,c,x,y=map(int,input().split())
z=min(x,y)
ans=min(a*z+b*z,c*z*2)+min(a*(x-z),c*2*(x-z))+min(b*(y-z),c*2*(y-z))
print(ans)

C++

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a,b,c,x,y,z,ans;
    scanf("%d %d %d %d %d",&a,&b,&c,&x,&y);
    z=min(x,y);
    ans=min(a*z+b*z,c*z*2)+min(a*(x-z),c*(x-z)*2)+min(b*(y-z),c*(y-z)*2);
    printf("%d\n",ans);
    return 0;
}

公式解説がわかりません。探索出来ません。式一行で求めるやり方しかわかりません。悲しいですね。

三井住友信託銀行プログラミングコンテスト2019 D - Lucky PIN
PyPy3

n=int(input())
s=input()
d=[[30005,-1] for i in range(10)]
ans=set([])
for i in range(n):
    p=int(s[i])
    if d[p][0]==30005:
        d[p][0]=i
        d[p][1]=i
    else:
        d[p][1]=i
 
for i in range(1,n-1):
    for j in range(10):
        if d[j][0]<i:
            for k in range(10):
                if d[k][1]>i:
                    ans.add(str(j)+str(s[i])+str(k))
 
print(len(ans))

C++

int main(){
    int n,m;
    char s[30005];
    int d[10][2];
    set<int> ans;
    for (int i=0;i<10;i++) {
        d[i][0]=30005;
        d[i][1]=-1;
    }
    scanf("%d",&n);
    scanf("%s",s);
    for (int i=0;i<n;i++) {
        int p=s[i]-'0';
        if (d[p][0]==30005) {
            d[p][0]=i;
            d[p][1]=i;
        } else {
            d[p][1]=i;
        }
    }
    for (int i=1;i<n-1;i++) {
        for (int j=0;j<10;j++) {
            if (d[j][0]<i) {
                for (int k=0;k<10;k++) {
                    if (d[k][1]>i) ans.insert(j*100+(s[i]-'0')*10+k);
                }
            }
        }
    }
    printf("%ld\n",ans.size());
    return 0;
}

公式解説がわかりません。とりあえず文字列として受け取ったSを先頭から見て0-9のそれぞれが最も左と最も右にある位置を調べておきます。Sの2桁目からN-1桁目を暗証番号の真ん中になる数字とします。真ん中になると仮定したものより左に右にある数字を使って暗証番号を作ることが出来ます。適当にset型に入れておきます。set型がよしなに重複を除いてくれるのでset内の要素数が解になるはずです。

AtCoder Beginner Contest 128 C - Switches
PyPy3

n,m=map(int,input().split())
k=[[int(i) for i in input().split()] for j in range(m)]
p=[int(i) for i in input().split()]
ans=chk=0
for i in range(2**n):
    l=[0]*n
    for j in range(n):
        if i&1: l[j]=1
        i=i>>1
    y=0
    for j in range(m):
        x=0
        for a in range(k[j][0]):
            if l[k[j][a+1]-1]==1: x+=1
        if x%2==p[j]%2: y+=1
    if y==m: ans+=1
print(ans)

C++

#include<bits/stdc++.h>
 
using namespace std;
 
#define rep(i,n)  for(int i=0;i<n;++i)
#define sc1(a)  scanf("%d",&a)
#define sc2(a,b)  scanf("%d %d",&a,&b)
 
int main(){
    int n,m,ans=0;
    sc2(n,m);
    int k[15][15];
    int p[15]={0};
    rep(i,15) rep(j,15) k[i][j]=0;
    rep(i,m) {
        sc1(k[i][0]);
        rep(j,k[i][0]) sc1(k[i][j+1]);
    }
    rep(i,m) sc1(p[i]);
    rep(i,pow(2,n)) {
        int x=i;
        int s[15]={0};
        rep(j,n) {
            if (x&1)  s[j]=1;
            x=x>>1;
        }
        int chk=0;
        rep(j,m) {
            int cnt=0;
            rep(a,k[j][0]) if (s[k[j][a+1]-1]==1) cnt=(cnt+1)%2;
            if (cnt==p[j]) chk++;
        }
        if (chk==m) ans++;
    }
    printf("%d\n",ans);
 
    return 0;
}

公式解説がわかりません。ビット全探索がお題なのでそうします。C++は書きなれていないのでかなり苦戦しました。

AtCoder Beginner Contest 147 C - HonestOrUnkind2
PyPy3

n=int(input())
w=[]
ans=chk=0
for i in range(n):
    a=int(input())
    t=[]
    for j in range(a):
        x,y=map(int,input().split())
        t.append((x,y))
    w.append(t)
for i in range(1,2**n):
    l=[0]*n
    for j in range(n):
        if i&1: l[j]=1
        i=i>>1
    chk=1
    for j in range(n):
        if l[j]:
            for k in w[j]:
                if l[k[0]-1]!=k[1]:
                    chk=0
                    break
    if chk: ans=max(ans,sum(l))
print(ans)

C++

#include<bits/stdc++.h>
using namespace std;
 
#define rep(i,n)  for(int i=0;i<n;++i)
#define per(i,n)  for(int i=n-1;i>=0;--i)
#define sc1(a)  scanf("%d",&a)
#define sc2(a,b)  scanf("%d %d",&a,&b)
#define sc3(a,b,c)  scanf("%d %d %d",&a,&b,&c)
 
 
int main(){
    int n,a,ans=0;
    sc1(n);
    int w[15][14][2];
    rep(i,15) rep(j,14) rep(k,2) w[i][j][k]=0;
    rep(i,n) {
        sc1(a);
        rep(j,a) sc2(w[i][j][0],w[i][j][1]);
    }
    rep(i,pow(2,n)) {
        if (i==0) continue;
        int x=i;
        int l[15]={0};
        rep(j,n) {
            if (x&1) l[j]=1;
            x=x>>1;
        }
        int f=1;
        rep(j,n) {
            if (l[j]) {
                rep(k,14) if (w[j][k][0]>0 && l[w[j][k][0]-1]!=w[j][k][1]) f=0;
            }
        }
        int cnt=0;
        if (f) {
            rep(j,n) cnt+=l[j];
            ans=max(ans,cnt);
        }
    }
    printf("%d\n",ans);
    return 0;
}

ビット全探索がお題なのでそうします。C++は書きなれていないのでかなり苦戦しました。あと探索用の数列用意するときに x&1 とするはずが x&i と書き間違えを繰り返す癖を直したいので練習積みましょう。

AtCoder Beginner Contest 145 C - Average Length
PyPy3

import itertools
 
n=int(input())
l=[int(i) for i in range(n)]
ans=chk=p=0
w=[]
for i in range(n):
    x,y=map(int,input().split())
    w.append((x,y))
for i in list(itertools.permutations(l,n)):
    chk=0
    for j in range(n-1):
        chk+=((w[i[j]][0]-w[i[j+1]][0])**2+(w[i[j]][1]-w[i[j+1]][1])**2)**0.5
    ans+=chk
    p+=1
 
print(ans/p)

C++

#include<bits/stdc++.h>
using namespace std;
 
#define rep(i,n)  for(int i=0;i<n;++i)
#define sc1(a)  scanf("%d",&a)
#define sc2(a,b)  scanf("%d %d",&a,&b)
#define sc3(a,b,c)  scanf("%d %d %d",&a,&b,&c)
 
int main(){
    int n,cnt=0;
    int d[8][2];
    double ans=0.0;
    sc1(n);
    vector <int>  p(n);
    rep(i,n) p[i]=i;
    rep(i,n) sc2(d[i][0],d[i][1]);
    do {
        //printf("%d %d %d\n",p[0],p[1],p[2]);
        cnt++;
        rep(i,n-1) ans+=pow(pow(d[p[i+1]][0]-d[p[i]][0],2)+pow(d[p[i+1]][1]-d[p[i]][1],2),0.5);
    } while (next_permutation(p.begin(),p.end()));
 
    printf("%.15lf\n",ans/(cnt*1.0));
    return 0;
}

順列全探索がお題なのでそうします。Python3ならitertoolsで、C++ならnext_permutationでしょうか。C++でdouble使うはずがfloat使っていて時間を溶かし。

AtCoder Beginner Contest 054 C - One-stroke Path
PyPy3

import itertools
n,m=map(int,input().split())
l=[[0]*n for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    l[a-1][b-1]=1
    l[b-1][a-1]=1
d=[int(i)+1 for i in range(n)]
ans=chk=0
for i in list(itertools.permutations(d,n)):
    chk=1
    if i[0]!=1: continue
    for j in range(n-1):
        chk*=l[i[j+1]-1][i[j]-1]
    ans+=chk
print(ans)

C++

#include<bits/stdc++.h>
using namespace std;
 
#define rep(i,n)  for(int i=0;i<n;++i)
#define per(i,n)  for(int i=n-1;i>=0;--i)
#define sc1(a)  scanf("%d",&a)
#define sc2(a,b)  scanf("%d %d",&a,&b)
#define sc3(a,b,c)  scanf("%d %d %d",&a,&b,&c)
 
int main(){
    int n,m,ans=0,chk=1;
    sc2(n,m);
    int d[8][8];
    vector <int> v(n);
    rep(i,n) v[i]=i;
    rep(i,8) rep(j,8) d[i][j]=0;
    rep(i,m) {
        int a,b;
        sc2(a,b);
        d[a-1][b-1]=1;
        d[b-1][a-1]=1;
    }
    do {
        if (v[0]!=0) continue;
        chk=1;
        rep(i,n-1) chk*=d[v[i+1]][v[i]];
        ans+=chk;
    } while (next_permutation(v.begin(),v.end()));
    printf("%d\n",ans);
    return 0;
}

順列全探索がお題なのでそうします。頂点が1から開始のみらしいのでそれをどう扱うか次第で全列挙する要素数が1つ減らせそうですが、経路を調べるときに初手と2手目以降でif分岐必要な気がしたので何もしませんでした。