No.314 ケンケンパ

No.314 ケンケンパ - yukicoder

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

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

• 
• 
• 
• 

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;
}