Home / Python /

京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200）をPythonで解く

投稿日：　

Atcoder Python

B!
Daniel AgreloによるPixabay(https://pixabay.com/)からの画像

こんにちは, Shinoryoです.

今回は京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200）を, Pythonで解いてみた結果を書き連ねていこうと思います.

KYOCERA Programming Contest 2021（AtCoder Beginner Contest 200） - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A - Century

求めるのは, $N / 100$を小数点以下切り上げた値になります. 世紀の定義そのままですね.

B - 200th ABC-200

問題文に書かれていることをそのまま実行すればよいです. 「整数$N$を, $N$の後ろに文字列として $200$を付け加えた整数に置き換える」というのは,

  1. $N$をstr型にして
  2. 後ろに「200」(文字列)を付け加えて
  3. int型にする

という操作によって実行できます.

C - Ringo's Favorite Numbers 2

数列$A$から2つを取り出す全ての組み合わせを全通り探索して, $A_i - A_j$が$200$の倍数であるかどうかを確かめてしまうと, 時間計算量が$O(N^2)$となりTLE.

さて, $A_i - A_j$が$200$の倍数であるならば, $A_i$を$200$で割った余りと$A_j$を$200$で割った余りが等しいということを利用します. $A$の配列全てを$200$で割った余りにしておき, $A$に含まれている$0$の個数, $1$の個数, ……を順に確かめていきます. そして, $A$に含まれている$i$の項目から2個を選ぶ場合の数を加えていきます.

ここでは, 組み合わせの場合の数を計算するのにscipy.special.combを使用しています. int型を貫くために, 第3引数で「exact=True」とします(「exact=True」だとint型, 「exact=False」(デフォルト)だとfloat型を返します).

D - Happy Birthday! 2

鳩の巣原理(Pigeonhole principle)より, $201$個以上の$B$または$C$の候補を用意すれば, $200$で割った余り(の合計)が同じになるものが2つ以上存在することになります. 数列$A$の長さ$N$に対して, $B$または$C$の候補は$(2^N - 1)$個あるので, 数列$A$は$8$個分だけ調べれば十分となります($2^7 - 1 = 127$, $2^8 - 1 = 255$).

$N = \mathrm{min}(N, 8)$として, $1 \leq i < 2^{N - 1}$を満たす$i$に対して, それを2進数にした表現を利用します. このような全探索方法(bit全探索)に関しては, 「AtCoder Beginner Contest 197（Sponsored by Panasonic）をPythonで解く」の「C - ORXOR」でも行っています.

AtCoder Beginner Contest 197（Sponsored by Panasonic）をPythonで解く

こんにちは, Shinoryoです. 今回は AtCoder Beginner Contest 197（Sponsored by Panasonic） を, Pythonで解いてみた結果を書き連ねていこうと思います. AtCoder Beginner Contest ...

$B$の候補に関して, $200$で割った余りが一致すれば, それを出力します. 一致するものがあるかどうかは, 「余りが$\mathrm{mod}$になる$B$の候補」を$\mathrm{bcand\_record}[\mathrm{mod}]$に記録し, $\mathrm{mod\_count}[\mathrm{mod}]$のフラグを$+1$することによって, $\mathrm{mod\_count}[\mathrm{mod}]$が$2$になるかどうかで確かめます. 余りが一致するもう1つの$B$の候補は$\mathrm{bcand\_record}[\mathrm{mod}]$に記録されているので, それを再現すればよいです.

最後の出力では, .joinでいい感じにつなぎます.

E以降

E以降は私の能力不足故に省略いたします.

参考にしたサイト等