2020-11-01 包除原理(abc178_c) 競技プログラミング(AtCoder) 概要 問題 解説図 答えの式 1.初期イメージ 2.加算:全パターン(10^n)。 3.減算:0を含まないパターン(9^n) 4.減算:1を含まないパターン(9^n) 5.加算:0と1を含まないパターン(8^n) 6.結果 概要 知識不足で包除原理の解説が難しかったので、図で解説する。 問題 atcoder.jp 解説図 答えの式 1.初期イメージ ベースはこれ。 2.加算:全パターン(10^n)。 全パターンを+1。 3.減算:0を含まないパターン(9^n) 「0を含む」以外のパターンを-1。 4.減算:1を含まないパターン(9^n) 「1を含む」以外のパターンを-1。 5.加算:0と1を含まないパターン(8^n) 「0を含む」「1を含む」以外のパターンを+1。 6.結果 「0を含む」かつ「1を含む」パターンだけ算出できた。 (そのほかの部分は0なので除外できている)