TopCoderの学習のお時間

2016-11-14

■ [CodeChef]November Challenge 2016 00:48

https://www.codechef.com/NOV16

最後の問題までやる時間とれないですねえ…

Task for Alexey(ALEXTASK)

最小公倍数

https://www.codechef.com/viewsolution/12015223

Chef and squares(CHSQR)

F(K) の上界が K/2 であることはすぐにわかって、次のように K/2 になる例が構成できるので F(K) == K/2

4 5 1 2 3
3 4 5 1 2
2 3 4 5 1
1 2 3 4 5
5 1 2 3 4

5 6 7 1 2 3 4
4 5 6 7 1 2 3
3 4 5 6 7 1 2
2 3 4 5 6 7 1
1 2 3 4 5 6 7
7 1 2 3 4 5 6
6 7 1 2 3 4 5

https://www.codechef.com/viewsolution/12015468

Count Permutations(CPERM)

i=k の場合が何通りか == iよりも左の(k-1)個に 1〜N-1のうち何個を割り当てるか == C(N-1,k-1)

なので、 i=1,2,...N の場合を足し上げると C(N-1, 0) + C(N-1,1) + ... + C(N-1,N-1) = (1+1)^(N-1)

なので、求める答えは i=1,N の場合を除いた 2^(N-1)-2

https://www.codechef.com/viewsolution/12015546

Gift and Chef(GIFTCHEF)

S上のマッチ箇所を列挙してからDP

文字列のマッチはローリングハッシュでやったら、ハッシュ衝突するテストケースが含まれてたみたいでやたら時間かかった…。せっかくSuffixArrayライブラリ持ってるのだからそっち使っとくべきだった

https://www.codechef.com/viewsolution/12016700

Friends Meeting(FRIEMEET)

木DPですべてのあり得る経路の合計長を求める

https://www.codechef.com/viewsolution/12017157

Urban Development(URBANDEV)

y軸方向のどの座標にhorizontalな辺があるかをBITで持ってx軸方向に平面走査

各辺が交差する回数を出さないといけないのでxy入れ替えて2回やる

https://www.codechef.com/viewsolution/12028457

Kirito in Memeland(KIRMEME)

なんか重心分解とかでできそうなんだけど、よくわからないので独自なアルゴリズムでがんばっていた。

各ノードにBITを2つ持たせて Weighted Union Heuristics で木DPをする。

2つのBITは、それぞれ次の値を持つ。

そのノードの子孫（自身含む）で始まり、そのノードで終わる経路のうち最後の移動で標高が上がっているもので、経路の中に「上がって下がる」をi箇所含むものが何個あるか
上と同じ経路のうち、最後の移動で標高が上がっていないもの

BITに先頭へのadd（既存の要素は1つずつ後ろへshiftされる）をサポートさせる必要があったので、ただのBITではなくて改造を加えた。

最初はサイズに余裕を持たせておいて配列の途中から使い、先頭へのaddのときは前側に伸ばしていって、いっぱいになったらキャパシティを2倍にしてコピーする、といった実装にした（vectorの伸長みたいな）。

O(N logN^2)

https://www.codechef.com/viewsolution/12075326

Bear and Shuffled Points(BIKE)

行列累乗で部分点のみ

https://www.codechef.com/viewsolution/12082386

Sereja and Permutations 3(SEAPERM3)

手つかず

Sereja and Ways in the Cube(SEAWCU:タイブレーク)

DFSしただけ

https://www.codechef.com/viewsolution/12099756

34.069点

~~上位のスコアが理論限界超えてる気しかしなくて何かがおかしい（ソースをチラ見したけどわからず…）~~

【追記】自分のコードがバグってるだけでした…

結果

764.069pts/1000pts
28位/4143人

2016-10-18

■ [CodeChef]October Challenge 2016 17:35

http://www.codechef.com/OCT16

ひさしぶりに参加した。ちょうど良い難易度だった。

Chef and Keyboard(CHEFKEY)

やる

https://www.codechef.com/viewsolution/11712752

Chef and Three Dogs(CHDOGS)

Three Dogs Problem でググると http://mathworld.wolfram.com/MiceProblem.html に行き着く

https://www.codechef.com/viewsolution/11712881

Fenwick Iterations(FENWITER)

実験するとわかる

https://www.codechef.com/viewsolution/11764653

Chef and Two String(CHEFTWOS)

2を使うのは次のように 2,2,1 と並んでいる形しかありえない

2 2 1 ?
 --->
  <-
   --->

2が何個連続しているかを状態としてDPする。終端でぴったり終わらないといけないので最後だけちょっとややこしい

https://www.codechef.com/viewsolution/11766059

Big Queries(BGQRS)

遅延更新するSegmentTree。

各ノードに次の値を持たせる

