AT_s8pc_6_h Percepts of AtCoder 2

[problemUrl]: https://atcoder.jp/contests/s8pc-6/tasks/s8pc_6_h E869120 は square1001 に、今年から $ Q $ 年間誕生日に数列をプレゼントすることにしました。 square1001 は、「プレゼントする数列の長さが短い方がよりコンパクトで良い」と言ったので、プレゼントする数列は出来るだけ短くしたいです。また、古から伝わる AtCoder 社の教えに基づいて、プレゼントする数列を決める必要があります。 AtCoder 社の教えとは、以下のようなものです。 - 数列の要素は全て **異なる**。 - プレゼントする数列に部分列として出現する数列のうち、単調増加列であるようなものの種類数はちょうど、聖なる数 $ K $ 個である。 ここで、数列 $ A\ =\ (A_1,\ A_2,\ ...,\ A_N) $ の「部分列」とは、$ A $ から $ 0 $ 個以上 $ N $ 個以下の値を消して、残った値の順序を変えずにできる数列のことです。 また、数列 $ A\ =\ (A_1,\ A_2,\ ...,\ A_N) $ が「単調増加列」である条件は、$ A_1\

N/A

N/A

### 制約 - $ Q $ は $ 1 $ 以上 $ 1\ 000 $ 以下の整数 - $ K_i $ は $ 1 $ 以上 $ 5\ 000\ 000\ 000\ 000\ 000\ 000\ (=\ 5\ \times\ 10^{18}) $ 以下の整数 ### 小課題・得点 1. (30 点)：$ K_i\ \leq\ 100 $ を満たす。 2. (70 点)：$ K_i\ \leq\ 1\ 500 $ を満たす。 3. (1400 点) : 追加の制約はない。 ただし、小課題 $ 3 $ について、以下のように得点が決定します。 ここでは、$ Q $ 年間における $ N $ の最大値を $ L $ とします。また、全てのテストケースにおける $ L $ の最大値を $ L' $ とします。 - $ 120\ \leq\ L'\ \leq\ 128 $ のとき、この小課題の得点は $ 125 $ 点 - $ 100\ \leq\ L'\ \leq\ 119 $ のとき、この小課題の得点は $ 1400\ \times\ 5^{-(L'\ -\ 99)\ /\ 20} $ 点 - $ 0\ \leq\ L'\ \leq\ 99 $ のとき、この小課題の得点は $ 1400 $ 点 ### Sample Explanation 1 $ 1 $ 年目のプレゼントとして渡す数列は、$ (2,\ 3,\ 1) $ です。 この数列には、増加部分列が $ 5 $ 個あります。$ (),\ (1),\ (2),\ (3),\ (2,\ 3) $ です。