途中まで考え方は良かったけど、時間的に無理だったしそも微妙に考慮不足。
解説を何度も読み返して、解法は合ってるはずなのに何故かWAが出る、と試行錯誤してたら結局それまで使ってたはずの二分探索のコードにバグがあったことが判明するまで2時間ほどああでもないこうでもないと難儀を……。
問題文
ティーバッグが全部でA[1]+A[2]+…+A[N]個あります。
フレーバーはN種類です。
ディーラーにx個渡してもらい、その中から難易度Bの数だけ同じフレーバーのティーバッグを選べば勝ち、というゲームをします。
ディーラーは最善を尽くし必ず負かそうとするので、Q回ある難易度Bそれぞれについて、確実に勝ち筋が存在するxを求めるが、存在しなければ-1とします。
解説
まず服をディーラー側の気持ちになります。
ティーバッグとそのフレーバーがこのようにある状況で考える。
1 □□□□
2 □□□
3 □□□□□□
4 □□□□□□□
ディーラーからすれば、難易度Bの数だけ同じフレーバーのティーバッグを勝てないように選ぶためには、満遍なく違うフレーバーのティーバッグをx個選びたい。
少し飛躍するが、言い換えれば、ティーバッグのフレーバー毎の個数の最大Max(A[1…n])を超過する難易度Bの場合、ディーラーは必ず勝てないようにティーバッグを選ぶことができる。(それって前提から破綻してるクソゲーなのではと思わなくもない)
であれば難易度BはAの最大値以下の数の場合のみ考慮すればよい。
では、上記の例で難易度Bが4で、xを13と宣言した時を考える
1 ■■■□
2 ■■■
3 ■■■□□□
4 ■■■□□□□
ここまでディーラーが12個を選んだ時点で、次にどのフレーバーのティーバッグを渡しても勝ち筋が存在するようになってしまう。
フレーバー毎のティーバッグの数であるAを昇順に並べ替えれば、勝ち筋が存在するしないの境目ができる。つまり二分探索が使える。
であれば上記に示した図からも、
B未満の個数を持つAの総和
B以上の個数を持つAの種類数にB-1を掛けた数
+1
以上のすべてを足し合わせた数が答えになることがわかる。
上記の例で計算すると、3+(3*(4-1))+1 = 13 となる。
総和を求めるにはQ回あるBの都度O(N)の計算をする必要があるが、それでは遅いので累積和を使う。
というわけで二分探索と累積和を使えば答えをO(N)程度で求められることがわかる。
コメント