基本情報受かった

f:id:fushime2:20161119201523j:plain

午前午後共に合格ラインぎりぎりだった。

勉強に使ったのは基本情報技術者試験ドットコムというサイトで、午前の過去問の一問一答を 3 年分埋めたりした。安定させるためにもう少しやるべきだったと思う。

午後はアルゴリズムが 1 問ミスで C 言語の問題は時間が無くて適当に選んだけどなんとかなったらしい。よかったですね。

nCrについてのメモ

n 個から r 個を選ぶ組み合わせは nCr = n! / (k! * (n-r)!) と書ける。ただ、mod p(pは素数) で計算するときは、分母にある「階乗の逆元」を求めるのがやや面倒である。

この逆元はフェルマーの小定理で求められる。説明を省略すると、a は p で割り切れないとき、a の逆元は a ^ (p-2) となる。

n = (H+W-2), r = (H-1), p = 10 ^ 9 + 7 としたときはこんな感じ(atcoderの問題)。factとその逆元invfを計算すると、nCr = fact[n] * invf[r] * invf[n-r] で求められる。

C: 経路 - AtCoder Beginner Contest 034 | AtCoder

#include <iostream>
using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;
int w, h;
ll f[200010] = {0}; // f(n) = (n!) % mod

// 繰り返し二乗法 O(log n)
ll mod_pow(ll x, ll n){
    ll res = 1LL;
    while(n > 0){
        if(n & 1) res = res * x % mod;
        x = x*x % mod;
        n >>= 1;
    }
    return res;
}

ll mod_inv(ll x){
    return mod_pow(x, mod-2) % mod;
}

// nCr % mod
ll comb(int n, int r){
    return (((f[n] * mod_inv(f[r])) % mod) * mod_inv(f[n-r])) % mod;
}

int main() {
    cin >> w >> h;

    // O(w+h) で階乗テーブルをつくる
    f[0] = f[1] = 1;
    for(int i=2; i<=w+h-2; ++i) f[i] = (i * f[i-1]) % mod;
    ll res = comb(h+w-2, h-1);
    cout << res << endl;
    return 0;
}

python だと標準ライブラリを駆使してこう http://abc034.contest.atcoder.jp/submissions/978322

オーバーフローには気を付けよう!(注意喚起)

// 追記

アイカツが終わってしまった

2013 年の終わり頃(二期のそらちゃんが登場したあたり)から視聴を始めた。実はそれより以前にさくらちゃんの登場回(26 話)やトライスター回(35, 36 話)など部分的に見ていた話もあるが、夕方に放送しているアニメとして眺めていただけだった。何も知らない状態でトライスター回を見ていると「こいつ脱走して何やってんだ」と思っていた覚えがある。

続きを読む