AtCoder Beginner Contest 156お疲れ様でした！
公式ページ
今回の自分の書いたコードはこちら
結果はA-DまでAC、Eはコンテスト終了後5分でACできました。悔しい
以下簡単に解説します。
問題A
引数にNとKが与えられ、
Kが10以下の場合にはNに100*(10-K)を足し算する問題。
100点問題っていう感じの難易度だったかと思います。
問題B
とある数字がK進法だと何桁かを出力する問題。
while文でぐるぐるまわして桁数をカウントしていけば大丈夫です。
while (n >= k) {
n = n / k;
digit++;
}
問題C
数直線上にN人の人がいて、その全員の移動距離の二乗和を最小にする点と二乗和を求める問題。
まずN人の人の中心となる座標を選定して(整数じゃないといけないのが注意)
あとは単純に二乗和を足し算しました。
N<=100となっていたので、計算量はあんまり気にしなくて大丈夫そうでした。
問題D
二項係数的な問題。以下の性質を使用します。
2^n = {}_n C _0 + {}_n C _1 + {}_n C _2 + ・・・\\
= \sum_{k=0}^n {}_n C _k\\
すると、計算すべきは、
2^n - {}_n C _0 - {}_n C _a - {}_n C _b
となります。
問題E
法則を見つけられたのが終了10分前とかで、実装が間に合いませんでした、、
もともとN個の部屋に1人ずつ入っていて、1回移動が起こると、どこかの部屋が0になることに気づきました。
K個の部屋が0人の場合の組み合わせを計算してみました。すると、
{}_n C _k \times {}_{n-1} C _{n-1-k}
となります。具体的に言うと、n=6,k=2の場合は、
{}_6 C _2 \times {}_5 C _3
です。なので、この和をとって、
\sum_{i=0}^k \left( {}_n C _k \times {}_{n-1} C _{n-1-k} \right)
です。k=1のときとkが大きいときはまた別途考慮が必要でしたが、基本は以上で計算できました。
逆元を最初に計算して計算量の部分はうまく書けたのに、あとちょっとでした。
問題F
手つかずです。なんか入力も多くて難しい気がしたのでスルーしました。笑
レーティングは944→974。
全体的に少し難しかったように思えます。
E問題があともう少し・・・で手が届かず。でも、もう少しでE問題に手が届きそうだったので成長の実感は得られました！
次こそはE問題ACしたい・・・！
あと、TeX使って数式書いてみました。やっぱり美しいですね