三井住友信託銀行プログラミングコンテスト2019-E(500) Colorful Hats 2
概要
N人の人が並んでいて、それぞれが赤、緑、青の帽子をかぶってる。i番目の人が自分より前で、自分と同じ色の人がそれぞれA_i人いるという。この状況で全体的にありうる並びの場合の数はいくつか？
ACするまで
1. 数学的な性質がパッと見なさそうなので、なにかの数え上げDPだなー。
2. 最大3本の1ずつ増える増加列があるけど、いい感じに途中でどれかからどれかに遷移してるが入り乱れてるなぁ。
3. ひたすらにDPDPDPDPDPを考えるも、うまく遷移が見つからない。ー＞死
4. 2の考えからは実は正解に行く。手元で3つの増加列の現状が、色とか考えずに大小でソートすると、一意に決まるので、DPする必要もない。増加してるのがどれかはわかるので、掛け算すればAC。
考察
一見数学的な性質がないので、動的計画法で数え上げたくなるが、いずれにせよ手元で実験をしてみるべきである。
手を動かすと、最大3本の1ずつ増えてる列をいい感じに作っていくとわかる。R, G, Bが絡むとどれがどれかわかりづらいので、この手の問題でよくある、
色を固定しても、最後に掛け算すれば一般性を失わない。
を使う。
ひとまず、どれがどれかに該当するのかを無視する。
それぞれの色の人が(0, 0, 0)人いる状態からA_0, A_1...を見ていく。
i - 1番目まで、三色がそれぞれいくつか、つまり(x, y, z)人がわかるとする。
A_iから、i - 1番目では、それぞれの色の人(x, y, z)人のうち、どれかがA_iでないといけないし、その中にA_iとなる個数をPとすると、そのP種類のx or y or z = A_iのうち、どれからでもi番目でのA_iの条件を満たしかつ、毎回のこの操作は、i-1番の(x, y, z)人にのみ依存してi番目の(x, y, z)人を作るので、これは独立な事象の場合の数である。
よって、(x, y, z)を保持して、更新する際に、i-1番目での(x, y, z)人がA_iとなるx or y or zの数を掛ければよい。
ACコード：
Submission #8751136 - Sumitomo Mitsui Trust Bank Programming Contest 2019
一言
純粋に力負け。実験するという方法があまり出てこないってやっぱ経験不足だし何も言い訳できない。コドフォやらない俺が悪い。
