キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)をPythonで解く

こんにちは, Shinoryoです.

今回はキャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)を, Pythonで解いてみた結果を書き連ねていこうと思います.

Caddi Programming Contest 2021(AtCoder Beginner Contest 193) - AtCoder

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

A - Discount

$\left( A - B \right) / A$の$100$倍を計算します.

B - Play Snuke

高橋くんがスヌケマシンを買うことができる条件は, $X_i > A_i$となります. そのような店$i$における販売価格$P_i$の最小値を求めればよいです. $P_i$の最大値は$10^9$なので, 答えの初期値を$10^9 + 1$にしてそれが更新されなかった場合は$-1$にするようにしています.

C - Unexpressed

$N$までの自然数のうち, $2$以上の整数$a$, $b$を用いて$a^b$と表すことができないものの数を求める問題です. $a^b$と表すことができるものの数を求める方が楽そうだということは容易に想像できるでしょう.

全ての$2 \leq a \leq N$に関して探索するコードがこちらです. 各$a$に対して$b$を$2$から順に調べていき, $a^b \leq N$になるまで続けます. それを, $2 \leq a \leq N$に関してループします. $N \leq 10^{10}$なので当然TLEです.

そこで, $a$の範囲は実際には$2 \leq a \leq \sqrt{N}$に絞れることを利用します. 実際, $b \geq 2$なので, $a > \sqrt{N}$に対しては必ず$a^b > N$となってしまいます.

$\sqrt{N} \leq 10^5$なので, これだけでかなり時間計算量を減らすことができますね. 時間内に思いつきたかった.

D - Poker

残っているカードを調べて全探索すればええやんけ！ ってやると当然TLEです. 配列card_remainに, $1$から$9$までのカードがそれぞれ何枚残っているかを格納し, それを配列card_remain_cardに実際のカードを模して表現(card_remainが[1,1,2,1,1,2,1,1,2]なら, card_remain_cardには[1,2,3,3,4,5,6,6,7,8,9,9]が入ります)し, card_remain_cardから$2$つを選ぶ場合をitertools.permutationsで書きだします.

そこで, 頭を使って考えることにします.

まず, 残っているカードは$\left( 9K - 8 \right)$枚になるはずです. これを高橋くんと青木くんに配る場合の数は, $\left( 9K - 8 \right) \left( 9K - 9 \right)$となります.

残っている$i$のカードを$C_i$($1 \leq i \leq 9$)とします. 高橋くんに$x$のカード, 青木くんに$y$のカードを配る場合の数は当然 \begin{align} \left\{ \begin{aligned} & C_x C_y \quad (x \neq y) , \\ & C_x \left( C_x - 1 \right) \quad (x = y) \end{aligned} \right. \end{align} となります. このことを利用すれば, 残ったカードから$2$つを選ぶ場合をitertools.permutationsで書きだすなんてことをしなくてもよいですね.

E以降

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

参考にしたサイト等

• 「解説 - キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)」
  Editorial - Caddi Programming Contest 2021(AtCoder Beginner Contest 193)

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