TakefumiYamamura commented 8 years ago

D - 禁止された数字

時間制限 : 2sec / メモリ制限 : 256MB

問題文たかはし王国の国王であるたかはし君主は数字の 4 と 9 が大嫌いです。それらの数字を国内で目にするだけで気分が悪いので、それらを使ってはいけないという法律を定めました。この法律を破ってしまうと罰せられます。数字が禁止されているので、ある数の10進表現を考えたとき、いずれかの桁に禁止された数字が1つでも含まれている場合、その数を使うことはできません。

今まで使っていた数字を使えなくなったあなたは、うっかり使ってしまって罰せられては困るので、使う可能性がある数の区間 [A,B]={A,A+1,A+2,…,B} に、いくつ禁止された数が含まれているかを確かめることにしました。そのためのプログラムを作ってください。

部分点この問題には2つのデータセットがあり、データセット毎に部分点が設定されている。

1≦A≦B≦10,000 を満たすデータセット 1 に正解した場合は 30 点が与えられる。追加制約のないデータセット 2 に正解した場合は、上記のデータセットとは別に 70 点が与えられる。

note

lets accustomed to use a digit dp 桁dpと配列初期化用のテンプレートの扱いになれるべし

#include <iostream>
#include <vector>
#include <string>
#define ll long long
using namespace std;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

ll digDP(ll n){
    ll dp[20][2][2];
    ll size = 0;
    string s = to_string(n);
    size = s.size();
    //dp[i][j][k] 
    //i桁目まで確定,j:=禁止されている値かどうかのフラグ,k:= n未満が確定しているかどうかのフラグ
    Fill(dp, (ll)0);
    dp[0][0][0] = 1;

    for (int i = 0; i < size; ++i)
    {
        ll digit = s[i] - '0';
        for (int j = 0; j < 2; ++j)
        {
            for (int k = 0; k < 2; ++k)
            {
                for (int d = 0; d < (k ? 10: digit+1); ++d){
                    dp[i+1][j || d == 4 || d == 9][k || d < digit] += dp[i][j][k];
                }
            }
        }
    }
    return dp[size][1][1] + dp[size][1][0];
}

int main(){
    ll a, b;
    cin >> a >> b;
    cout << digDP(b) - digDP(a-1) << endl;

}

TakefumiYamamura commented 8 years ago

C - 幅優先探索

http://abc007.contest.atcoder.jp/tasks/abc007_3

note

普通にキューつかって幅優先するだけ

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

struct Point
{
    int x, y;
};

class Bfs
{
public:
    int r, c;
    Point s, g;
    vector<vector<bool> > map;
    vector<vector<int> > cost;
    Bfs();
    ~Bfs();
    void exec();

};

Bfs::Bfs(){
    cin >> r >> c;
    cin >> s.y >> s.x;
    cin >> g.y >> g.x;
    s.x--;
    s.y--;
    g.y--;
    g.x--;
    map.resize(r);
    cost.resize(r);
    for (int i = 0; i < r; ++i)
    {
        map[i].resize(c);
        cost[i].resize(c);
        string tmp;
        cin >> tmp;
        for (int j = 0; j < c; ++j)
        {
            if(tmp[j] == '#'){
                map[i][j] = false;
            }else{
                map[i][j] = true;
            }
            cost[i][j] = -1;
        }
    }
}

Bfs::~Bfs(){}

void Bfs::exec(){
    queue<Point> q;
    q.push(s);
    cost[s.y][s.x] = 0;
    while(!q.empty()){
        Point tmp = q.front();
        q.pop();
        // cout << "x, y " << tmp.x << " "<< tmp.y << endl; 
        // cout << cost[tmp.y][tmp.x] << endl;
        if(cost[g.y][g.x] != -1){
            cout << cost[g.y][g.x] << endl;
            return;
        }
        if(map[tmp.y+1][tmp.x] && cost[tmp.y+1][tmp.x] == -1){
            Point next = {tmp.x, tmp.y+1};
            q.push(next); 
            cost[tmp.y+1][tmp.x] = cost[tmp.y][tmp.x] + 1;
        }
        if(map[tmp.y][tmp.x+1] && cost[tmp.y][tmp.x+1] == -1){
            Point next = {tmp.x+1, tmp.y};
            q.push(next); 
            cost[tmp.y][tmp.x+1] = cost[tmp.y][tmp.x] + 1;
        }
        if(map[tmp.y-1][tmp.x] && cost[tmp.y-1][tmp.x] == -1){
            Point next = {tmp.x, tmp.y-1};
            q.push(next); 
            cost[tmp.y-1][tmp.x] = cost[tmp.y][tmp.x] + 1;
        }
        if(map[tmp.y][tmp.x-1] && cost[tmp.y][tmp.x-1] == -1){
            Point next = {tmp.x-1, tmp.y};
            q.push(next); 
            cost[tmp.y][tmp.x-1] = cost[tmp.y][tmp.x] + 1;
        }
    }
}

int main(){
    Bfs bfs = Bfs();
    bfs.exec();

}

TakefumiYamamura / programming_contest

AtCoder Beginner Contest 007 #17

D - 禁止された数字

note

C - 幅優先探索

note