最近atcoderをやっていることをツイートしたら, めちゃめちゃ頭のいいFさんにお声がけいただいて,つよつよエンジニア学生Aくんも誘って, 競プロの勉強会をすることにしました。

僕はそんなに頭がよくなく理解が遅いかつ実装が遅いのでなかなか恐れ多い勉強会ですが, 頑張って食らいついていこうと思っております。

僕はC++を使っていて, FさんとAくんはPythonを使ってます。
Fさんは来週からC++使うそうです。あっという間に抜かされそうです。

今週はatcoder150を解きました。

D - Semi Common Multiple

長さ N の偶数からなる正の整数列 A = a_1, a_2, ..., a_N と、整数 M が与えられます。 任意の k ( 1 ≤ k ≤ N) に対して以下の条件を満たす正の整数 X を A の「半公倍数」と定義します。 X = a_k * (p + 0.5) を満たす負でない整数 p が存在する。 1 以上 M 以下の整数のうちの A の半公倍数の個数を求めてください。

半公倍数の理解に時間がかかった。Aの要素が2で割れる回数が全て等しくなければならないというところがミソ。

E - Change a Little Bit

0, 1からなる長さ N の異なる 2 つの数列 S , T に対し、関数 f (S , T) を以下のように定めます。 S に対し以下の操作を繰り返して T と等しくすることを考える。このとき行う操作のコストの和として考えられる最小の値が f(S , T) である。 S_i を ( 0 から 1 、もしくは 1 から 0 に) 変更する。この操作のコストは、変更の直前に S_j ≠ T_j ( 1 ≤j ≤N) であったような整数 j の個数を D として、 D * C_i である。 0 , 1 からなる長さ N の異なる 2 つの数列の組 (S , T) は 2^N × ( 2^N − 1) 通り考えられます。これらすべてに対する f( S , T) の和を 10^9 + 7 で割った余りを計算してください。

各コストの係数を保持するという変な解き方をしてしまったが, Σの計算を進めると簡単になったらしい。。。

まとめ

メモ程度に残していこうと思います。

来週は蟻本 中級編をやっていこうと思ってます。