AtCoder Beginner Contest 117 非公式解説

飛んだ先の世界で時間が $T$ 時間過ぎると、元の世界では時間は $\frac{T}{X}$ 時間過ぎます。

多角形の成立条件に関する問題。問題文を読むと、長さが最大の辺が他の辺の長さの和より真に短いと多角形が成立することになるので、辺の長さでソートするなりmaxを取るなりして、最大の辺の長さを除去して残りの辺の長さの和を取って判定すれば解けます。

数学的背景を少し説明しておくと、仮に図形が三角形だとすると、長さが最大の辺が他の2辺の長さの和より長いか等しいと、三角形が潰れて直線になってしまうので、三角形が成立しません。

駒をある地点に置くと、その地点への到達はクリアされるので、まずは駒を地点のうちのどこかに置きます。

そして、駒を次々に隣り合うまだ到達していない地点に動かしていきます。

すると、全ての地点を踏むことができます。

ここで、駒を動かすとき、地点と地点の間隔ををどれか1つ動くことになります。この行動によって到達した地点が1つ増えます。

すると、この間隔を小さいほうから $M-N$ 個選ぶと全ての地点を踏めるようにできます。この長さの総和はソートなどを駆使して求められます。

まず、 $K$ が $2^t-1$ のような値であった場合、bit毎にそのbitを立てるべきか否かを貪欲に選べば求解できます。

そうでない場合、ある $K$ に対し一番上のbitを立てて $K=K-2^t$ として残りのbitを考えるか、一番上のbitを立てずにそのbitより下のbitを自由に決めるかでより良いほうを取る分岐が生じます。

これで、この問題は再帰の構造になります。あとは、この再帰を実装するとこの問題を解くことができ、計算量も $O(N log A_i)$ となります。

physics0523's 精進ログ