| For All Solvers
OMC103 (for beginners)

OMC103(F)

ユーザー解説 by torii

　包除原理パートについて補足をしておきます．（包除原理を知らない方は先に包除原理について調べてみてください．）

　簡単のため，ここでは 77 文字からなる文字列の場合について考えます．i,i+1,i+2i, i+1, i+2 文字目が「ココア」であるような文字列の集合を Si,i+1,i+2S_{i,i+1,i+2} と置きます．このとき，求めるものは ∣S1,2,3∪S2,3,4∪S3,4,5∪S4,5,6∪S5,6,7∣|S_{1,2,3}\cup S_{2,3,4}\cup S_{3,4,5}\cup S_{4,5,6}\cup S_{5,6,7}| です．ここで，包除原理より次が成り立ちます． ∣S1,2,3∪S2,3,4∪…∪S5,6,7∣=+∣S1,2,3∣+∣S2,3,4∣+∣S3,4,5∣+∣S4,5,6∣+∣S5,6,7∣−∣S1,2,3∩S2,3,4∣−∣S1,2,3∩S3,4,5∣−∣S1,2,3∩S4,5,6∣−⋯−∣S4,5,6∩S5,6,7∣+∣S1,2,3∩S2,3,4∩S3,4,5∣+∣S1,2,3∩S2,3,4∩S4,5,6∣+⋯+∣S3,4,5∩S4,5,6∩S5,6,7∣−∣S1,2,3∩S2,3,4∩S3,4,5∩S4,5,6∣−⋯−∣S2,3,4∩S3,4,5∩S4,5,6∩S5,6,7∣+∣S1,2,3∩S2,3,4∩S3,4,5∩S4,5,6∩S5,6,7∣\begin{aligned} &|S_{1,2,3}\cup S_{2,3,4}\cup\ldots\cup S_{5,6,7}|\\ =&+|S_{1,2,3}|+|S_{2,3,4}|+|S_{3,4,5}|+|S_{4,5,6}|+|S_{5,6,7}|\\ &-|S_{1,2,3}\cap S_{2,3,4}|-|S_{1,2,3}\cap S_{3,4,5}|-|S_{1,2,3}\cap S_{4,5,6}|-\cdots-|S_{4,5,6}\cap S_{5,6,7}|\\ &+|S_{1,2,3}\cap S_{2,3,4}\cap S_{3,4,5}|+|S_{1,2,3}\cap S_{2,3,4}\cap S_{4,5,6}|+\cdots+|S_{3,4,5}\cap S_{4,5,6}\cap S_{5,6,7}|\\ &-|S_{1,2,3}\cap S_{2,3,4}\cap S_{3,4,5}\cap S_{4,5,6}|-\cdots-|S_{2,3,4}\cap S_{3,4,5}\cap S_{4,5,6}\cap S_{5,6,7}|\\ &+|S_{1,2,3}\cap S_{2,3,4}\cap S_{3,4,5}\cap S_{4,5,6}\cap S_{5,6,7}| \end{aligned}

　右辺の式の 22 段目の ∣S1,2,3∩S2,3,4∣+⋯+∣S4,5,6∩S5,6,7∣|S_{1,2,3}\cap S_{2,3,4}|+\cdots+|S_{4,5,6}\cap S_{5,6,7}| に注目してみましょう．S1,2,3∩S2,3,4S_{1,2,3}\cap S_{2,3,4} は，1,2,31,2,3 文字目と 2,3,42,3,4 文字目がそれぞれ「ココア」であるようなものの集合ですが，このようなものは存在しないので ∣S1,2,3∩S2,3,4∣=0|S_{1,2,3}\cap S_{2,3,4}|=0 です．同様に考えると，22 段目の項のうち 00 でないものは ∣S1,2,3∩S4,5,6∣,∣S1,2,3∩S5,6,7∣,∣S2,3,4∩S5,6,7∣|S_{1,2,3}\cap S_{4,5,6}|,|S_{1,2,3}\cap S_{5,6,7}|,|S_{2,3,4}\cap S_{5,6,7}| のみです．S1,2,3∩S4,5,6S_{1,2,3}\cap S_{4,5,6} の要素数は 77 文字目を自由に決めることで 212^1 つと求めることができます．残りも同様に考えるとそれぞれ 212^1 つと求めることができます．

　ここで，重要な考察として，22 段目の項に現れる値は 00 か 22 の 22 通りです．実は，任意の段について，登場する値は 00 またはある特定の値 KK（=2(自由に決められる文字の個数)=2^{(自由に決められる文字の個数)}）の高々 22 通りになります（これは，長さが 77 の場合でなくても成り立ちます）．したがって，各段について， KK が何回登場するかがわかれば，登場回数に KK をかけた値が段全体の値になります．

　さらに，ii 段目の式に登場する KK の回数は，ii 個の「ココア」の配置の方法の数に一致します．先ほどの例では，(1,2,3)(1,2,3) と (4,5,6)(4,5,6) に配置する方法，(1,2,3),(5,6,7)(1,2,3),(5,6,7) に配置する方法，(2,3,4),(5,6,7)(2,3,4),(5,6,7) に配置する方法の 33 通りです（(1,2,3)(1,2,3) と (2,3,4)(2,3,4) のように重ねて配置することはできません）．この配置の方法は，公式解説にあるように，「ココア」22 個と「○」11 個の並べ方に帰着することができます．

　整理すると，ii 段目の値 （=ai=a_i とする）は，自由に決められる文字の個数を kk 個，ii 個のココアの配置の方法を mm 通りとすると ai=2kma_i=2^km です．すなわち，

  • 11 段目について，11 個の「ココア」の配置の方法は 5C1{}_{5}\mathrm{C}_{1} 通り，自由に決められる文字の個数が 44 個だから a1=24×5=80a_1=2^4\times5=80 ．
  • 22 段目について，22 個の「ココア」の配置の方法は 3C2{}_{3}\mathrm{C}_{2} 通り，自由に決められる文字の個数が 11 個だから a2=21×3=6a_2=2^1\times3=6 ．
  • 33 段目について，33 個のココアの配置の方法は存在しないから，a3=0a_3=0
  • 4,54,5 段目についても，4,54,5 個のココアの配置の方法は存在しないから，a4,a5=0a_4, a_5=0

　これをもとの式に代入することで，∣S1,2,3∪S2,3,4∪…∪S5,6,7∣=a1−a2+a3−a4+a5=80−6+0−0+0=74|S_{1,2,3}\cup S_{2,3,4}\cup\ldots\cup S_{5,6,7}|=a_1-a_2+a_3-a_4+a_5=80-6+0-0+0=74 と求めることができます．1212 文字からなる文字列の場合も同様に考えることが可能です．