配下の範囲に含まれる2の数,5の数の和
配下の範囲すべてに共通して含まれる2の数,5の数
配下の範囲がクエリ2によってひとつの等差数列に含まれているなら、その先頭の値

https://www.codechef.com/viewsolution/11770129

Sereja and Stones(SEASTONE)

石の配分を固定したとき、Eが大きい箱にたくさんの石を置くようにするのが最適なので、箱はEの値でソートする。

Eが最大の箱にすべての石を入れる、またはできるだけフラットになるように石をすべての箱に分配する、という戦略が良い上限になっているようで、枝刈り探索で十分早く答えが出た。メモ化もせず0.38秒。

forumによると、DPを加速する方針の計算量が保証できる解答もあるらしい

https://www.codechef.com/viewsolution/11790150

Power Sums(POWSUMS)

https://ja.wikipedia.org/wiki/%E5%AF%BE%E7%A7%B0%E5%BC%8F#.E3.83.8B.E3.83.A5.E3.83.BC.E3.83.88.E3.83.B3.E5.A4.9A.E9.A0.85.E5.BC.8F

このあたりを使うと、与えられた情報からN変数の基本対称式の値がすべて求まる。

それを元に、a_i が満たすべきN次モニック方程式が出るので、きたまさ法を使って a_i^x の次数を落とせる。

https://www.codechef.com/viewsolution/11719575

Bear and Shuffled Points(GEOCHEAT)

逆向きに、すべての点がある状態から一つずつ取り除いていくと考える。

最遠点対は、凸包を作ってキャリパー法すると O(NlogN) でわかる。

取り除く点が最遠点対に一致したときのみ再計算する。点がランダムに並び替えられていることから、再計算は頻繁には起きないのでこれで間に合う。

ちなみに N=750000 のとき、再計算回数の期待値を計算してみると28くらいだった。

なおキャリパー法を蟻本を元に実装したら、停止しないケースがあって焦った。とりあえずアドホックに対応したけど、もうちょっとちゃんと対策しておかねば。

https://www.codechef.com/viewsolution/11864670

Tree Balancing(TREEBAL)

考える時間が無くて自明な部分点のみ。

https://www.codechef.com/viewsolution/11865084

Sereja and Progressions(SEAARI:タイブレーク)

まずは絶対値が大きい順にD個取り除く。

残りの値の最小値が配列の左端、最大値が右端にくるとして、それらを結んだ直線を仮の回答とする。

その直線からのずれが最も大きい位置を交換元とし、交換元の値が本来あるべき位置の周辺を探索し、入れ替えたときに最もコストが減少する位置を交換先とする。これをK回行う。

PriorityQueueを使って1回の交換あたり O(logN) で処理する。

https://www.codechef.com/viewsolution/11867199

83.106点

結果

893.106pts/1000pts
9位/6517人

2016-08-15

■ [ICFPC] ICFP Programming Contest 2016 12:46

例年のように会社の人たちと参加した（チーム名：fixstars）。6人で合宿。

やったこと

ソルバ作成

紙を開いていくという王道な方針のソルバは他の人がやっていたので、違う方法を考える。

入力のskeltonを最小の多角形に分解して、それらを1x1の正方形になるように敷き詰める、という方針にした。

2日目の昼くらいには何となく動いて、雑魚問は解けるようになった。

ただ指数オーダーなのでちょっと入力が複雑になると全く無理。

改善しようとしたけどたいして良くはならず、解ける問題のうち最も複雑なのはこの程度でした（problem id 285）

出題用の問題作成

2日目の夜に寝ながら考えたら、どうやら問題を解くよりも出題のほうがスコアに占めるウエイトが大きそうなことに気付いた。

その時点で自チームの出題は一応最後の分まで行われていたけど、けっこう解かれそうなので強化することにした。

Unagiの問題が強そうなので方針をパクる。折るのは90度か45度の線のみで、skeltonの線がたくさん重なっているような非凸の図形だったら良い。

このシンプル仕様でも紙を折る実装が難しくて、生成器を作るのに8時間くらいかかってしまった。

ランダムに折りまくって適当に設定した評価関数にかけて良いのを出力する、というものだけど、評価関数だけではあんまり強いのを抽出できず、何十個か生成した中から人目で強そうなのを選別していた。

（でも結局数十個しか作らないのだから、GUIを用意して人力で作るようにしたほうが良かった気もする）

なんとか最後11問は、これで作成した問題に置き換えることができた。

Unagiのものほど強くはないけど、ひとつを除いてUnagiにしか解かれていないし、サイズも1000未満なので、1問2000点以上入ることになっていてまずまずといえよう。

はじめに提出していたやつは20チーム以上に解かれていたので、置き換えたことで2万点ほど得られたことになる。良かった（ただしUnagiに対してはアシスト）。

