AtCoder Beginner Contest 007(ABC007) 解説

A – 植木算
B – 辞書式順序
C – 幅優先探索
D – 禁止された数字

A – 植木算

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

絵や入力例を見れば何となく法則が掴めてくるかと思います。
左端から木を植えると考えると、最初の1本以外は左の木と隣り合うため、木の数-1が答えになります。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin>>n;
    cout<<n-1<<endl;
}

B – 辞書式順序

B - 辞書式順序

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

入力例3より、”a”が辞書順最小ということが分かります。
この問題は、辞書順が小さい文字を何でも1個出力すればいいため、

入力が”a”以外なら”a”を出力
入力が”a”なら-1を出力

でOKです。

#include<bits/stdc++.h>

using namespace std;

int main(){
    string s;
    cin>>s;

    if(s=="a") cout<<"-1"<<endl;
    else cout<<"a"<<endl;
}

C – 幅優先探索

C - 幅優先探索

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

BFS(幅優先探索)のチュートリアル的問題です。
この問題の解き方や組み方が分からない場合は、BFSの勉強をしましょう！

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

蟻本がおススメです。私も、この本でBFSの勉強をしました。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int R,C;
    int sx,sy;
    int gx,gy;

    cin>>R>>C;
    cin>>sy>>sx;
    cin>>gy>>gx;

    string maze[R];
    for(int i=0;i<R;i++){
        cin>>maze[i];
    }

    int ans[R][C];
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            ans[i][j]=INT_MAX;
        }
    }

    queue<int> qx,qy;
    qx.push(sx-1);
    qy.push(sy-1);
    ans[sy-1][sx-1]=0;

    while(!qx.empty()){
        int nx=qx.front();
        int ny=qy.front();
        qx.pop();
        qy.pop();
        int dx[]={0,0,1,-1};
        int dy[]={1,-1,0,0};
        for(int i=0;i<4;i++){
            int xx=nx+dx[i];
            int xy=ny+dy[i];
            int nn=ans[ny][nx];
            int xn=ans[xy][xx];
            if(maze[xy][xx]=='.'&&(xn==INT_MAX||nn+1<xn)){
                ans[xy][xx]=nn+1;
                qx.push(xx);
                qy.push(xy);
            }
        }
    }

   cout<<ans[gy-1][gx-1]<<endl;
}

queueをstack、front()をtop()とすることでDFS(深さ優先探索)となり、こちらでも解けます。
が、実行速度が遅くなってしまいます。
※上記コードのBFS解が8ms、stackに変えたDFS解が25msでした。

問題によってはBFSはACだけど、DFSはTLEになることがあります。
特別な理由がなければqueueを使う方が無難です。

D – 禁止された数字

D - 禁止された数字

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

桁DPのチュートリアル的な問題です。
dp[桁数][4,9が含まれている][絶対にNを越えない]
としてDPテーブルを更新します。

A～Bなので、『絶対にNを下回らない』の条件も必要そうですが、ややこしくなるので
(Bまでの答え)-(A-1までの答え)
と2回求め、DPの計算では意識しないようにしました。

#include<bits/stdc++.h>

using namespace std;

long long solve(long long N){

    long long dp[20][2][2]={{{0}}};

    int keta=0;
    long long n=N;
    while(n!=0){
        keta++;
        n/=10;
    }
    dp[0][0][0]=1;
    for(int i=1;i<=keta;i++){
        long long n=N;
        for(int j=0;j<keta-i;j++){
            n/=10;
        }
        n%=10;
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                int to=n;
                if(k==1) to=9;
                for(int l=0;l<=to;l++){
                    int nxj=0;
                    if(j==1||l==4||l==9) nxj=1;
                    int nxk=0;
                    if(k==1||l!=n) nxk=1;
                    dp[i][nxj][nxk]+=dp[i-1][j][k];
                }
            }
        }
    }
    return dp[keta][1][0]+dp[keta][1][1];
}
int main(){
    long long A,B;
    cin>>A>>B;

    cout<<solve(B)-solve(A-1)<<endl;
}

桁DPを知らないとパット見分からないですが、ほぼ典型のような書き方です。
ポイントとしては以下の2点です。