AtCoder ABC163
April 18, 2020
https://atcoder.jp/contests/abc163
D解いてる途中でunratedなコンテストになってしまった。
D - Sum of Large Numbers
なので、を全探索するのは無理。
実験
とりあえず0~NのN+1個の数からK個選ぶ場合を樹形図で書く。 についてはあとで足せばいいので、からK個選ぶとする。 実際書いてみると、の組の和はほとんどすべてがの和と同じで、新たに生成される和は(1と、N,N-1,…からK-1個をとる場合)のみであることに気づく。以降についても同じ。こうして樹形図を眺めると、0~NのN+1個からK個選んだときにあり得る和は、その最小値から最大値まですべてをとりそうなので、これを簡単に示す。
0~NのN+1個の数からK個選んでつくられた組の和の集合をSとおく。Sの最小値を与えるのは、のときであり、最大値を与えるのは、となることは明らか。したがって、
最大値は、
となる。示したいことは、任意のに対して、その和を与える組が存在すること。これを構成的に示す。
まず、最小値を与える組を考える。この組の要素の総和をとしたとき、K-1をKに置き換える(右にずらす)ことで、要素の総和がとなる組が得られる。こうして得られた組のをに置き換えることで、要素の総和がである組が得られる。これを繰り返して、の組まで作ると、これ以上、を右にずらすことはできないので、次に、のをで置き換えるという操作を繰り返す。以上の操作を繰り返すことで、最終的に、集合Sの最大値を与える組が得られる。操作から明らかなように、任意のに対して、その和を与える組が存在することがわかる。
(ここで、K個選んだ場合の和とK+1個選んだ場合の和で同じになるものがあるかと疑問に思うが、N+1個の整数は、であることを思い出すと、これはあり得ないことがわかる。)
解法
実験によって、K個選んだときの要素の総和がとりうる値は、その最小値から最大値すべてなので、個ある。選ぶ個数をまで繰り返して計算すれば、この問題を解くことができる。
E - Active infants
直感的には、が大きい幼児から、元の位置からもっとも遠い位置で空いている位置に移動させるという貪欲法がうまくいきそうではあるが、このアルゴリズムだと正しい解は得られない。少し考えてみると、移動後の位置は、両端からうまっていくので、空いている位置の区間をと表すと、の狭まり方は当然その後に配置される幼児に影響を与える。したがって、貪欲法ではなくDPで解く必要があるとわかる。配置するのは、が大きい幼児からでよさそう(要証明)なので、問題は、空いている区間のどちらに配置するかということである。
結論から言うと、という状態にまとめて、DPをすればいい。はじめ、として考えていたが、これだと計算量的に間に合わない。この状態は結局という状態と1対1に対応するので、もうすこし状態の意味について考察をするべきだった。
あとは普通にDPを実装するだけ。