281.1

考え方を変えないと話にならないフェーズには突入しているんだろうなぁ、と思う。取り敢えず守りに入る段階ではない。

250

使っていい数字が制限されている状態で、ある数の次の数を求めよ、という問題。使ってはいけない数を含むものや、0で始まるものは不正な入力とする。

使っていい数字の数の進数表記でインクリメントする。面倒な実装系。

こういうので25点くらい差がつく。

600

45度の角度を常になして移動するボールがある。四方が壁になっていて、壁に当たると直観的な方法で反射する。(問題文にはなぜか90度右に回転すると書いてあって、その通りに実装したらあり得ない動きをしてくれた。)いくつかある特定の場所に到達するまでに、何回反射すれば良いか答えよ、という問題。角での衝突は1回とカウントする。いつまでも到達しないならばそう答える。

単純なシミュレーション問題。ボールが移動する領域をx*yとすると、整数値の座標だけ考えればいいので、x+yステップくらいで停止するはず。各ステップで目的地に到達するかどうか判定すれば良い。

悲しいことにJavaだと単純な到達判定だと間に合わないらしい。(C++だともっと低速そうな判定をしている人が普通に通っていたりするので、定数倍の問題だと思う。)仕方がないので、目的位置をx座標でソートして、ボールの位置と進行方向から、明らかに到達しない側については無視するような最適化(これでおよそ倍になる)をやったところ通った。

1000

N個の物体を重ならないように等間隔に並べることを考える。このとき、各物体の移動距離の総和をコストとするとき、最小コストを求めよ、という問題。

まず、初期位置でソートする。最終的な配置を求めることができたなら、移動に必要な最小コストは各要素の差分の総和になる。また、各物体の移動方向を考えると、左に移動するか右に移動するか移動しないかのいずれか。すべてを移動すると仮定すると、右に移動するものがK個のとき、左に移動するものはN-K個になるので、全体として考えると、K>N-Kならば最終的な位置を左にする方が得になる。つまり、N個の物体のうち、どれか一つは動かさない状況で、最適なコストを実現することができる。

N点のうちどれか一つを固定したときに、最小のコストを実現するには、物体の配置間隔を計算できれば良い。まず、下に凸な式の線形和は下に凸である。物体の間隔をDとし、固定する物体をX番目とするとき、I番目の物体の置き場所は、p[X]+(I-X)*Dになる。移動コストはabs(p[X]+(I-X)*D-p[I])なので、これは下に凸な関数である。すべてのIについてこれは成り立つので、Dについて三分探索を行えば、これらの総和の最小値を求めることができる。

また、一点固定と同様にすると、もう一点の固定もできる。実際には固定ではなくて、その点に一番近い左側の点または右側の点のいずれかに固定できる。(整数座標にしか置けないので。)