なぜ"Colorful Hats 2"に35分も掛けてしまったのか。

Colorful Hats 2三井住友信託銀行プログラミングコンテスト2019のE問題です。本番ではこの問題に35分かかったので、振り返りをします。

f:id:matsu7874:20191201225941p:plain 三井住友信託銀行はどこに競技プログラマ需要があるのでしょうか?気になりますね。

問題概要

a = [A[0:i-1].count(A[i]) for i in range(N)] が与えられるので、そのような A = [(R|G|B) for i in range(N)] として考えられるものの個数を求める問題です。

直感的に満たすべき条件

  • 各数は最大3回までしか出現しない。

サンプルを足す

例示されているサンプルがあまりに自明なので、小さなサンプルを追加します。

9
0 0 1 0 1 2 1 2 2
96

前から順番に割り当てられるものの個数を数えていくと3*2*2*1*2*2*1*2*1 = 96になり、素直にこれを実装するとACします。

n = int(input())
a = list(map(lambda x: int(x)+1, input().split()))
MOD = 1000000007

up = [0] * (n+1)
up[0] = 3
p = 1
for i in a:
    if up[i - 1] < up[i]:
        print(0)
        exit()
    p = (p * (up[i - 1] - up[i]) % MOD)
    up[i] += 1

print(p % MOD)

何が良くなかったのか

では、なぜ私は35分もこの問題に掛けてしまったのでしょうか。

1. 「3色だから3!で*6通り」と考えてしまった

3色を使う数え上げ問題を見て、反射的に3色の対称性から「3色だから3!で*6通り」と考えてしまいました。
この考えは各a[i]に注目して、取れる選択肢の数を掛けていく方法と相性が悪く、1つ目の 0 に注目した時点で RGB の3つから1つ選ぶということが表現されています。

2. 「途中までの状態数を足し算する?」と考えてしまった

012001122みたいな入力に対して、前半の012が3通り作れることと、残った色で後半の001122を8通り作れることは 独立 なので、掛け算で大丈夫です。
残った色の部分で重複しないように調整されています。

3. 「1色しか使わないとき、2色しか使わないときのことを考慮しないと」と考えてしまった

0に使える色の数を求めるときに、考慮しているので、1色だから*3とかしなくていいです。
2色だから1色余らせて、残りの2色は入れ替え可能だから*6とかしなくていいです。
それは各a[i]を処理するときに考慮しています。

まとめ

独立なんだから掛け算しろよ!!
マスター・オブ・場合の数でもやりますか……