公式

E - Existence Counting 解説 by evima

Hints

Hint 1 Let’s first consider counting by hand.
How can we find the answers to the problem as easily as possible?

Hint 2 Consider the case where \(N=6, K=4, P=(4,6,5,1)\).
When counting by hand, you would first deal with the following:
  • Sequences in the dictionary \(s\) starting with \(1\)
  • Sequences in the dictionary \(s\) starting with \(2\)
  • Sequences in the dictionary \(s\) starting with \(3\)

Next, you would deal with the following:

  • Sequences in the dictionary \(s\) with prefix \((4,1)\)
  • Sequences in the dictionary \(s\) with prefix \((4,2)\)
  • Sequences in the dictionary \(s\) with prefix \((4,3)\)
  • Sequences in the dictionary \(s\) with prefix \((4,5)\)

Hint 3 By performing the steps in Hint 2 “recursively,” you should be able to find the answers by hand.
Let’s conduct a detailed analysis to realize this with code.

Hint 4 In Hint 2, we said the following:

Consider the case where \(N=6, K=4, P=(4,6,5,1)\).
When counting by hand, you would first deal with the following:

  • Sequences in the dictionary \(s\) starting with \(1\)
  • Sequences in the dictionary \(s\) starting with \(2\)
  • Sequences in the dictionary \(s\) starting with \(3\)

At this point, you would have added equal values for \(1,2,3\) and for \(4,5,6\). (Formulating the value to add here is not so difficult)
We should know a data structure that is friendly to such additions.


Hint 5 In Hint 2, we also said the following:

Next, you would deal with the following:

  • Sequences in the dictionary \(s\) with prefix \((4,1)\)
  • Sequences in the dictionary \(s\) with prefix \((4,2)\)
  • Sequences in the dictionary \(s\) with prefix \((4,3)\)
  • Sequences in the dictionary \(s\) with prefix \((4,5)\)

At this point, you would have added equal values for \(1,2,3,5\) and \(6\) respectively.
\(4\) is missing, isn’t it? What should we do?


Hint 6 When you reach Hint 5, all sequences that have not been checked yet begin with \(4\). In other words, all sequences in the dictionary \(s\) considered from this point onward will necessarily contain \(4\).

Hint 7 Here’s a more vague hint.
Once \(4\) appears in \(P\), all sequences considered after that must necessarily contain \(4\), so the handling of \(4\) after that is pretty much irrelevant.
However, in the final valuation, the sequences starting with \(4\) in the dictionary \(s\) are not irrelevant, so they need to be processed somewhere.

Hint 8 It’s time to connect Hint 3 and Hint 7.
Could the “processing” mentioned in Hint 7 be done “recursively”?

投稿日時:
最終更新: