AB二完で終了。悲しい。
C - Maximize GCD
解説AC。
Aの要素全てをmax(A)に揃えられるほどKが大きいときはOK。
問題は、そうできないとき。
普通に考えると、gcdをxにできるかどうか、の判定にはO(N)かかる。なので、gcdの候補をどうやって絞っていくかが問題。だけど、どう絞れば良いのだろう……？
……と考えてハマってしまった。
実際は、「gcdをxにできるかどうかの判定」の計算量を減らせる。
あるxに対して、kxより大きく(k+1)x以下の範囲にあるものは全て(k+1)xにする。なので、「その範囲に何個あるか」「その範囲の総和」が分かれば良い。
それらを予め求めておくことで、各xについて、O(max(N)/x)になり、（調和級数の）logの計算量で求められる。
コンテスト中、「gcdをxにできるかどうかの判定」の計算量が本当にO(N)必要なのか？ を疑問に思った時間は確かにあった。だけど、gcdの候補の方が絞れそうな気がしたので、真面目に考えずに終わってしまった。
候補を絞るのが難しそうと思ったときに計算量を減らせないか検討すべきだったんだろうけど、飛ばしてDへ行こうと思ってしまった（飛ばしたこと自体は悪いことではないけど）。
まあ確かに、max(A)とかから候補を絞るのはいかにも嘘っぽいので、計算量削減を考える方が筋は良いんですよね。
D - Pure Straight
（解説通りの方法ではないけど）解説AC。
解説の「使う項と部分列の位置を固定した場合」の部分が非常に重要だと思う。コンテスト中、一応正しいことを考えてはいたようだけれど、答えは「転倒数＋何か」になるはずとは思ったけれど、「何か」の部分があやふやだった。
あとは、区切り位置を決め、「その前の部分からどの数字を取ってきて、その後ろの部分からどの数字を取ってくるか？」をbit全探索すれば計算量は悪いが答えが求まる。自分の書き方だと定数倍がきついため、bit全探索の部分を枝狩り（区切りの直前の数字は必ず前におく、など）してAC。
0 件のコメント:
コメントを投稿