2015-10-14

SRM 671 Div1 300 BearCries

03:16 |

なんか久しぶりの参加な気がする。

;__; な顔文字(_は1コ以上)が、1コの顔文字内では順番が保持されたまま何セットか混ざった200文字以内の文字列が与えられる。valid な顔文字に分割する方法は何通りあるか? (mod 10^9+7で)

考察考察
;の個数は偶数じゃないとだめ
両端は;じゃないとだめ
各 _ の両端に来る ; という観点ではどうか？ -> 単純な掛け算にならなさそう
最大200文字→3でわって最大66コの顔文字しかない

; までできてる ;_までできてる ;_;までできてる数を別々な状態として持つDPは？
-> 新規に _ が現れた場合、今までの ; が ;_ になったのか ;_ が ;_ になったのか一意にきまらない (※後で→元状態から複数の状態に遷移できるので一意に決まらなくてもいいし)

わからんし全探索を書く
最初の文字は; である。対応する右の;を決め、その間の _ から全 bit 組み合わせで全通り取る。ただし 1 コ以上。
採用した顔文字を消した後の文字列を再帰的に count で計算する。
これは動いた。...が、そこから発展がない...
いろんなパティーンの解を印字してぢっと眺むる。

おわり

あとで
Tourist の見ると3次元DP。だが添字の意味が分からず。ほぉ〜??
[i][;][;_] なる TL が。
; が来たら新規 ; を作るか ;_ に ; を足して1コ完成させるかすることができる。(; に ; は足せない)
_ が来たら ; を ;_+ にするか ;_+ を ;_+ にすることができる。(新規 _ は作れない)
で最終的に途中の顔文字がない状態 [N][0][0] が答え
分かってしまえば分かるがどうして分からなかったか分からない
どんな指標で状態を同一視するか、状態ごとにどんな演算をするか(これとこれを足しちゃっていいのか??とか)、MECEになってるか、あたりの思考がクリアにできてない感じがする。
今回だと、その指標だと状態から状態への演算がうまくいかん →実はうまくいく　みたいな
具体的には ; が来た時新規 ; と ;_+ → ;_; を別々に加算しちゃってるけど何かこう二重にカウントしちゃってる気がする→だめだ　あたり。

Accepted in practice

// [i][j][k] ... M[I], I in [0, i] の範囲で, ;で終わってる顔文字が j コ, ;_+ な顔文字が k コあるような状態の個数
modll dp[202][202][202];
class BearCries {
	public:
	int count(string M) {
		CLEAR(dp, 0);
		int N=M.size();
		dp[0][0][0]=1;
		REP(i, N) REP(j, N) REP(k, N) {
			auto cur = dp[i][j][k];
			if(M[i]==';') {
				dp[i+1][j+1][k] += cur; // 新規 ;
				if(k-1>=0) dp[i+1][j][k-1] += cur*modll(k); // ;_+ -> ;_+; (k コある)
			} else {
				dp[i+1][j][k] += cur*modll(k); // ;_+ -> ;_+ (k コある)
				if(j-1>=0) dp[i+1][j-1][k+1] += cur*modll(j); // ; -> ;_+ (j コある)
			}
		}
		return dp[N][0][0];
	}
};

kojingharangの日記

2015-10-14

SRM 671 Div1 300 BearCries