Hatena::Grouptopcoder

not's memo

2015-08-06

yukicoder No.262 面白くないビットすごろく

23:48 | はてなブックマーク - yukicoder No.262 面白くないビットすごろく - not's memo

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


用意していた問題

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

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

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


解法

続きを読む

2015-06-27

ICPC2015国内予選「G問題」参加記

00:30 | はてなブックマーク - ICPC2015国内予選「G問題」参加記 - not's memo

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

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

続きを読む

2014-12-09

幾何の小手先テクn選

22:18 | はてなブックマーク - 幾何の小手先テクn選 - not's memo

これは、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以下しか動かないのでどっちから来たか簡単に分かります。

モンテカルロ法

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

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

2014-11-28

ハル研究所プログラミングコンテスト2014参加記

09:58 | はてなブックマーク - ハル研究所プログラミングコンテスト2014参加記 - not's memo

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


提出したコード

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


方針

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

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


やったこと

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

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

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

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

最後の一手なら加速

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

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

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

流れを考慮

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

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

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

やってないこと

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

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

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

len(hoge)をメモ

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

スタート直後の最適化

無理でしょ

ゴール直前の最適化

めんどいんじゃ

流れをちゃんと考える

めんどいn(ry

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

めんd(ry

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

m(ry


マジックナンバー

10ターンごとに加速

Parameter::CharaAddAccelWaitTurn

-2*field.flowVel()

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

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

その他

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

2014-10-22

~shiokawaのチーム体制について

07:30 | はてなブックマーク - ~shiokawaのチーム体制について - not's memo

こんなどうでもいい記事を読む前にiwiwi大先生の偉大な記事を読みましょう!!!!

背景

チーム解散から1年経っても未だに「~shiokawaは良いチームだった」と言われることがあるので、当時どういうことを考えていたのかを公開するのは価値があるかなと思って記事にしました。

チーム体制

~shiokawaは基本的に3並列で問題を解いていました。

3人ともあえて得意分野が被らないように練習していて、問題を読めば誰が書くべきかわかるくらいの感覚でした。

問題共有・解法検討が終わったあとは基本的に1人で実装詰めてコーディングしていました。

ただし、最終盤は解く問題を1問か2問に絞って確実に通す方針に切り替えていました。

場合に依ってはkawateaさんとshioshiotaさんのペアプロとか全員で1問にとりかかるとかすることもありました。このへんは状況次第。

印刷

~shiokawaと言えば印刷、というくらい印刷しまくっていました。

基本的にバグったり交代したりする際にはとりあえずコードを印刷し、デバッグなり見直しなりがすぐにできるようにしました。

時には印刷が来る前にデバッグが終了し、来たコードをそのまま捨てることも。

印刷・clarはコンテスタントに与えられた権利なので最大限利用しましょう。

練習量

2012年は会津の練習会に週2くらいで参加させてもらっていました。

2013年は個人練習を重視しようと思って週1くらいで地区大会の過去問を解いていました。

量よりも質だとは思いますが、それでも週1くらいはやったほうがいいと思います。楽しいし。

チーム戦略はどれくらい重要なのか

個人的にはチーム戦略によって3時間セットで1問・5時間セットで1〜2問くらい最大で変わりうると思っています。

逆に言うとそれ以上は個人の力の差なので、その差を埋めようと思うならチーム練習より個人練習を重視したほうがいいと思います。

もっとも、チーム練習をすることでチームメンバーの知識を吸収できるので個人の能力が上がる可能性もあります。

個人練習でそれぞれ違う方向に知識を深め、チーム練習でそれを共有するというのが理想的だと思います。

使えそうなテクニック

誰もキーボードを触らない時間がなくなるように、多実装系・ライブラリゲー・幾何などを走らせつつ他の問題で実装軽そうなのがあれば交代する方針になることが多かったです。

バグってもキーボードが空くことはない、というのは心理的にとてもゆとりがもてるのでおすすめです。


問題読んだ人はコーディングまでやってしまったほうが良いと思います。

もちろん全員コーダーだからそんなことが言えるわけですが、細かい条件まで含めてきっちり伝えきるのは難しいので読んだ人が書くのが結局ロスは少なくなります。

しかし得意分野もろもろの都合もあるのでそうできない場合は、ペアプロなりで補完しました。


チームメンバーに遠慮しないってのはかなり大事です。

彼らは運命共同体なので「いま他のこと考えてるな〜」とか「こんなつまらないバグに付き合わせるのは申し訳ない」とかそういう気持ちは捨ててチームとしていい戦略を取りましょう。


チーム戦中にいま暇だな〜と思うことがあるなら、それはチーム戦略をミスったか問題のレベルが高すぎます。

とりあえず問題文を読み直すくらいはしましょう。

まとめ

チーム練習楽しいからみんなもっとしよう!

gl&hf!