AtCoder Beginner Contest 178 [ C - Ubiquity ]をPythonで解く。包除原理問題（🟫茶diff、300点）

atcoder.jp

解法

各条件について考えてみる。

• 
  これを満たす数列の個数(ア) = 10^N

• なるが存在する(イ)。
  これを満たす数列の個数 = 10^N - 9^N
  9^Nはを満たす個数

• なるが存在する(ウ)。
  これを満たす数列の個数 = 10^N - 9^N
  9^Nはを満たす個数

abc178_c

問題の答えとしては(オ)を求める。

ここでa, b, c, dを定義する。

a: (ア) = 10^N
b: (イ)以外 = 9^N
c: (ウ)以外 = 9^N
d: (エ) = (イ)(ウ)以外 = 8^N

a - b - c + d が(オ)の数、つまり答えとなる。

なぜ、この式で答えがでるのか。
イ、ウ、エ、オの4グループについて考える。
(イ): a、cに含まれる。 a - c なので0
(ウ): a、bに含まれる。 a - b なので0
(エ): a、b、c、dに含まれる。 a - b, -c + d なので0
(オ): a に含まれる。(イ)、(ウ)、(エ)が0なので(オ)が残る

実装

数学的な解法さえ、わかってしまえば実装はアッサリ。

参考

youtu.be 解法は、この放送のsnukeさんの説明にならっている。

ja.wikipedia.org