なんか「いかにUnagi以外には解かれなくてサイズができるだけ小さい問題を作るか」という競争だった気がする。

サイズが小さいと解くうまみが少なくて、人力部隊のターゲットから外れやすくなるという効果もありますね。

ちなみに作ったのはこんなやつ（problem id 5607・5638）。

問題一覧作成

ソルバを作る過程でデバッグ用に問題を画像出力していたのを流用して、各問題がどんな見た目をしているかの一覧を作成した。

ちゃんとデプロイする環境を用意しなかったので、自分以外にはあまり活用されていない感

反省・感想

よかったこと

めっちゃでかいホワイトボードがあって活躍した
合宿先からコンビニが近いと便利
朝食がバイキングだったので時間に縛られづらく、朝食を取らない人の罪悪感も減じられた
睡眠時間は1日5時間程度で、集中も続いて削りすぎずちょうど良いくらいだった
コンテストの形式が非常に良く練られていて、本質以外の部分でのストレスが無かった
たくさんソルバの実装ができた
- 例年あまりソルバ担当にならないので…
- 次回はインフラ方面やりたい

よくなかったこと

最後ソルバにバグが残ってることが発覚して、取り切れず諦めてしまったけど、後で考えてみたらそのバグが存在したのは「解答サイズを最小にするため多角形をマージする」という部分なので、必ずしも実行しなくて良いところだった。それに気付いていればバグの影響をかなり抑えられたはずだが…
バグが残っていることに気付くのも遅かった。ソルバとしては解が出たら満点のはずなのだから、それ以外になっている時点で即アラートを上げてもらうようにしておくべきだった
コンテスト全体としての戦略に対する考察が不十分だった。出題がかなり重要であることにもっと早く気付いていたら、あと5万点くらい違っているはず
会議室の鍵がひとつしかなくて扱いづらかった（一人だけ先に寝ておいて早起きしてくる、みたいなのがやりづらい）

そのほか

「これyowaさん問題専用ソルバあってよいよね」「でも自分らでやりたくないよね」「だれかやってくれないかな」とずっと思っていたら天羽々斬がやってくれていた。ありがとう
モダン焼フジ、学生の頃に気になってはいたけど結局行ったことがないままだ

2015-12-01

■ [部活]すごいサブミット 00:42

これは Competitive Programming （その2） Advent Calendar 2015の1日目の記事です。

Advent Calendarの基本に返って、すぐ書ける記事にします。

これまでにコンテストで見た、印象に残ったサブミットを列挙します。

他人のコードを勝手に紹介することをお許しください。

SRM436

https://community.topcoder.com/stat?c=problem_solution&rm=300564&rd=13698&pm=10336&cr=10597114

想定解がFFTの問題だったのですが、インラインアセンブラで気合いで通しています。

1発ACを要求されるSRMで、36分でこのコードを書いて通すのは、当時の界隈にかなりの衝撃をもたらしました。

2010 TCO Marathon Round 2

https://community.topcoder.com/longcontest/?module=ViewProblemSolution&pm=10989&rd=14273&cr=22696357&subnum=8

このマラソンマッチは完全なる高速化ゲーでした。

というわけでJITです。

Marathon Match 78

https://community.topcoder.com/longcontest/?module=ViewProblemSolution&pm=12444&rd=15570&cr=21688563&subnum=13 （重いので注意）

圧勝した人のコードです。

皆が焼きなます中、Pythonで遷移パターンを列挙して埋め込んでDPしたみたいです。

NSA Marathon Match Event 1

https://community.topcoder.com/longcontest/?module=ViewProblemSolution&pm=10676&rd=14176&cr=7462740&subnum=3

これはコードよりも順位表を見てもらった方が良くて、訳が分からない点差が付いています。

これは暗号解読の問題だったのですが、どうも一人だけまともに解読できたらしいです。

コードで何をやっているか読めた方は来年のAdvent Calendarのネタにでもすると良いのではないでしょうか。ぜひしてください。

AtCoder Regular Contest #030

http://arc030.contest.atcoder.jp/submissions/286413

コードを見ても何をやっているのか分からないと思いますが、見るべきは提出時間で、コンテスト開始3秒後にサブミットされてACを取っています。

サンプルから解答を推測するプログラム、なのでしょうか？？

お誕生日コンテスト

http://birthday0410.contest.atcoder.jp/submissions/128080

http://birthday0410.contest.atcoder.jp/submissions/127943

これも順位表を見てもらった方が良くて、WA回数が大変なことになっています。

問題の性質的に、インプット解析でがんばれてしまったのですね…。

なおこのようなひどい（褒め言葉）問題であるにもかかわらず、まともな方法で満点を得ているサブミットもあってこちらもすごい

http://birthday0410.contest.atcoder.jp/submissions/127561

