|
出題しようと準備していた問題が想定TLE解法で出題されてしまって、とても悲しい気分になったので解説を書きました。。。
Xから立ってるビットの数だけ足すというのをK回くりかえすと何になるか？
X,KはT個与えられる。
X,K<10^17, T<10^5
|
これは、Competitive Programming Advent Calendar Div2014の9日目の記事です。
誤差死したときはlong doubleにし、TLEしたときはdoubleにできるように最初からtypedefしておくと便利です。
座標の範囲が[-1000:1000]だとEPS=1e-8を使うというのを基準にしていて、相対誤差っぽく[-10000:10000]だとEPS=1e-7とかにすると苦しむことが減ります。
与えられた全ての点を原点を中心に少しだけ回転させる。
スラブ分割（コンピュータ・ジオメトリ P.149）する時など、x座標が同じ頂点があって縮退している場合に縮退が解けます。
例題：最終防衛線
上と同じタイプの縮退が解けます。
座標に小さな乱数（ただしEPSよりは十分大きい）を追加して縮退を解く。
ただし、実際に値を出すときは縮退前の座標を使わないとちょっとずれてWAの原因になります。
小手先でゎない。
混乱を避けるため、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));}
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));}
-EPSを突っ込んで死ぬのを回避。
inline Real sr(Real a) {return sqrt(max(a, (Real)0));}
円と線分をグラフに落とすときにc.c+polar(c.r, PI/2*i)を頂点に追加しておくと便利なことがあります。
円周上をPI/2以下しか動かないのでどっちから来たか簡単に分かります。
どんな面積でも簡単に求められることで有名。
というのはさすが冗談で、例えばサブミットデバッグするときに答えが大きくずれているかのチェックができたりします。
|
※この記事は結果発表前に書いています
https://gist.github.com/not522/9a398898d258b24a4512
忙しくて時間がなかった（実際にかけた時間は12時間くらい）ので楽に点数が上がりそうなのだけ実装する
そもそもかなり自由度が低いゲームなので、貪欲でもそこそこの点数が得られそうと予想していた
player.accelCount()を見て適宜調整
基本的には2個くらい残す
離れていってるなら残り1個だろうと加速
きちんと出す（TODO昔書いた記事のURLを書く）のが面倒だったのでてきとう
てきとう（-2*field.flowVel()）にやった
ちゃんとやれば1〜2万点はあがりそう
上位と差が付いたのはたぶんここ
すぐできるし、これはやったほうが良かった（ボトルネックになってる）
無理でしょ
めんどいんじゃ
めんどいｎ（ｒｙ
めんｄ（ｒｙ
ｍ（ｒｙ
Parameter::CharaAddAccelWaitTurn
2*Σ_{i=0}^9(0.875-0.0625*i)/0.875が13.5くらいなのでnormalizeとかすれば10くらいになって良さそう
ちゃんと確かめたわけじゃないのでてきとう
100ステージ×100ケースでパラメタ調整した
|
チーム解散から１年経っても未だに「~shiokawaは良いチームだった」と言われることがあるので、当時どういうことを考えていたのかを公開するのは価値があるかなと思って記事にしました。
~shiokawaは基本的に３並列で問題を解いていました。
３人ともあえて得意分野が被らないように練習していて、問題を読めば誰が書くべきかわかるくらいの感覚でした。
問題共有・解法検討が終わったあとは基本的に１人で実装詰めてコーディングしていました。
ただし、最終盤は解く問題を１問か２問に絞って確実に通す方針に切り替えていました。
場合に依ってはkawateaさんとshioshiotaさんのペアプロとか全員で１問にとりかかるとかすることもありました。このへんは状況次第。
~shiokawaと言えば印刷、というくらい印刷しまくっていました。
基本的にバグったり交代したりする際にはとりあえずコードを印刷し、デバッグなり見直しなりがすぐにできるようにしました。
時には印刷が来る前にデバッグが終了し、来たコードをそのまま捨てることも。
印刷・clarはコンテスタントに与えられた権利なので最大限利用しましょう。
2012年は会津の練習会に週２くらいで参加させてもらっていました。
2013年は個人練習を重視しようと思って週１くらいで地区大会の過去問を解いていました。
量よりも質だとは思いますが、それでも週１くらいはやったほうがいいと思います。楽しいし。
個人的にはチーム戦略によって３時間セットで１問・５時間セットで１〜２問くらい最大で変わりうると思っています。
逆に言うとそれ以上は個人の力の差なので、その差を埋めようと思うならチーム練習より個人練習を重視したほうがいいと思います。
もっとも、チーム練習をすることでチームメンバーの知識を吸収できるので個人の能力が上がる可能性もあります。
個人練習でそれぞれ違う方向に知識を深め、チーム練習でそれを共有するというのが理想的だと思います。
誰もキーボードを触らない時間がなくなるように、多実装系・ライブラリゲー・幾何などを走らせつつ他の問題で実装軽そうなのがあれば交代する方針になることが多かったです。
バグってもキーボードが空くことはない、というのは心理的にとてもゆとりがもてるのでおすすめです。
問題読んだ人はコーディングまでやってしまったほうが良いと思います。
もちろん全員コーダーだからそんなことが言えるわけですが、細かい条件まで含めてきっちり伝えきるのは難しいので読んだ人が書くのが結局ロスは少なくなります。
しかし得意分野もろもろの都合もあるのでそうできない場合は、ペアプロなりで補完しました。
チームメンバーに遠慮しないってのはかなり大事です。
彼らは運命共同体なので「いま他のこと考えてるな〜」とか「こんなつまらないバグに付き合わせるのは申し訳ない」とかそういう気持ちは捨ててチームとしていい戦略を取りましょう。
チーム戦中にいま暇だな〜と思うことがあるなら、それはチーム戦略をミスったか問題のレベルが高すぎます。
とりあえず問題文を読み直すくらいはしましょう。
チーム練習楽しいからみんなもっとしよう！
gl&hf!
