出題しようと準備していた問題が想定TLE解法で出題されてしまって、とても悲しい気分になったので解説を書きました。。。

用意していた問題

Xから立ってるビットの数だけ足すというのをK回くりかえすと何になるか？

X,KはT個与えられる。

X,K<10^17, T<10^5

解法

ツイートする

ひっくり返して線分の集合にバラして双対となる多角形の集合を求めて外周を決めるだけ。

ライブラリ除いて50行くらい。サンプルは通った。

ツイートする

これは、Competitive Programming Advent Calendar Div2014の9日目の記事です。

誤差

typedef double Real;

誤差死したときはlong doubleにし、TLEしたときはdoubleにできるように最初からtypedefしておくと便利です。

EPSゲー

座標の範囲が[-1000:1000]だとEPS=1e-8を使うというのを基準にしていて、相対誤差っぽく[-10000:10000]だとEPS=1e-7とかにすると苦しむことが減ります。

縮退

回転

与えられた全ての点を原点を中心に少しだけ回転させる。

スラブ分割（コンピュータ・ジオメトリ P.149）する時など、x座標が同じ頂点があって縮退している場合に縮退が解けます。

例題：最終防衛線

(x,y)->(x+α*y,y)

上と同じタイプの縮退が解けます。

乱数

座標に小さな乱数（ただしEPSよりは十分大きい）を追加して縮退を解く。

例題：Exportation in Space

ただし、実際に値を出すときは縮退前の座標を使わないとちょっとずれてWAの原因になります。

記号摂動

小手先でゎない。

便利関数

sign

混乱を避けるため、EPSはこの関数以外では使わないようにしています。

inline int sgn(Real a, Real b = 0) {return a < b - EPS ? -1 : a > b + EPS ? 1 : 0;}
inline bool near(Point a, Point b) {return !sgn(abs(a - b));}

vec

inline Point vec(const Line& a) {return a.b - a.a;}

角度

inline Real arg(const Point& base, const Point& a, const Point& b) {return arg((b - base) / (a - base));}

sqrt

-EPSを突っ込んで死ぬのを回避。

inline Real sr(Real a) {return sqrt(max(a, (Real)0));}

その他

c.c+polar(c.r, PI/2*i)

円と線分をグラフに落とすときにc.c+polar(c.r, PI/2*i)を頂点に追加しておくと便利なことがあります。

例題：Magnum Tornado

円周上をPI/2以下しか動かないのでどっちから来たか簡単に分かります。

モンテカルロ法

どんな面積でも簡単に求められることで有名。

というのはさすが冗談で、例えばサブミットデバッグするときに答えが大きくずれているかのチェックができたりします。

ツイートする

※この記事は結果発表前に書いています

提出したコード

https://gist.github.com/not522/9a398898d258b24a4512

方針

忙しくて時間がなかった（実際にかけた時間は12時間くらい）ので楽に点数が上がりそうなのだけ実装する

そもそもかなり自由度が低いゲームなので、貪欲でもそこそこの点数が得られそうと予想していた

やったこと

Parameter::CharaAddAccelWaitTurnごとくらいで加速

player.accelCount()を見て適宜調整

基本的には2個くらい残す

離れていってるなら残り1個だろうと加速

最後の一手なら加速

加速なしで次の蓮に到達できるならそのまま

次の蓮の位置を考慮して速度ベクトルを決める

きちんと出す（TODO昔書いた記事のURLを書く）のが面倒だったのでてきとう

流れを考慮

てきとう（-2*field.flowVel()）にやった

加速しなくても目標の蓮に同じターン数以下で到達できるなら加速しない

加速したら次のターンで先輩忍者にぶつかる場合は加速回数が余っていない限り加速しない

やってないこと

蓮の位置を考慮して何回ごと加速すればよいか決める

ちゃんとやれば1〜2万点はあがりそう

上位と差が付いたのはたぶんここ

len(hoge)をメモ

すぐできるし、これはやったほうが良かった（ボトルネックになってる）

スタート直後の最適化

無理でしょ

ゴール直前の最適化

めんどいんじゃ

流れをちゃんと考える

めんどいｎ（ｒｙ

先輩忍者をちゃんと考える

めんｄ（ｒｙ

次の次の蓮をちゃんと考える

ｍ（ｒｙ

マジックナンバー

10ターンごとに加速

Parameter::CharaAddAccelWaitTurn

-2*field.flowVel()

2*Σ_{i=0}^9(0.875-0.0625*i)/0.875が13.5くらいなのでnormalizeとかすれば10くらいになって良さそう

ちゃんと確かめたわけじゃないのでてきとう

その他

100ステージ×100ケースでパラメタ調整した

ツイートする