No.1658 Product / Sum
解説AC。
1でない個数を二個にして式変形してみると、解ける。
解法を理解してから見ると、サンプル1が良い誘導になっているのが分かる。二変数にすれば良いんだ、と。
コンテスト中は、一変数にしなくては厳しい気がして悩んでいた。
サンプル1で、10*10 / (2*10) = 5 という式が見えてしまったのが良くなかったか。一般にはN = 2でA1 = A2のとき上手くいくとは限らないのは分かったけど、この式から変形してどうにかするのか、と。
詰まったら別の方針を考えないとね。
No.1659 Product of Divisors
コンテスト後、自力で解けた。
が、公式解説で二項係数でやっているところを思いつかず、DP＋行列累乗で解いてしまった。
・DP[i] = pに関する指数が残りi個のときの場合の数
として、そこから各dに何個振り分けるか？ というのをK回行った。
まあNが小さいからこの解法で問題ないけど、最初二項係数でできるのでは？ と疑ったのに、解法を思い付けなかったのは良くない。
0 件のコメント:
コメントを投稿