おはようございます。しほみんです。
ずっと更新してなかったABC156について、振り返ります。前回のリベンジができたので良かったなあって感じです。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは650前後の茶色です。まずは750目指します。
＜Atcoderでのスタンス＞
・アルゴリズムについては未学習。問題を通じて学習中。
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約35回参加、8か月。
・目標はABCのD問題までをちゃんと解けるようにすること。さらに短時間であればなおよい。レートは緑を安定的にとる。
今回は90分でABCDの4完でした（D問題で2回ミス）。パフォーマンスも1020で久々の緑で、レートも652→695とそのまま戻りました。まあちょっと出かけていたのでそのせいで時間はかかっていますが、悪くはないです。
D問題は二項係数を求める問題で過去にやらかした問題です。復習したおかげできちんと解けるようになって成長を感じます。
今日はE問題まで復習して終わりにしようと思います。E問題はさらにD問題の延長線上で非常に勉強になったのでE問題まで解答します。
ここから解説します。
A問題
Butcoderでは内部レートと表示レートがあります。
表示レートは参加回数が10回以上のとき内部レートと一致、10回未満なら、K回参加すると100×(10-K)だけ引かれて表示します。
参加回数と表示レートから内部レートを求めてください。
単純なif文です。10回以上と、それ以外で場合分けです。10回未満のとき引かれているので、コード上では足し合わせることに注意します。
（構成例）
if(N >= 10)
Console.WriteLine(R);
else
Console.WriteLine(R+(10-N)*100);
B問題
NをK進数で表したとき何桁か求めよ。
K進数なのでm桁の最小値はKの（m-1)乗を示し、最大値はKのm乗-1を示します。
10進数なら1桁は0-9です。2桁は10-99です。
ということはKで何回割って、0にするかを考えればよいです。こういう時はwhile文で終わるまでやることをかんがえるとよいです。ループした回数は別で数えます。
（構成例）
count = 0;
while(n != 0)
{
n /= k;
count++;
}
Console.WriteLine(count);
C問題
N人住んでいます。i番目の人が住んでいる町の座標はXiです。
集会は任意の場所座標Pで開けて、このときそれぞれの人は(P -Xi)の2乗の体力を使います。
体力が最小になるときを求めなさい。
座標候補はたかだか100通りしかありません。そして人数も100人しかいないので、100×100ですべて消費する体力を計算すればよいです。
あとは随時最小値を更新していけばよいです。
(構成例）
int ans = 100000000; //大きい数を入れておく
for(int i = 1;i <= 100;i++)
{
int sum = 0;
for(int j = 0; j< n; j++)
sum += (j - X[j])*(j - X[j]);
ans = Math.Min(ans, sum);
}
Console.WriteLine(ans);
D問題
n種類の花が1本ずつあります。しかし、作る人はa,bの数字が嫌いで、a,b本の束の花は作れません。ここで作れる花は何通りありますか？
少し考察します。
n種類から1本選んで束を作る場合、nC1です。
n種類から2本選んで束を作る場合、nC2です。
ということはa,bを考慮しないで作る場合は
nC1+nC2+nC3+......+nCn-1+nCnです。
この和は一般的に2のn乗-1で知られています。
よって求める数は2のn乗-1- nCa-nCbです。
あとはmod(10の9乗+7)に気を付けて計算します。
2のn乗は繰り返し二乗法で求められます。BigIntegerでも一応求まります。
nCaは逆元を使ってうまく求めましょう。
二つともmodの位置に気を付けて計算します。
具体的なことはコードを見てください。
E問題
n個の部屋があってそれぞれ1人ずついます。1人が違う部屋に動くことをｋ回行いました。このとき部屋の人数として考えられる場合はいくつでしょう。
ぱっと見とてもとっつきづらい問題です。ですがk回は最低2回あることから誰もいない部屋というのは任意の回数生成できます。
この証明自体は厄介ですが、なんか何回か実験してみて行けそうだなって感じることが重要だと思います。
ということは空き部屋の数をm個とすると
空き部屋の組み合わせがnCm、空き部屋じゃないところの人の入り方はn-mHmです。（n-m人を重複を許してm個の部屋に入れるという重複数列）
ということでnCm×n-mHm = nCm×n-1Cn-m-1です。
あとはm = 0からMin(n-1,k)までの分計算して求めます。
でこの二項係数の計算ですが、nまでの数をあらかじめ計算しておいて、あとは引き出せばo(1)のオーダーで済みます。
この処理は結構有名みたいです。
それぞれ、modの世界において、n!の値、n!で割ったときの値、nの逆元が機能的に出てきます。これを使って数列化して記録しておいて、引き出せばよいのです。
以下がコード例です。
最後に...
今回で二項係数についてはばっちりできたなと感じます。あとはこれを使った問題を落とさないようにしたいところです。ではでは。
