いきなりのAtcoderが出てきましたが、このブログのメインコンテンツ(予定)です。
その内、Atcoderの自体の説明記事を書きます。
注意
・言語はC++で記入します。
・マクロは使っていませんが、
#include<bits/stdc++.h>
using namespace std; この二つだけは書いています。
・説明雑で、ソース汚いです(コメントアウトされたデバッグ出力も残っています)。
A – 複数形
入力の末尾にsを付ける問題。
言語によって様々かと思いますが、C++は“+”演算子で文字列の結合ができます。
入力の文字列に”+”で”s”を結合し、出力すればOKです。
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
cout<<s+"s"<<endl;
}
B – カキ
12個の文字列の中から”r”が含まれている文字列の数を出力する問題。
C++はfind関数を使うことで、文字の探索ができるため、それでOKです。
find関数は、探索文字が存在する場合は最初の出現位置が、存在しない場合はstring::nposが返ってきます。そのため、string::nposではない個数を数えることで”r”が含まれる文字列の個数が分かります。
#include<bits/stdc++.h>
using namespace std;
int main(){
int ans=0;
for(int i=0;i<12;i++){
string s;
cin>>s;
//cout<<s.find('r')<<endl;
if(s.find('r')!=string::npos){
ans++;
}
}
cout<<ans<<endl;
}
C – Brute-force Attack
‘a’,’b’,’c’から作れる、長さNの文字列全てを辞書順で出力する問題。
N桁3進数を考えれば上手くいきます。(3進数の0を’a’,1を’b’,2を’c’みたいに置き換えて考える)
Nが最大の8のときでも、3^8=6561通りしかないので、時間的な余裕はかなりあります。
具体的には、
i=0～3^N-1回のforを回す
iを3進数に直す。
3進数の0～2をそれぞれ’a’,’b’,’c’に置き換えて出力する。
辞書順に出力という条件があるため、そこにだけ注意です。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
cin>>N;
for(int i=0;i<pow(3,N);i++){
int n=i;
int c=N;
string s="";
while(c--){
s=(char)('a'+n%3)+s;
n/=3;
}
cout<<s<<endl;
}
}
D – 1
1～Nの数字を書いたとき、’1’は何回書くことになるか。
愚直に考えれば、各数字に1が幾つ含まれているか調べる方法かと思います。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
cin>>N;
int ans=0;
for(int i=1;i<=N;i++){
int n=i;
while(n!=0){
if(n%10==1) ans++;
n/=10;
}
}
cout<<ans<<endl;
}
このコードはO(NlogN(底=10))になるため、N=10^9の時は計算量が9*10^9になってTLEします。
部分点は満たしているため20点解法となります。
※満点を取るためには？
桁DPします。桁DPの細かいやり方は調べてください。
dp[上位i桁目][好きな数字が置けるか][‘1’の個数]
として、DPテーブルを更新していきます。
O(logN(底=10))になるため(正確には定数倍*400がある)、余裕をもってACがとれます。
#include<bits/stdc++.h>
using namespace std;
int main(){
string N;
cin>>N;
int dp[20][2][20]={{{0}}};
dp[0][0][0]=1;
for(int i=0;i<(int)N.size();i++){
int n=N[i]-'0';
for(int j=0;j<2;j++){
for(int k=0;k<20;k++){
int nx=9;
if(j==0) nx=n;
for(int l=0;l<=nx;l++){
int jx=0;
int kx=0;
if(j==1||l<n) jx=1;
if(l==1) kx=1;
dp[i+1][jx][kx+k]+=dp[i][j][k];
}
}
}
//cout<<dp[i+1][0][0]<<","<<dp[i+1][0][1]<<"+"<<dp[i+1][1][0]<<","<<dp[i+1][1][1]<<endl;
}
int ans=0;
for(int i=0;i<20;i++){
//cout<<dp[N.size()][0][i]<<","<<dp[N.size()][1][i]<<endl;
ans+=(dp[N.size()][0][i]+dp[N.size()][1][i])*i;
}
cout<<ans<<endl;
}
おわりの一言
桁DP、とても苦手です。
キレイに書ける方、毎回すごいなって思います。
コメント