Cまで三完。
D. Unique Median
こたつがめさんの放送の振り返りを見てAC。アイディアは自然だが難しい。解法を理解するまでに、三回放送を見返した。
コンテスト中は、中央値が1～10それぞれになるときに、場合の数を求めるという方針を考えていた。
中央値がaのとき、aを0、a未満の数を-1、aより大きい数を1としたとき、（1の個数と-1の個数の差）が(0の個数)/2切り捨て以下になれば良い、というところまでは分かったが、数え上げに持っていけず。
そうではなく、k以下で-1、kより大きいとき+1として、累積和を取らなくてはいけなかった。
こうすると、区間和が0のとき、k以下のものの個数とkより大きいものの個数が等しくなるため、goodでない配列の個数を求められそう。（Zero-Sum Ranges系の処理ですね）
これに加えて、「kが中央値になるため区間内にkが存在する」という条件が必要になる。これは二分探索で処理できる。
0 件のコメント:
コメントを投稿