ABC215 参加記録 - geam1113’s diary

GCCの組み込み関数__builtin_clzllを使うと、

__builtin_clzll(1LL) - __builtin_clzll(N)

で求められます。

文字列の並び替えの総数は最大でも、8! = 40320なので全列挙可能です。

c++ではnext_permutationで順列全探索できます。得られた文字列を昇順ソートして重複要素を削除し、K番目を求めます。

条件の $gcd(A_i, k)=1$ を言い換えると、「kは $A_i$ と共通する素因数を持たない」です。よって、 $A_i$ の素因数を全て列挙し、素因数の倍数を全て候補から外し、残ったM以下の数が答えです。

Nが小さいので高速素因数分解により、全ての素因数は $O(NlogN)$ で全列挙可能です。自作ライブラリになかったので、コンテスト中の実装は下記のサイトのものを使用しました。

高速素因数分解は過去問にもありましたが、osa_k法と呼ぶのは初めて知りました。

素因数の倍数を候補から外す処理は、エラトステネスの篩と同様の処理でできます。候補となる素因数の個数をPとして、 $O(PlogN)$ くらいです。

下記のコードは、osa_k法をオリジナルで実装しなおして、コンテスト後に提出し直したものです。

コンテスト後に解説は見ずにACしました。

状態として必要なのは、

1.これまでどのコンテストにでたか

2.最後にどのコンテストにでたか

です。1は $2^{10}$ の冪集合で表現でき、2は10通りです。

1回目のコンテストから順に、i回目のコンテストに出る、出ないという選択に基づいて、各状態を更新する場合、全状態数は最大でも $1000×2^{10}×10≒10^7$ なので、実行時間制限に間に合います

dp[i][j][k] := i回目のコンテストまでを考えた時に、出場したコンテストの集合がjで、最後に出場したコンテストがkであるものの総数

とします。また、A = 0, B = 1, ..., J = 9とします。

ここで、初期状態をdp[0][0][0] = 1にしておきます。空集合を定義していないので状態と矛盾しますが、特に実装上問題ありません。

i回目のコンテストから $i+1$ 回目のコンテストへの状態遷移は以下のようになります。

(1) $i+1$ 回目のコンテストに参加しない

　　出場したコンテストや最後に出場したコンテストの状態に関わらず、状態は $i$ から $i+1$ に引き継がれます。よって、

　　 $dp[i+1][j][k]$ += $dp[i][j][k]$

(2) ${i+1}$ 回目のコンテストに参加する

　　(i) $j$ で $AS_{i+1}C$ が出場済みとなっている時( $j$ が $S_{i+1}$ を含む)

　　　　(A) 最後に出場したコンテストが $AS_{i+1}C$ の時( $S_{i+1}$ == $k$ )

　　　　　　 $AS_{i+1}C$ に出場可能です。よって、

　　　　　　 $dp[i+1][j][k]$ += $dp[i][j][k]$

　　　　(B) 最後に参加したコンテストが $AS_{i+1}C$ でない時( $S_{i+1}$ != $k$ )

　　　　　　問題文の条件に反するので、遷移できません。

　　(ii) $j$ で $AS_{i+1}C$ が出場済みとなっていない時( $j$ が $S_{i+1}$ を含まない)

　　　　最後に出場したコンテストによらず、コンテストに出場できます。よって、

　　　　 $dp[i+1][j \cup S_{i+1}][S_{i+1}]$ += $dp[i][j][k]$

最後にdp[N][0000000001〜1111111111][0〜9]の総和をとれば答えです。

コンテスト中、全状態数をしっかり見積もらずに棄却してしまったので、10種類という少ない制約からも、もう少し考えるべきでした。