おはようございます。しほみんです。
今日は昨日に続いてD-F問題について振り返ります。明日はお休みします。
最近謎に仕事を抱えてしまったので…
D問題
整数Nがあります。
Nにたいして以下の条件zを考えます。
・zはpのe乗数とします。
・Nはzで割り切れる。
・前のNとはどの数とも異なる。
NをN/zに置き換えます。
この操作を1回とすると最大何回行えますか？
とても厄介そうですが、Nについて素因数分解していくとすると、
それぞれの素因数にたいして、z = p1の1乗、p1の2乗、p1の3乗...と可能です。
なので、それぞれ素因数が何個あるか見つけ出して、あとはその数に応じて決めていけばよいです。
素因数はo(√N）で求められるので、十分間に合います。
素因数pで割った回数に応じて答えを出すにはちょっと工夫が必要です。
まず1回割ったときにカウントします。その次は、2回割ったらカウントします。
というようにカウントすべき回数を随時更新してやっていけばよいです。
自分は最初合成数でやってWAを出しましたが、普通に気が付けば問題ないレベルでした....Cでてんぱったのは大きいですね。
E問題
N個の数があります。
それぞれのi番目の数はAiからBiの間の数を取ります。
このできた数列の中央値を取ります。（奇数なら(n+1)/2、偶数ならn/2とn/2+1）
この中央値としてありうる数を求めなさい。
問題制約を見てみます。
Nは10の5乗、数字は10の9乗をとるので、
まあ、あり得る数を全部数えるはo(10の9乗)となり、無理そう。
o(N)ぐらいで考えられるけどなんかいいアイデアもない....
となると後あり得るのは最小の数列でとる中央値と最大の数列で取る中央値の間は全部とれるって仮定すれば、
ai,biの数列をソートして、偶奇の場合で中央値をきめて、max -min +1ぐらいしかないなって思ってかきます。
もしなんかダメな条件があるなああとはそれを引くしかないなって感じでした。
ただ、ダメな条件がないのでそのままだして、ACしました。（たった10分で解けてる...）
まあ中央値が途中をとる理由は結構明確な気がします。なんとなく、いろいろ数をとっていく中高々1しか変わらないので、うまくひっくり返すことができるのです。それを繰り返すと帰納的にオッケーだと思います。
F問題
長さNの正整数列があります。正の整数Sがあります。
上の整数列から最低1つ以上の要素を選び出して、T数列を出します。
このTのうちに、空集合でない部分列を取り出します。その総和がSとなる組み合わせをf(T)とします。このf(T)の和を求めなさい。
非常に大きい数なので998244353で割った余りを求めなさい。
まあ、この問題みてどうも無理だなーって感じを思ってました。そしたら時間終わってました。
ただ、よくよく考えれば計算量的にo(N)が限界で、頭から考えることしかできないです。なので、頭から求める方法を考えます。
こういう時は動的計画法が便利です。
その方法ですが、
dp[i,j]をi番目まで見たとき、その和がjになっている組み合わせの数とします。
すると、dp[0,0]を1として初項に置くと
i+1を考えるとき、すべての和（3000以下）において、
・iの中ですでに和がSiでi+1番目を選ばないケース
このケースはdp[i +1, Si] += 2*dp[i,Si]です。
なぜなら、集合Tとしては、i+1番目は選ぶかどうか自由です（あくまで、そのあとの和がSになるときにi+1番目を選ばなければよい）。
・iの中で和がSiでi+1番目を選ぶケース
このケースはdp[i +1, Si + （i+1番目の数）] += dp[i,Si]です。
なぜなら、集合Tとしてはi+1番目を追加する場合の数しかないし、i+1を和として追加しないとならないからです。
よってそれで推移していけば完成です。
最後に....
F問題は解きたかったですがこういう動的計画法はちゃんと学ばないとダメかなあと思います。ただ、頭から解いていくって発想だと何となく出てきたのでもっとそこら辺を強めないとだめだなと自覚しました。
今度もABCも自己ベスト更新できるように頑張ります。ではでは。
