ABC 007

abc007.contest.atcoder.jp

A問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int n;
    cin >> n;
    cout << n-1 << endl;
}

Submission #1025099 - AtCoder Beginner Contest 007 | AtCoder

B問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    string A;
    cin >> A;
    if(A == "a") cout << -1 << endl;
    else cout << "a" << endl;
}

Submission #1025101 - AtCoder Beginner Contest 007 | AtCoder

C問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
typedef pair<int, int> P;
 
char c[51][51];
int v[51][51];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int main(void) {
    int R, C, sx, sy, gx, gy;
    cin >> R >> C >> sy >> sx >> gy >> gx;
 
    REP(i, R) {
        REP(j, C) {
            cin >> c[i][j];
            v[i][j] = -1;
        }
    }
 
    sx--; sy--; gy--; gx--;
 
    queue<P> que;
    que.push(P(sy, sx));
    v[sy][sx] = 0;
    while(true) {
        P p = que.front(); que.pop();
        int y = p.first;
        int x = p.second;
        int s = v[y][x];
        if(x == gx && y == gy) {
            cout << s << endl;
            return 0;
        }
        REP(i, 4) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(nx < 0 || nx >= C || ny < 0 || ny >= R
                || v[ny][nx] != -1 || c[ny][nx] == '#') continue;
            que.push(P(ny, nx));
            v[ny][nx] = s+1;
        }
    }
}

Submission #1025116 - AtCoder Beginner Contest 007 | AtCoder

D問題

  • [A, B]に含まれる禁止された数（4または9が含まれる数）の個数を数え上げる
  • [0, A]に含まれる禁止された数を求める関数f(A)を作ればf(B)-f(A-1)が答え
  • f(A)の作り方を考えるために例としてA=3456の場合を考える
  • A=3256のときは、A=2999までの禁止された数とA=456までの禁止された数を数えればよい。
  • このように、同じ桁数の数についてのカウントと、違う桁数の数についてのカウントを分けて再帰的に数えていく。
  • A=2999までのときは0〜999、1000〜1999、2000〜2999にそれぞれ 1000 - 8^3個の禁止された数がある
  • A=456までのときは最上位が禁止された数なのでA=399までの禁止された数の個数と400〜456の数の個数の和が禁止された数の個数である。
  • したがって、最上位の数が4 or 9のときとそれ以外のときで再帰するかどうかが変わる
  • 「同じ桁数の数についてのカウント」で最上位の桁が4 or 9の数は全て禁止された数になるのでカウント時に8のべき乗を引かなくて良い。それを表すために最上位の桁に応じた引く回数を配列cntに入れておく。
#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define RREP(i,n) for(int i=(int)(n); i>=0; --i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int cnt[] = {0, 1, 2, 3, 4, 4, 5, 6, 7, 8};
 
ll f(ll n) {
    if(n == 0) return 0;
 
    ll size = 1;
    ll ok = 1;
    while(n/size >= 10) {
        size *= 10;
        ok *= 8;
    }
    ll msd = n / size;
 
    ll ret = size * msd - ok * cnt[msd];
 
    ll rem_digit = n - msd * size;
 
    if(msd == 4 || msd == 9) {
        return ret + (rem_digit + 1);
    } else {
        return ret + f(rem_digit);
    }
}
 
 
int main(void) {
    ll A, B;
    cin >> A >> B;
    cout << f(B) - f(A-1) << endl;
}

Submission #1025963 - AtCoder Beginner Contest 007 | AtCoder