水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

No.314 ケンケンパ

No.314 ケンケンパ - yukicoder

本当に典型的なDP問題。
なお、私は考察に失敗し、一般項を出すことに失敗しました。(考察が弱いかも…)


ハム吉さんの解説の通り、和が少ないものの時に試すと以下のことがわかります。

  •  {a_1=1}
  •  {a_2=2}
  •  {a_3=2}
  •  {a_n=a_{n-2}+a_{n-3} (n \ge 4)}

hamukichi.hatenablog.jp


というわけで、この数式の計算通りになるよう、DPを構築するという感じですかね…。
本当はもう少し上手く前の状態を見て(ケンだったのか、パだったのか)やるのかもしれませんが、まあ… 解けたから良しとします…。

あと、うっかりしていてDPの確保範囲が狭いためにbus errorに初めて直面しました。ちょっとびっくりしましたが、制約ちゃんと読まないとダメですね。気をつけます(桁が一つ小さかった)。


以下、C++での解答です。

#80821 No.314 ケンケンパ - yukicoder

ll dp[1000001];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout.precision(16);
	
	int n;
	cin >> n;
	
	dp[0]= 1;
	dp[1] = 2;
	dp[2] = 2;
	for(int i = 3; i < n; i++) {
		dp[i] = (dp[i-2] + dp[i-3]) % MOD;
	}
	
	cout << dp[n-1] << endl;
}