AtCoder Beginner Contest 042

[TakefumiYamamura]

C - こだわり者いろはちゃん / Iroha's Obsession

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

配点 : 300 点

問題文

いろはちゃんはこだわりもので、嫌いな数字が K 個あり、それぞれ D1,D2,…,DK です。

いろはちゃんはお店でお買い物をしていて、 N 円の品物を買おうとしています。 もちろん、この品物は N 円以上のお金を支払えば買うことができます。 しかし、先ほど述べたようにいろはちゃんは強いこだわりがあるので、自分がお店に支払う金額の 10 進表記にいろはちゃんの嫌いな数字が出現しないような最も少ない金額を支払おうとします。

いろはちゃんが支払う金額を求めてください。

制約

1≦N<10000 1≦K<10 0≦D1<D2<…<DK≦9 {D1,D2,…,DK}≠{1,2,3,4,5,6,7,8,9}

note

Constraint is not so hard, so I can use Brute-force search

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

int main(){
    int n, k;
    cin >> n >> k;
    int d[10];
    for (int i = 0; i < k; ++i)
    {
        cin >> d[i];
    }
    while(true){
        int tmp;
        tmp = n;
        bool flag = true;
        while(tmp != 0){
            int num;
            num = tmp % 10;
            tmp -= num;
            tmp /= 10;
            for (int i = 0; i < k; ++i)
            {
                if(d[i] == num){
                    flag = false;
                }       
            }
        }
        if(flag){
            cout << n << endl;
            return 0;
        }
        n++;
    }

}

[TakefumiYamamura]

D - いろはちゃんとマス目 / Iroha and a Grid

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

配点 : 400 点

問題文

縦 H マス、横 W マスのマス目があります。 いろはちゃんは、今一番左上のマス目にいます。 そして、右か下に1マス移動することを繰り返し、一番右下のマス目へと移動します。 ただし、下から A 個以内、かつ左から B 個以内のマス目へは移動することは出来ません。

移動する方法は何通りあるか求めてください。

なお、答えは非常に大きくなることがあるので、答えは 109+7 で割ったあまりを出力してください。

制約

1≦H,W≦100,000 1≦A<H 1≦B<W

note

10e9+7が素数だからフェルマーの小定理を利用した逆元をdpで求める数学の問題。 数学力の無い俺は死ぬ。 http://hos.ac/slides/20130319_enumeration.pdf ☝️神スライド

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

const ll MOD = 1e9+7;

ll factorial[200003];
ll revfac[200003];

ll con(ll a, ll b){
    return factorial[a] * revfac[b] % MOD * revfac[a-b] % MOD; 
}

ll pow(ll a, ll e){
    ll tmp = 1;
    while(e > 0){
        if( e & 1ll){
            tmp = tmp * a % MOD ;
        }
        a = a * a % MOD;
        e >>= 1; 
    }
    return tmp;
}

void set_factorial(ll n){
    factorial[0] = 1;
    revfac[0] = 1; 
    for (int i = 1; i <= n; ++i)
    {
        factorial[i] = factorial[i-1] * i % MOD;
        revfac[i] = pow(factorial[i], MOD - 2) % MOD;
    }
}

int main(){
    ll h, w, a, b;
    cin >> h >> w >> a >> b;

    set_factorial(h+w);
    ll ans = 0;
    for (int i = 0; i <= h-a-1; ++i)
    {
        ans += con(b+i-1, i) * con(w-b+h-i-2, w-b-1) % MOD;
    }
    cout << ans % MOD << endl;
}

[TakefumiYamamura]

なんで？ a-1 ≡ a^(p-2) (mod p)