SRM 522 DIV1 Easy RowAndCoins

SRM 感動した O(1)

http://apps.topcoder.com/stat?c=problem_statement&pm=11566&rd=14547

コメント

Editorial http://apps.topcoder.com/wiki/display/tc/SRM+522
を見て、感動した。
これはDIV2MediumでもRowAndManyCoinshttp://apps.topcoder.com/stat?c=problem_statement&pm=11605&rd=14547として出されている。
ただし、DIV1Easyの方は(N<=14)なのに対し、DIV2Mediumの方は(N<=50)。
これはどういうことかというと、(これは自分もそうだったが)最初に(N<=14)を見て状態をbitで持つ、と方針を決めてしまった。
しかし実際には式一発で解ける問題であった。
ただ、bitでやってもいい(なんか計算量見積り、自分が間違ってた)
また、自分は戦略を考えていたが、bitでやることが頭にあって、それを前提とした考え方をして、わからなかった。
これはつまり、制約による引っ掛け問題であって、単純に制約だけで方針を決めることは必ずしも良くなく、柔軟に考えることが必要だということだ。
また、O(1)でなくても、メモ化再帰の計算量を確実に見積もってそれでやるべきだ。
ただやっぱりDIV2Mediumに会っていた可能性もあるのでO(1)も思いつくべきだ