ABC094: D - Binomial Coefficients

ABC094: D - Binomial Coefficients

問題概要

• 相異なるN個の正の整数から2つを選んで(a,b)とする。
• aCbが最大になるようなa,bを求めよ。
• N <= 100000

  思考プロセス

• N ~ 10⁶なのでO(N)もしくはO(NlogN)までしか許されないだろう。
• 2つ選ぶ組み合わせを全部試すだけでNC2 ~ N²となってしまうので、工夫を要する。
• というか、組み合わせの計算自体もO(1)ではできない。しかしコンビネーションの値は要求されておらず、最大を与えるa,bを求めれば十分である。（ヒント）
• aCbにおいてaを固定すれば、bはa/2にできるだけ近いものが最大値を与える。
• aを決め打ち（特定の値に決める）ときに最適なbを高速に求めることができれば、N通りのaを試すことで問題が解ける。
• aを固定したときのbは、あらかじめソートしておけば2分探索でO(logN)で求めることができそう。しかし少し面倒。
• よく考えると、bを固定したときにはaは大きければ大きいほどaCbが大きくなるじゃないか。
• ということはaは最大のものだけ取ればよく、その後a/2にできるだけ近いbを選べばよい。どちらもO(N)でできる。

提出コード

https://beta.atcoder.jp/contests/abc094/tasks/arc095_b

振り返り

• 「決め打ち」に気づいた時点で、aとbの両方の決め打ちを幅優先的に検討すれば、bの決め打ちというより決定的なポイントに早く気づくことができた。
• 「決め打ち」とは何か。1つまたは2つ以上の変数を固定することである。
• この問題は、要するに、2変数関数の最大値を求めよという問題である。そういう言い方をすれば、1つの変数を固定するということは自分にとっても「典型」だといえる。滑らかな多変数関数の最大値問題であれば、受験数学の微積分でもやっているし、大学でも何度もやっている。
• にもかかわらず、その点に気づかなかったのは、2項変数という整数引数関数かつ「組み合わせ」という意味を持つ関数であることに惑わされて、「2変数関数の最大値問題」であるという当たり前の視点が持てなかったからだ。
• 滑らかな関数の最大値問題と離散的な関数のそれとでは、1変数を固定した後の最大値の求め方が異なっている。しかし、1変数を固定するという考え方の有用性自体は共通している。