読者です 読者をやめる 読者になる 読者になる

SRM403 500 : TheLuckySequence

テスト前は良くない。

問題概要

  • 4と7のみで構成される数字がラッキーナンバーです。
  • ラッキナンバーをlength個並べた数列Aがあったとして、
    A[i]の一番左の数とA[i+1]の一番右の数が一致していた場合それはラッキーな配列です。
    例){447,74,4444,447} 
  • 今 配列number[i]と、長さ lengthが与えられます。
  • 各A[i]の要素は必ずnumber[j]のどれかに一致していなければいけません。
  • ラッキーな配列は何通りありえますか?

解法

  • dp + ダブリング
  • まず、ラッキーナンバー以外は使わないのでnumber[i]からラッキーナンバーだけを抽出します。
  • こうして出来た新しいnumber[i]の要素数がlengthより大きい場合は普通に
    dp[今幾つ目のを見ているか][あといくつ数字を使うか]=何通り?
    でDPして終わり。
  • もしlengthより小さい場合はnumber[i]の要素数に対してまず上のdpをしてやります。
  • すると
     4から始まって4で終わる通り数 と
     4から始まって7で終わる通り数 と
     7から始まって4で終わる通り数 と
     7から始まって7で終わる通り数 に場合わけできます。
  • 4->7 = 4->4 * 4->7 + 4->7 * 7->7 のような式で 組み合わせをつなぎ合わせることができます。(ソースのxros関数を参照 )
  • これを利用して2^k回繰り返した時の通りの数が分かるので
    ダブリングによってlengthの値が巨大なときも対応することができます。
  • あまりが出てしまった場合はもう一度、DPしてxrosの式で掛けあわせます。
ソースコード

感想

解法思い付いたときはすげえ教育的良問だ!

と思ったのも束の間実装に1時間以上かかるとは思わなかった。

最初、二次元配列のコピー怖くてずらずら書いてたらコードがやばいことになったのでこれでもマシになった方。

時間ないに思い付くことが出来ても解ける気がしない。

迅速な実装力が必要(もっと賢い方法があるのかなぁ‥)