はい。
https://atcoder.jp/contests/abc114
A - 753
x=int(input())
chk=[7,5,3]
print("YES" if x in chk else "NO")
#include<bits/stdc++.h>
using namespace std;
#define sc1(a) scanf("%d",&a)
int main(){
int x;
sc1(x);
printf("%s\n",(abs(x-5)==2 || x==5)?"YES":"NO");
return 0;
}
7,5,3のどれかではないかを調べる。if文で条件沢山書くよりは in 配列とかで確認するのが楽だと思います。
B - 754
s=input()
x=len(s)
ans=10**9+7
for i in range(x):
ans=min(ans,abs(753-int(s[i:i+3])))
print(ans)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
int main(){
char s[15];
int n,m,ans=mod;
scanf("%s",s);
long l=strlen(s);
rep(i,l) {
int w=0;
rep(j,l-i) {
w*=10;
w+=s[i+j]-'0';
if ( w<1000 && w>99) ans=min(ans,abs(w-753));
}
}
printf("%d\n",ans);
return 0;
}
ループ回して余裕なので調べます。必要なトコをスライスしてintでキャストして753との差の絶対値を調べます。
C - 755
t=["0","3","5","7"]
s=["3","5","7"]
n=int(input())
ans=chk=0
for a in t:
for b in t:
for c in t:
for d in t:
for e in t:
for f in t:
for g in s:
for h in s:
for i in s:
x=str(int(a+b+c+d+e+f+g+h+i))
y=set(list(x))
if ("0" not in y) and (len(y)==3) and (int(x)<=n):
ans+=1
print(ans)
def f(a,b):
if a==7 and b>=4: return b
if a==7 and b<4: return b+4
if a==5 and b in (2,3,6,7): return b
if a==5 and b not in (2,3,6,7): return b+2
if a==3 and b in (1,3,5,7): return b
if a==3 and b not in (1,3,5,7): return b+1
n=input()
l=[int(i) for i in "0"+n]
dp=[[[0]*9,[0]*9] for _ in "ww"]
dp[0][0][0]=1
chk=(7,5,3)
for i,j in enumerate(l):
if i==0: continue
elif i==1:
if j in chk: dp[i%2][0][f(j,0)]=1
if j not in chk: dp[i%2][0][0]=1
if j>7: dp[i%2][1][4]+=1
if j>5: dp[i%2][1][2]+=1
if j>3: dp[i%2][1][1]+=1
dp[i%2][1][0]=1
else:
dp[i%2][1][0]=1
dp[i%2][1][4]+=1
dp[i%2][1][2]+=1
dp[i%2][1][1]+=1
for k in range(8):
if dp[i%2-1][0][k] and (k==0 or j not in chk): dp[i%2][0][0]=1
elif dp[i%2-1][0][k] and j in chk: dp[i%2][0][f(j,k)]=1
if dp[i%2-1][0][k] and k!=0:
if j>7: dp[i%2][1][f(7,k)]+=1
if j>5: dp[i%2][1][f(5,k)]+=1
if j>3: dp[i%2][1][f(3,k)]+=1
if dp[i%2-1][1][k] and k!=0:
dp[i%2][1][f(7,k)]+=dp[i%2-1][1][k]
dp[i%2][1][f(5,k)]+=dp[i%2-1][1][k]
dp[i%2][1][f(3,k)]+=dp[i%2-1][1][k]
for k in range(9):
dp[i%2-1][0][k]=0
dp[i%2-1][1][k]=0
print(dp[0][0][7]+dp[0][1][7]+dp[1][0][7]+dp[1][1][7])
#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 sl1(a) scanf("%lld",&a)
long long n,ans;
bool p[13];
map <int ,long long> v;
bool chk(int a) {
bool d[3]={0,0,0};
while(a>0) {
if(a%10==3) d[0]=1;
if(a%10==5) d[1]=1;
if(a%10==7) d[2]=1;
a/=10;
}
if (d[0]==1 && d[1]==1 && d[2]==1) return 1;
else return 0;
}
void sol(long long x){
rep(i,3) {
x*=10;
x+=v[i];
if (x>n) return;
if (chk(x)) ans++;
sol(x);
x/=10;
}
}
int main(){
sl1(n);
v[0]=3ll;v[1]=5ll;v[2]=7ll;
sol(0ll);
printf("%lld\n",ans);
return 0;
}
9重ループは本当にダメです。
桁DP練習で試してみた方も753の出現状況を1,2,4でフラグ管理？をして全て出現したら合計7になる(Linuxとかのパーミッション設定からパクりました)。行数は嵩んだしフラグ管理も面倒でかなり大変でした。
桁DPよりは753しか使わないで、再帰で数を作るようにしたほうが楽そうな気がします。
D - 756
def sol():
n=int(input())
e=[0]*(n+1)
for i in range(2,n+1):
cur=i
for j in range(2,i+1):
while cur%j==0:
e[j]+=1
cur//=j
ans=0
for i in range(n+1):
if e[i]>73: ans+=1
for i in range(n):
for j in range(i+1,n+1):
if e[i]>23 and e[j]>1: ans+=1
if e[i]>1 and e[j]>23: ans+=1
for i in range(n):
for j in range(i+1,n+1):
if e[i]>13 and e[j]>3: ans+=1
if e[i]>3 and e[j]>13: ans+=1
for i in range(n-1):
for j in range(i+1,n):
for k in range(j+1,n+1):
if e[i]>3 and e[j]>3 and e[k]>1: ans+=1
if e[i]>3 and e[j]>3 and e[k]>3: ans+=1
if e[i]>1 and e[j]>3 and e[k]>3: ans+=1
print(ans)
if __name__=="__main__":
sol()
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define sc1(a) scanf("%d",&a)
int cnt[105];
int main(){
int xod=100, n,m=0,ans=0;
vector <int> pb;
bool tb[xod+3];
rep(i,xod+3) tb[i]=1;
sc1(n);
for(int i=2;i*i<=101;i++) {
if (!tb[i]) continue;
for(int j=i*i;j<=xod;j+=i) {
tb[j]=0;
}
}
for(int i=2;i<xod;i++) if(tb[i]) pb.push_back(i);
for(auto i=pb.begin();i!=pb.end();++i) m++;
for(int i=2;i<=n;i++) {
int w=i;
for (auto j=pb.begin();j!=pb.end();++j) {
if(w==1) break;
while(w%*j==0) {
cnt[*j]++;
w/=*j;
}
}
}
int ans2=0,ans3=0;
for (int i=0;i<25;i++) for(int j=0;j<25;j++) for(int k=0;k<25;k++) {
if (i!=j && i!=k && j!=k) {
if (cnt[pb[i]]>3 && cnt[pb[j]]>3 && cnt[pb[k]]>3) ans3++;
else if (cnt[pb[i]]>1 && cnt[pb[j]]>3 && cnt[pb[k]]>3) ans2++;
}
}
ans+=(ans2/2) + (ans3/2);
int ans4=0; ans2=0;
for (int i=0;i<25;i++) for(int j=0;j<25;j++) {
if (i!=j) {
if (cnt[pb[i]]>23 && cnt[pb[j]]>23 ) ans4++;
else if (cnt[pb[i]]>3 && cnt[pb[j]]>23) { ans2++; ans2++; }
else if (cnt[pb[i]]>3 && cnt[pb[j]]>13) ans2++;
else if (cnt[pb[i]]>1 && cnt[pb[j]]>23) ans2++;
}
}
ans+=(ans2) + (ans4*2);
rep(i,100) if (cnt[i]>73) ans++;
printf("%d\n",ans);
return 0;
}
殆どはpdf解説資料のコードを利用してます。
Nの階乗の約数を知るのにN!がいくつなのか、9!が362880というのはそれほど重要な情報ではないです。多分。。。
9!=362880は、27 x 34 x 5 x 7です。これは上のコードでは配列eの中に入っています。
あと七五数は、p74, p24 q3, p14 q4, p4 q4 r3 のいずれかの時に成立するようです。なので素因数分解で調べておいたものからpqrが違う数で必要な個数が使えるものがあるかを全部調べて数える個数が解になるはずです。
pdf解説ではlambdaでさっくりと求めているようです。lambda式覚えましょう。
C++で書いたのは100までの数を素因数分解して出現回数を調べておいて七五数になるものをなんとか数えます。
