kmjp's blog

競技プログラミング参加記です

三井住友信託銀行プログラミングコンテスト2019 : E - Colorful Hats 2

無駄はあったものの、割と早く解けた。
https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_e

問題

N人の人が並んでいる。
各人赤青緑色のいずれかの帽子をかぶっている。
各人が自分の前に自分と同じ色の帽子をかぶっている人が何人いるか、という情報が与えられる。
情報に合致する全体の帽子の組み合わせは何通りか。

解法

i番目の人がpと答えた場合、手前にp回登場した色の帽子のいずれかを選択することになる。
また、その時その帽子の登場回数はインクリメントされる。

C(p) := p回登場した帽子の数
として、この配列を前から順に入力に対応して増減させていけばよい。

int N;
int C[101010];
const ll mo=1000000007;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll ret=1;
	C[0]=3;
	FOR(i,N) {
		cin>>x;
		ret=ret*C[x]%mo;
		C[x]--;
		C[x+1]++;
		
	}
	cout<<ret<<endl;
}

まとめ

普段だと400ptでもいいぐらいだな。