sumitb2019_e

E - Colorful Hats 2

• 
• 考えたこと
  • DPかなぁ
  • 最初の人の発言は情報0
  • 最初の人の帽子は赤として、後で3倍すればよい
  • 次に0と答えた人が青
  • 場合の数がそんなに増えるパターンある？？
  • 0,0,0,1と来た時にこの人の色は3通りあるのか
  • 手前の人の色ごとの人数を定義域にしてDPか :

for (a, b, c) in memo:
	if a == x:
		push((a + 1, b, c))
	if b == x:
		push((a, b + 1, c))
	if c == x:
		push((a, b, c + 1))

- ということか。
- しかし、これの効率的な更新方法がわからないな。
- そんなに種類が増えないのだろうか。
- ほとんどの場合1倍で、最大3倍だけどその次は3倍にならないことが確定してるし、あんまり増えないのかな。

• 公式解説
  • あー、なるほど、a,b,cを区別する必要はない、と。
  • この気づきはどのような言葉にすれば良いか？