京セラプログラミングコンテスト2021（AtCoder Beginner Contest200)に参加しました。
結果
A,B,C,D問題の4問正解でパフォーマンスが1560でした。 D問題が結構難しかったこともありレーティングがそこそこ上がった。やっと緑に帰ってこれた。
D問題が結構難しかった気がする。一応正解したけど嘘解法だと思ってる。 E問題はもう少し数学ができれば解けそうな気がした。
A - Century
何世紀か答えるだけなので、基本的に100で割った値を出せばいい。例外として100で割り切れる場合は別途対応が必要になる。
例えば2000年は21世紀じゃなくて20世紀。
B - 200th ABC-200
問題文にある通りの処理を行えばいい。
後ろに文字列として200を付け加えるってのは1000倍して200を足せば良い。
注意点は答えが答え用に用意した変数の型の値域に収まるかどうかを気にするくらいかなあ。
C - Ringo's Favorite Numbers 2
愚直に二重ループでの組み合わせを全通り試そうとすると
で
くらいになりそうだからTLEになる。
求めたいのはになる
の組み合わせだけど、式変形すると
となる。つまり、200で割った余りを計算して0~199がそれぞれ何個あるのか、各値で何通りの組合せが作成できるのかを数えれば良くなる。
入力を受け取ってそれぞれを200で割った余りを計算して、0～199が何個ずつあるのかをもとに組み合わせ数()を計算して合計していく。
D - Happy Birthday! 2
要するに数列Aの各要素を、数列Bに加える・数列Cに加える・数列Bにも数列Cにも加えないのどれかとして、問題文の条件を満たせる数列B,Cを作れば良い。
また、数列の和を200で割った余りが等しいとあるのでは200で割った余りと置き換えられる。
正しい解き方はわからないけど、N桁を3進数表現で表して桁目が0なら数列Bにも数列Cにも加えない、1なら数列Bに加える、2なら数列Cに加えるとしてbit全探索っぽく処理した。
ただ、そうすると計算量は最大で
になって余裕でTLEになるので、
か
の小さい方をループ回数の上限として処理してみた。
一応それでACしたから良かった。
解説を読んでみると回確認するだけで十分っぽい。鳩ノ巣原理って聞いたことなかったや。理屈は理解できるけど。
E - Patisserie ABC 2
難しかった。Nを適当に選んで手元で各パラメータの和を計算してどの値が何個あるのかを計算してみたら、なんか法則があるっぽい変化の仕方をしてた。
パラメータの和がxの時y個あるってのがわかればK番目はパラメータの和がどの値のときかは求められるから、その中から数えれば良さそうな気がしてる。
肝心の入力のNに対してパラメータの和がいくつの物が何個というのが求められなかったのでだめだったけど。
