AB二完。終了後にCを自力AC。
No.1513 simple 門松列 problem
求めるものが二つあるが、ans2はans1に[0,K)の平均を掛ければ良さそう。
ではans1をどうやって求めるか？ というとこっちはDPが使える。
DP[i][j]で、x-2番目の要素がi、x-1番目の要素がjの長さxの門松列列の個数とする。これを用いて長さx+1の門松列列の個数を求める。
i<jのときを考える。
すると、次の値となりうるのは、0, 1, 2,..., j-1からiを除いたもの。これをそのままやると間に合わない（全体での計算量が四乗になってしまう）が、累積和を使うことで計算量が落とせ、全体で三乗になるため、間に合う。
No.1514 Squared Matching
ABCで同じ問題が出たのを機に、解説AC。
こちらの方が制約が厳しいため、強引に素因数分解・約数列挙して解くことはできない。
xの約数のうちの最大の平方数f(x)について着目することが必要になる。
x/f(x)で分類してCounterで数えれば答えが合うことは分かったが、それだとMLEになってしまう。
実は、各aについて、bは(a/f(a))*(平方数)と表せるので、bの個数はsqrt(N/(a/f(a)))と直接求められる。
0 件のコメント:
コメントを投稿