GCJ 2021 Round 1A Prime Time - かんプリンの学習記録

問題概要
解説
提出プログラム
感想

問題概要

素数が書かれたカードが複数ある．そのカードを ${A}$ のカードに書かれた数の総和と ${B}$ のカードに書かれた数の総積が等しくなるように2つのグループ ${A,B}$ に分けたとき， ${A}$ の総和( ${B}$ の総積)として考えられる最大の値を求めよ．

入力

素数 ${P}$ は ${2\leq P \leq 499}$
素数 ${P_i}$ は ${N_i}$ 個ある．
与えられる素数の数 ${M\leq 95}$
${2\leq \sum_{i}N_i \leq 10}$ (Test Set 1)
${2\leq \sum_{i}N_i \leq 100}$ (Test Set 2)
${2\leq \sum_{i}N_i \leq 10^{15}}$ (Test Set 3)

解説

以下 ${A}$ の総和( ${B}$ の総積)を ${K}$ とする．

Test Set 1は ${A}$ にいれる数をDFSとかで全探索でできるのはすぐわかる．

Test Set 2はそうもいかないが，カードの総和は ${100×500}$ 以下であることに注目すると， ${K}$ を決めると素因数分解の一意性から ${A,B}$ に分けられるかの判定ができる．Osa_kとかで素因数分解すれば高速に解ける．

Test Set 3はカードの総和が大きくなるので工夫がいる． ${B}$ に入るカードの数が少ないことから， ${B}$ の総積ではなく総和を探索する． ${B}$ の総和を決めると ${K}$ がきまるのでTest Set 2と同様に解ける． ${B}$ の総和は ${10000}$ もないので高速．

提出プログラム

感想

全探索じゃなくずっとDPで考えてたのが敗因