おわりに

ほかにも興味深いコードがあったら教えてください！！

2015-08-10

■ [ICFPC]ICFP Programming Contest 2015 01:58

例年のように会社の人と合宿して参加した。5人チーム。

やったこと

テトリス AIだったので、まあビームサーチかなということでまずは下に落とすだけのソルバを書いた。

2日目の午前中くらいには回転なし版がそれなりに動いて、あとはライトニングの提出に向けて回転を足して調整したり高速化したりで2日目終了。

3日目には他の人たちもソルバを拡張し始めていて、あまり他の人がコードをいじるようなつもりで書いていなかったのでアッアッ…という感じだったけど、そこで手を出してしまうと同じコードを同時に複数人で変更することになってカオスになるのでソルバの拡張は任せることにした。

公式の順位表が重くて見づらいことに嫌気がさして、ダウンロードしてきて適当にフォーマットして表示するようにした。

公式順位表のデータ部分はJavaScriptで生成されているようだったので、 Seleniumでブラウザ起動して取得→重すぎ casperjsでサイレント実行して取得→なぜかcronで実行するとうまく取れないとはまっていたけど、実は https://davar.icfpcontest.org/rankings.js をダウンロードしたら順位表データが全部入っていた…。時間をだいぶ無駄にしてしまった。

あとはビジュアライザのスクリーンショットを順位表と合わせて表示するようにした。どのような盤面はどのくらいのスコアが出ていて、ライン消すのかPowerをたくさん狙うのかどちらがよさそうかなどを判断する情報になってくれたかもしれない。

それと各チームのベスト記録を元にした潜伏なし版ランキングも作っていたので、Unagiチームの強さはだいぶ早いうちから知ることができていた。

最終日はソルバのコードもだいぶ読めない感じになってきていて、Power探しシステムが完成していたこともあり、Powerの文字列候補のネタ出しをしていた。

Wikipediaからクトゥルフ関連の単語を大量に取ってきて投げたけど、その後で公式Twitterに「Wikipediaからコピペしてんじゃねーよ」みたいなことが書かれているのに気付いた…。

最長のPowerの長さが51文字ということで、ストーリーの文書からちょうど単語区切りが51文字になっている部分を全列挙して眺めてみて、「a new representation for ancient protection schemes （, called davar）」というとてもそれっぽい箇所があるのを発見するものの、「ep」と連なっているところが→,←の順での移動だから活用するのはほぼ無理だね、となって試さなかった（結局全然違っていた）。

時間の最後のあたりでソルバの重複盤面除去が甘いことに気付いて（自分が初期に入れたコード）直したりほかのデバッグの手伝いをしたりしていた。

例年と同じく最後はちょっと慌てたけれど提出完了。

反省

特によかったこと

最初に問題内容の理解を全員で合わせる機会を持った
かなり早いうちにビジュアライザができていたので作ったコードの動きが見えてやる気が上がった
Power探索がシステム化されて候補を探すのが効率的だった
ホワイトボードを有効活用できた
- 合宿先に4枚もあった
(個人的に)食事以外ではほとんど間食せず、それなりに睡眠も取って健康的だった。コードが書けたおかげで体調良くなった

そのほか

早いうちにやっておくべき事に着手するのが遅めだった
- Power探しは公式ジャッジサーバーに提出して結果が出るまで待たないといけないのでどうしても時間がかかる。2日目の夜はまだPowerの候補を出していなくて公式ジャッジのリソースが遊んでいたのがもったいなかった
- 順位表データはとりあえず保存しておくだけでも先にやっておきたかった。各チーム、ライトニング終了時点ではその時点でのベストスコアを出しているはずだけど、だいたいその後Power探しになって順位表がぐちゃぐちゃになるので、実際各ケースで最大どれだけのスコアが取れるのかがわかりづらくなってしまった
役割分担をそこまで厳格には決めなかった
- 本当はAI書く人は最初からずっとそれだけやるのが良いんだろうけど、まあみんなコード書きたいだろうし
- あんまりぎちぎちにしてしまうのはコンテスト参加の楽しみという点では辛いので
AIのパラメタ振り
- 盤面の特徴がさまざまなので1つのAI プログラムで対処するのが難しくて、ソルバのいくつかのバリアントで実行してベストの物を使えるように…
- という話はしていたが結局あんまりバリアント作れなかった（実際それで良くなるのかどうかはわからない）。
テスタは別途作っておくべきだった
- 手元での評価用に、正確に実行することだけを考えて作成したシミュレータを用意しておくべきだったように思う
- サーバーに回答（またはコード）を提出して結果を得る方式だと扱いづらいので。公式がバグってることもよくあるし…
開始前に「プログラムに名前をつけよう」と言っていたのを達成できなかった。特に好きなキャラクターとかないのが難しい