A – 753
A - 753
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
問題文通りに実装すればOKです。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int X;
cin>>X;
if(X==3||X==5||X==7) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
B – 754
B - 754
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
Sの長さが小さいので、部分文字列全てに対して753との差を取ればOKです。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
string S;
cin>>S;
int ans=INT_MAX;
for(int i=0;i<S.size()-2;i++){
int n=(S[i]-'0')*100+(S[i+1]-'0')*10+(S[i+2]-'0');
ans=min(ans,abs(n-753));
}
cout<<ans<<endl;
}
S[i]-'0'
とやると、文字を数字に変換することができます。
文字は内部的には数字で、’0′,’1′,’2’…は連番になっているため、’0’を引くことで’0’からの相対位置=その文字の数字が拾えます。
C – 755
C - 755
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
“7”,”5″,”3″で数字を作ることを考えた場合、使う数字が三種類しかないため、
1桁のパターン → 3パターン 2桁のパターン → 3^2=9パターン .... N桁のパターン → 3^Nパターン
で、Nが最大9なので最大29523パターンしかありません。
全パターン作り、3,5,7が1個ずつありN以下であるものを抽出しても十分間に合いそうです。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
set<long long> s;
void make(long long n,int k,int c1,int c2,int c3){
if(c1>0&&c2>0&&c3>0) s.insert(n);
if(k!=0){
make(n*10+3,k-1,c1+1,c2,c3);
make(n*10+5,k-1,c1,c2+1,c3);
make(n*10+7,k-1,c1,c2,c3+1);
}
}
int main(){
int N;
cin>>N;
make(0,9,0,0,0);
int c=0;
auto it=s.begin();
while(it!=s.end()){
if(*it<=N) {
//cout<<*it<<endl;
c++;
}
it++;
}
cout<<c<<endl;
}
完全におまけですが、1月ごろに桁DPの練習として解いていました。
当時のマクロのままですが載せておきます。
※禁断のマクロ、#define int long longがありますが、気にしないで下さい＞＜
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>
#include<stack>
#include<climits>
#include<cmath>
using namespace std;
#define int long long
#define MOD (1000000007)
#define MINF (-1*(LLONG_MAX-10))
#define INF (LLONG_MAX-10)
int ketadp(int N){
int dp[10][2][2][2][2]={{{{{0}}}}};
int q=0;
int tmpn=N;
while(tmpn!=0){
q++;
tmpn/=10;
}
dp[0][0][0][0][0]=1;
for(int i=0;i<q;i++){
int n=N/(int)pow(10,q-i-1)%10;
for(int j=0;j<2;j++){
for(int k=0;k<2;k++){
for(int l=0;l<2;l++){
for(int m=0;m<2;m++){
int t=0;
int s=0;
if(i==0) s=1;
if(m==0) t=n;
else t=9;
for(int w=s;w<=t;w++){
//cout<<i<<","<<j<<","<<k<<","<<l<<","<<m<<","<<w<<","<<dp[i][j][k][l][m]<<endl;
int tm=0;
if(w!=t||m==1) tm=1;
if(w==3){
dp[i+1][1][k][l][tm]+=dp[i][j][k][l][m];
}
else if(w==5){
dp[i+1][j][1][l][tm]+=dp[i][j][k][l][m];
}
else if(w==7){
dp[i+1][j][k][1][tm]+=dp[i][j][k][l][m];
}
}
}
}
}
}
}
return dp[q][1][1][1][0]+dp[q][1][1][1][1];
}
signed main(){
int N;
cin>>N;
int q=0;
int tmpn=N;
while(tmpn!=0){
q++;
tmpn/=10;
}
int qq=0;
int ans=0;
for(int i=0;i<q-1;i++){
qq*=10;
qq+=9;
ans+=ketadp(qq);
}
ans+=ketadp(N);
cout<<ans<<endl;
}
D – 756
D - 756
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
2*2*3=12の場合、約数が1,2,3,4,6,12の6個あります。
これは、素因数分解した後のそれぞれの素数の個数から計算できます。
12=2*2*3なら 2を0,1,2個使う → 3通り 3を0,1個使う → 2通り 3*2=6通り
なので、約数が75個というのは以下の4パターンの時です。
ある素因数A,B,Cの個数に着目して Aが74個ある → 75通り Aが14個、Bが4個ある → 15*5=75通り Aが24個、Bが2個ある → 25*3=75通り Aが4個、Bが4個、Cが2個ある → 5*5*3=75通り
N!を素因数分解、それぞれの素数の個数をカウントし、上記4通りのいずれか作れる3つの組み合わせをカウントすればOKです。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
set<long long> s;
int main(){
int N;
cin>>N;
int c[100]={0};
for(int i=2;i<=N;i++){
int n=i;
for(int j=2;j<=i;j++){
while(n%j==0){
c[j]++;
n/=j;
}
}
}
int ans=0;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
for(int k=j+1;k<N;k++){
if(i!=j&&j!=k&&i!=k){
if(c[i]>=2&&c[j]>=4&&c[k]>=4) ans++;
}
}
}
}
for(int j=0;j<N;j++){
for(int k=0;k<N;k++){
if(j!=k){
if(c[j]>=14&&c[k]>=4) ans++;
if(c[j]>=24&&c[k]>=2) ans++;
}
}
}
for(int k=0;k<N;k++){
if(c[k]>=74) ans++;
}
cout<<ans<<endl;
}
コメント