はい。 oox-
C問題は時間内になんとか出来そうだったけど時間が一部codeforcesと重複していたし、学生ではないので上位を狙う必要がなかったので途中で切り上げました。
https://atcoder.jp/contests/code-festival-2014-quala
A - CODE FESTIVAL 2014
問題文では明記されておらずClarでツッコミが入っていたが末尾に2014を付け足して出力する。
print(input()+"2014")
#include<iostream>
#include<cmath>
#include<string>
#include<cctype>
#include<vector>
#include<numeric>
#include<algorithm>
using namespace std;
int main(){
double pai=3.141592653589;
char w[20];
scanf("%s",w);
printf("%s2014\n",w);
return 0;
}
まぁこういう問題ならLL言語のが圧倒的に書きやすいと思う。。
B - とても長い文字列
a=input()
b=int(input())
x=len(a)
print(a[(b-1)%x])
#include<iostream>
#include<cmath>
#include<string>
#include<cctype>
#include<vector>
#include<numeric>
#include<algorithm>
using namespace std;
int main(){
string A;
long long B;
cin>>A;
cin>>B;
int len,chk;
len=A.size();
chk=B%len-1;
if(chk<0) chk=len-1;
cout<<A[chk]<<endl;
return 0;
}
剰余で何番目かを調べる。
C - 2月29日
a,b=map(int,input().split())
a-=1
print((b//4-b//100+b//400)-(a//4-a//100+a//400))
#include<iostream>
#include<cmath>
#include<string>
#include<cctype>
#include<vector>
#include<numeric>
#include<algorithm>
using namespace std;
int main(){
long long A,B,ac,bc;
cin>>A>>B;
int f=0;
if(A%400==0 || (A%100!=0 && A%4==0)) f=1;
ac=A/4-A/100+A/400;
bc=B/4-B/100+B/400;
cout<<bc-ac+f<<endl;
return 0;
}
Bまでのうるう年の回数からAの一年前までの回数を引いて調べる。Aは生まれている年なので一年ずらさないとうるう年の場合に計算がずれます。
D - 壊れた電卓
def cnt(x,y):
z=set([])
while x>0:
z.add(x%10)
x//=10
if len(z)<=y: return 1
else: return 0
qq=9999999999999999
a,k=map(str,input().split())
k=int(k)
a="0"+a
l=[int(i) for i in a]
dp=[1,0,-1]
s=0
for i,j in enumerate(l):
p=dp[0]*10
q=dp[1]*10
r=dp[2]*10
s=s*10+j
tmp=[qq]*2
for m in range(9,-1,-1):
pm=p+m
if q!=-10:qm=q+m
else: qm=qq+m
if pm>s and cnt(pm,k) and abs(tmp[0]-s)>abs(pm-s): tmp[0]=pm
if qm>s and cnt(qm,k) and abs(tmp[1]-s)>abs(qm-s): tmp[1]=qm
if abs(tmp[0]-s)<abs(tmp[1]-s): dp[0]=tmp[0]
else: dp[0]=tmp[1]
if dp[1]!=-1:
if cnt(q+j,k): dp[1]=q+j
else: dp[1]=-1
tmp=[qq]*2
for m in range(10):
rm=r+m
if q!=-10:qm=q+m
else: qm=qq+m
if rm<s and cnt(rm,k) and abs(tmp[0]-s)>abs(rm-s): tmp[0]=rm
if qm<s and cnt(qm,k) and abs(tmp[1]-s)>abs(qm-s): tmp[1]=qm
if abs(tmp[0]-s)<abs(tmp[1]-s): dp[2]=tmp[0]
else: dp[2]=tmp[1]
a=int(a)
ans=[abs(i-a) for i in dp if i!=-1 ]
print(min(ans))
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
long long dp[18][3];
bool lg[10],nn[10],sm[10];
int chk(long long x) {
int cv=0; bool cc[10];
rep(i,10) cc[i]=0;
while (x>0) {
if(cc[x%10]==0) {cc[x%10]=1; cv++;}
x/=10;
}
return cv;
}
int main(){
long long mmm=2e15+5;;
char s[20];
int k;
scanf("%s %d",s,&k);
long n=strlen(s);
rep(i,18) dp[i][2]=mmm;
dp[0][2]=0;
for (long i=0l;i<n;i++) {
long long t=s[i]-'0';
dp[i+1][1]=dp[i][1]*10+t;
rep(j,10) {
long long smp=dp[i][0]*10+(j*1ll), tmp=dp[i][1]*10+(j*1ll), lmp=dp[i][2]*10+(j*1ll);
if (tmp<dp[i+1][1] && chk(tmp)<=k) dp[i+1][0] = max(dp[i+1][0],tmp);
if (smp<dp[i+1][1] && chk(smp)<=k) dp[i+1][0] = max(dp[i+1][0],smp);
if (tmp>dp[i+1][1] && chk(tmp)<=k) dp[i+1][2] = min(dp[i+1][2],tmp);
if (lmp>dp[i+1][1] && chk(lmp)<=k) dp[i+1][2] = min(dp[i+1][2],lmp);
}
}
if (chk(dp[n][1])<=k) printf("0\n");
else printf("%lld\n",((dp[n][1]-dp[n][0])<(dp[n][2]-dp[n][1]))?dp[n][1]-dp[n][0]:dp[n][2]-dp[n][1]);
return 0;
}
Python:
桁DP分かりません。何桁目を見ているかはforループの回し方で管理できるし、前々回以前の情報を使うことは無さそうなので1次元配列で、より大きい・同じ・より小さいの3つの数を管理すればいいような気がしました。
色々な処理の都合上で入力の数を1桁増やして先頭には0があることとして進めます。
より大きい数は前回で既に大きい数から作れる数と前回までは同じ数から作れる大きい数とどちらが差分が小さくなるかを調べます。
同じ数は同じ数です。
より小さい数も大きい数と同様に調べます。
最後にどのパターンで作った数が差分が小さいかを比較したものが解になるはずです。多分。
C++:
dp[i][0]にはより小さい、dp[i][1]には同じ大きさ、dp[i][2]にはより大きい数を入れました。作ろうとして条件を満たしているかを確認したり、より差が小さいので更新したりしました。
