ABC 178 D - Redistribution を転がしながら思う 解けない問題との付き合い方

はじめに

 問題はコチラ
 DP のよくある問題の階段の登り方に類似して見えた。
 "DP あるある" かもしれないが、何を Dynamic に programming しようか非常に悩む。
 とりあえず S 段の階段への到達の組み合わせに置き換えて考えた

コード & 解説

 dp はコードをベースに考えた方が早い気がする
 ただ、その前に整理すべきポイントがあります。

  ・dp[i]における i は階段の数(今、1段？2段?3段?...S段?)
  ・dp[i]に格納する数字は、何回、その段数を通過したか(例えば 4段を 1回？2回？3回？)
  ・通過した階段はいずれも 3 以上(<=ココ重要)。

dp.cpp

#include <iostream>
#include <vector>
using namespace std;

int main() {
                                  // COMMENT(好き勝手に書いてみる、見にくかったらゴメン)
	int S; cin >> S;              // =>input
	vector<long long>dp(S + 1, 0);// =>start point is stair#0,so dp length is S+1;
	dp[0] = 1;                    // =>every one start at stair#0, so dp[0] = 1;

    //<-------let's start DP-------------------------------------------------
	for (int i = 3; i <= S; i++) {//Step by step, climb the stair.
       
        //If (S-i<3), rest factor would become under 3.    
        //There are no restrection of number of step to climb at once.
        //So stair#0 => stair#S is possible.this is why i==S needs.
		if(S-i>=3 || i==S){

            //Turn right, and let's look back.which stair did i through?
            //And if the total value of stairs that I through in the past,
            //the combination would be needed to transport to dp[S]. so int k's maximum is S.        
			for (int k = 0; k <= S; k++) {
                
                //If the differenct between current stair and past stair is bigger than 3,
                //let's adapt current stair.
                //Of course, I only use stairs that I have passed through in the past. 
				if (i - k >= 3 && dp[k] != 0){
					dp[i] += dp[k];
				}
			}
            //dp[i] would become too big value,so "% 1000000007" would be needed.
			dp[i] = dp[i] % 1000000007;
		}
	}
    //------------------------------DP end----------------------------------->
	cout << dp[S];

	//while (1) {}
	return 0;

}

 あとは紙に書いて各自イメージ作りに徹すれば行けると思う。

解けない時にやった事

・思い切って別のことをする[ex). 掃除、食器洗い、ご飯の準備。。しながら片隅で考える(以外に有効)]。
・レベルを下げてDP の原理を復習する
 --なんでもいい、paiza, educational dp or web で検索して有識者の見解を読み漁る
・全く別の問題を解いて、頭を柔らかくする
 --atcoder, paiza ... 色々ある、コツは解いてて楽しい問題である事がミソ。