AtCoder Beginner Contest 156（ABC156）

数学回で冷えなかったのでよし？

+1！w
Bondo416さんのAtCoder Beginner Contest 156での成績：1128位
パフォーマンス：1289相当
レーティング：1276→1277 (+1) :)#AtCoder https://t.co/gUa5LdviOB
— ボンド@競プロ (@bond_cmprog) 2020年2月22日

A - Beginner

最近のA読解辛めな気がする
ぱっと読めなかった
10回未満なら内部レーティングから引いたものを足してあげる
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, R;
    cin >> N >> R;
    if(N >= 10) cout << R << endl;
    else cout << R + 100 * (10 - N) << endl;
}

B - Digits

何回その数で割れるかでおっけー
$k = 10$ なら10進数の桁和求めるときとおんなじだね
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    ll ans = 0;
    while(N > 0){
        ans++;
        N /= K;
    }
    cout << ans << endl;
}

C - Rally

ぱっと見これは平均値！となったけどよく見ると答えが整数座標で制約も小さいので全探索
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> X(N);
    REP(i,N) cin >> X[i];
    ll ans = LINF;
    for(int i=-100;i<=100;i++){
        ll tmp = 0;
        REP(j,N) tmp += (X[j] - i) * (X[j] - i);
        chmin(ans, tmp);
    }
    cout << ans << endl;
}

やることは単純で $\sum_{k=1}^{n} {} _n C _k - ({} _n C _a + {} _n C _b)$ を求める
ただし、nが大きいのでちょっと工夫する必要がある
$\sum_{k=0}^{n} {} _n C _k = 2^{n}$ で、 $2^{n}$ は $\mathcal{O}(logn)$ 、 ${} _n C _a ,　{} _n C _b$ はそれぞれ $\mathcal{O}(a),　\mathcal{O}(b)$ で求められるので
$2^{n} - 1 - {} _n C _a - {} _n C _b$ を求めればいい
提出コード

//modint省略
mint kai(ll x, ll y){
    mint res = 1;
    for(ll i=0;i<min(x,y);i++) res *= (x - i);
    return res;
}
mint nCk(ll n, ll k){
    if(n < k) return 0;
    return kai(n, k) * modpow(kai(k, k), MOD-2);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, a, b;
    cin >> n >> a >> b;
    mint ans = modpow(mint(2), n);
    ans -= 1;

    ans -= nCk(n, a);
    ans -= nCk(n, b);
    cout << ans << endl;
}

E - Roaming

コンテスト中解けなかった、数学回辛い
考えたことは、 $k \geq n-1$ なら重複組合せがそのまま使える
サンプル1とサンプル2はそれだけで通るんだけどサンプル3が合わず終了
重複組合せ自体は間違っていなくて、0になる部屋が何個あるかと、残りを重複組合せしたものの積を加算していくと答えになる
0の部屋が作れる数は $min(n-1, k)$ なので各場合の数の総和が答え
言われるとたしかにな〜ってなるけどここまでたどり着けないなあ
提出コード

//modint省略
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, k;
    cin >> n >> k;
    mint ans = 0;
    for(int i=min(n-1,k);i>=0;i--) ans += bc.com(n-1,i) * bc.com(n, n-i);
    cout << ans << endl;
}

F - Modularness

コンテスト中ちらっと見たんだけど頭が壊れたのでまた今度…

おわりに

数学回冷えがちなので冷えなかっただけセーフ（ほんまか？）
Eは作れる部屋の数限定されるよなーとか考えてたのに0の部屋の数思いつかなかったのは反省かなあ
数え上げ力上がれば青だいぶ近づくから特訓したい…

接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。