Hatena::Grouptopcoder

横道にそれるTopCoder参加記録でもいいじゃないか

2018-06-04AtCoderでイエローになるまでにしたこと このエントリーを含むブックマーク

最近は少し精進を意識しています。

理由はよくよく考えてみると、ステータスになるからというモチベーションが大きい気がします。


・問題を解けるようにする

こちらは復習が基本になるかと思います。わかっててもなかなかできないやつです。

あとは作問したり、性質について洞察を深めるのも楽しくて有効かと思います。


・バグの発生を防ぐ

問題は解けていても、バグのために時間を浪費するのはなるべく避けたいものです。

intを使わず、すべてlong longを使うことにしました。今までそれが理由でメモリ不足になったりTLEになったことはありません。

組み合わせ数の計算はModIntクラスを作って、剰余を取り忘れたり、そのバグを疑って時間を浪費するのを避けるようにしました。

vectorもat()でバウンダリチェックしたいのですが、タイプするのが面倒でoperator[]を使ってしまっています。


・環境を整える

本当はIDEを使ったほうがいいんだろうなと思いつつ、vimmerしています。

テンプレートを整えたり、コンパイルの短縮エイリアスを使ったりするようにしました。

最近知って便利なのがpbcopyというクリップボードにコピーできるMacOSのコマンドです。

使い方は

cat A.cc | pbcopy

です。

いままでcatしてターミナルから文字を選択してコピペしていたので、提出するごとに長いときは10秒以上掛かっていたのが短縮できました。効果としては大きい部類だと思います。


・再利用する

中身の書き方を忘れたライブラリを使うのは何となく悲しくてライブラリは極力使わない主義だったのですが、最近はいくつかのライブラリを用意するようになりました。

問題を解くという行為に集中できるようになったのはメリットとして感じています。

そしてやはりcombinationをイチから書くと5分くらい掛かってしまうので、時間短縮の効果があります。

2018-05-18

TCO Marathon R1 Roads And Junctions 参加記録

00:08 | TCO Marathon R1 Roads And Junctions 参加記録 - 横道にそれるTopCoder参加記録でもいいじゃないか を含むブックマーク はてなブックマーク - TCO Marathon R1 Roads And Junctions 参加記録 - 横道にそれるTopCoder参加記録でもいいじゃないか

provisional 112位

6位→10位→112位なので次は1000位くらい取るのではないか

順位が芳しくなかったので参加記録は短くなる。


■反省するしかない

MSTをして、そこからフェルマー点などにJunctionを置いていく。cityの位置を少し動かして異なる初期SpaningTreeを作って、そちらでもJunctionを置いてみるという初期方針を立てました。

ポイントはcityの位置を少し動かしてMSTをやるという点。MSTから辺を適当に付け替えるよりマシなTreeが得られるでしょうということでそうしました。

これだとJunction候補点逃しそうだなと思ったものの、とりあえず組み始めてしまった。


そうしたら作り終わった時点で残り1日でした。

途中、standingsでどんどん抜かされていく様子をみて、恐らくランダム配置ベースの手法わりと上手くいくのだろうと推測するも、辺交換による長さ期待値の厳密計算を実装したのを捨てきれずどっぷりバグの沼にはまってしまう。

典型的なマラソンマッチのハマり。


■業務中はしていません

金土日と予定がありましたが、かけた時間はLighting Roundより多かったのではないでしょうか。

しかし平日、業務のあと帰宅してからはとてもしんどい。

私の能力は時間ではなく一日に使える体力で制約されているのを感じます。


土曜日、久々に会ったバイト時代の先輩から、ツイッターで熱心そうに見えるので業務中にマラソンマッチをやっているのではないかと疑われる。

断じて、業務中はやっていません。

2018-05-08

TCO Marathon Poland Lightning Round 参加記録

22:09 | TCO Marathon Poland Lightning Round 参加記録 - 横道にそれるTopCoder参加記録でもいいじゃないか を含むブックマーク はてなブックマーク - TCO Marathon Poland Lightning Round 参加記録 - 横道にそれるTopCoder参加記録でもいいじゃないか

登録者数はMM100より少ないものの、明らかにメンツが強そうなんだよなあと思っていたら、やっぱりMM100より順位がよくありませんでした。

このメンツでprov9位なら上出来だけど、topcoderのマラソンマッチは過去最高3位なので2位以内が欲しい。欲張り。


■スタート

5/5 10:00 ゴールデンウィークのちからを使い1,2日目はフル参加を決め込む。問題にたどり着けませんでしたが、koyumeishiさん、iwashiさん、大樹さんがリンクをツイートしてくれたので事なきをえました。


■t-macさんに初メール

スコアリングが気になっていたところ、forumにt-macさんが問題に関係しそうなことは個別に聞いてね、と投稿があったので勢い余ってメールで尋ねる。何とか英語が通じた模様。しかしt-macさんも勘違いしていたようですが、結局C_your * P_yourを最小化すればいいだけで、正規化係数は戦略には影響しませんでした。


■解法と反省

塗り直しが少なくなるように盤面を作り、それをなるべく壊さないように色を減らして行きました。色を減らすには四色問題を調べてケンプの鎖(2色の交互をそっくり入れ替えて他の色を使う余地をつくる)という方法を使いました。

「なるべく壊さないように」とか美しくなさがあふれているのが反省点。

なぜこんな発想になったかというと、この問題は焼き鈍しにくいと決め込んでしまったから。

でも終了後のタイムラインを見ていてそれが間違いだと気づきました。

焼き鈍しにくいのは必要最小限の色を使って、さらに色を減らそうと頑張った場合。そういうときは盤面の色同士がギチギチに関連し合ってしまって身動きがとれなくなってしまう。

しかし色数に余裕があったり、色数が少なくてもそれ以上色を減らそうと頑張っていなければ、焼き鈍す余裕は十分あったはずです。

気づいてしまえば何で気づかなかったんだという話だけど、決め込んでしまうのがマラソンマッチの怖いところ。きっと四色問題が頭にあったからでしょう。

ケンプの鎖もvalidなmoveは作りやすそうですが、recoloringを減らすという目的と相性がわるそうです。

それでも暫定9位だったのは幸運でした。


■初課金プレイ

いわゆる課金プレイ、つまりクラウドを使いました。awsではなくgoogle cloudを使うことにしました。理由はgoogle cloudのほうが多少割高なものの課金の時間単位が短く、10分などで切り上げる分にはgoogle cloudのほうが安上がりのようだったからです。

利用を開始すると3万円分のクーポンがついてきますが、有料アカウントにアップグレードしないと、8CPUまでしか利用できません。

私は有料アカウントにして20インスタンスで並列テストしました。

ほったらかしにしたらいくら課金されるのかと怖くなりますね。

やり方は

gcloud compute scp hoge.cc instancename:/home/machy/

でソースコードとテスト設定を送り込み、

gcloud compute ssh instancename --command="make -f /home/machy/Makefile"

などとしてmakeと実行をして、再びscpで実行結果を取得しました。

環境は一度構築してイメージにしておき、

gcloud compute instances create instance-1 instance-2 instance-3 ... --image=imagename

とすれば同じイメージで複数のインスタンスを同時起動できました。インスタンスの起動がかなり速い!(20秒かからないくらい)のもawsと比較したときのgoogle cloudの特徴のようです。

GUIでポチポチ設定して起動することもでき、その画面から同等のコマンドを取得することができます。

プリエンプティブインスタンスを使えば安く済みますが、何回かテストする間にも勝手に終了して一部結果が得られないことがありました。

2018-04-27

MM100 SameColorPairs 参加記録

09:13 | MM100 SameColorPairs 参加記録 - 横道にそれるTopCoder参加記録でもいいじゃないか を含むブックマーク はてなブックマーク - MM100 SameColorPairs 参加記録 - 横道にそれるTopCoder参加記録でもいいじゃないか

わりと順位が良かったので長くなる。


・greedyの前に、ちょっとだけ考察を…

土曜日。開封の儀式的にサンプルコードをvisualizerにかけてみる。それからサンプルコードにちょっとだけ手を入れてスコア計算式を確認。visualizerも読んでみると、同じ色のセルの個数が偶数になるように調整されている。

まずは消せるペアを見つけて消すgreedyを実装すべきだと考えたが、そのまえに考察したくなってペンとノートを取り出す。

今回の問題はグラフで考えやすそうだ。いつも二次元グリッドであることを忘れてグラフとして解けないか考えてしまう。そうしたら範囲外参照の問題とおさらばできる。

しかし今回も矩形領域を扱うので、完全に二次元グリッドを忘れることはできなそうだ。(x, yで操作する必要がでてくる)

依存関係が閉路になってると消せないなと絵を書いてみるものの、ノードを足したり引いたりしたとき、閉路検出を高速にできるデータ構造なんて知らない。


・greedyでルールの確認

考察を続けたいが我慢して、消せるペアを見つけて消すgreedyを実装した。visualizerにかけ、ルールの認識に間違いがないことを確認する。

ここで意外と消えてることに気づく。

これは前半はどう進めても問題ないやつかもしれない。

提出 4/21 10:34 471,408点 85th ローカルテストの絶対スコア0.9531


・データ構造を決める

トポロジカルソート的に解きたかったので、参照カウント(そのセルが消えていることに依存する操作の回数)を用意した。

するとこの参照カウントには任意の順番でunmoveしても性質が維持されるという好ましい性質があることがわかって嬉しくなった。

これでiとj-kをi-jとkというペアに変更する操作が可能になった。

提出 4/21 17:31 760,923点 42nd ローカルテストの絶対スコア0.9870


・ダミーをまく

ここからどうするかだが、とりあえず状態遷移がスムーズになるようダミーをまくのが良かろうということで、作ったペアを解消する操作を取り入れる。

提出 4/22 09:35 836,207点 17th ローカルテストの絶対スコア0.99707

ここで明らかに点数が良くなっているのに、greedyに4/100も負けているのに気づく。greedyはパーフェクトを取っていた。

これはパーフェクトを取らなくてはならないゲームなのでは?


・中間状態をビジュアライズ

いままで面倒がってビジュアライザは与えられたものをそのまま使うことがほとんどだったが、Pillowというpythonのライブラリで動画gifを作ってみることにした。

意外とすぐ動いたが、どうもライブラリの選択は間違えたようだ。(フレームレートをあまり速くできない)

これでダミーの分量を目視で確認できるようになった。

そして提出したらびっくりの2位。

提出 4/22 13:43 871,086点 2nd ローカルテストの絶対スコア0.99598


・無駄骨だった高速化

操作可能か調べるためのデータ構造を半日かけて作るものの、全く速くならず。

唯一成果があったのが、ローカルテストを早くするための工夫。

パーフェクトになったら処理を中断するようにしたことと、ビジュアライザのデータ作成結果を保存してビジュアライザなしで評価するようにしたこと。(しかしこのせいで無効な解答をチェックできず投げつけて0点を取ってしまった)


・つらいチューニング

評価関数をためしたり、変化が起きやすくなるよう操作手順を工夫してみるものの、効果は上がらず。

結局効果があったのは、時間係数の変化をスムーズにした(それまで一画面操作するごとにだけ更新していた)ことと、ダミーをまく確率を調整したことくらい。

しかしローカルのテストではパーフェクト率が約95%から約97%に向上したので大きな違い。

制限時間を2秒→9秒にするとパーフェクト率は99.1%になったので、高速化できれば改善する余地はまだありそうだった。

それだけに、分割解法はなるほど!と大きな衝撃をうけた。分割すると問題が解きにくくなると考えて、無意識に棄却していたのでしょう。

2018-01-16

2018-01-16 Weathernews Programming Competition 参加記録

22:05 | 2018-01-16 Weathernews Programming Competition 参加記録 - 横道にそれるTopCoder参加記録でもいいじゃないか を含むブックマーク はてなブックマーク - 2018-01-16 Weathernews Programming Competition 参加記録 - 横道にそれるTopCoder参加記録でもいいじゃないか

まずはポエムから。

普段、試行錯誤を楽しみにコンテストに参加している身としては優勝を意識してからは本当にしんどい感じでした。基本的に勝負事に向いていないのだと思います。

潜伏という姑息な手段で形式的には勝ちましたが、shinhさんとまともにやっては勝てる気がしません。

潜伏したのは夜なべして競い合うのは辛いからという理由ですが、主催側としては出来るだけ良い結果が欲しかったと思うので申し訳ないし、shinhさんにも申し訳なかったなあと思います。

最終日は細かいチューニングは済ませてしまってあり、僅差でも抜かれてしまうと手立てがない状況でした。


それでも出来栄えとしては外注してもどこにも達成できないくらいの性能が達成できたと思います。さすが優秀なcompetitorが集まるAtCoderですね!

改善の効果は指数関数的に小さくなっているという印象でした。

200点差というのは流石に想定していませんでしたが、2,000点くらいの差で決着することは十分考えられると思っていました。

イメージですが、

もともとの1ピクセルが16bitで

出現する値の偏り 4.2bit

上、左、左上のピクセルとの関連性 4.5bit

異なる時間、周波数の画像との関連性 0.7bit (隣接ピクセルとの関連と重複する情報以外の部分)

を使って1ピクセル6.7bitになった、という感じです。

600秒という制限のなかでは、ここから1%(0.07bit)削るのはかなり大変という印象でした。


使用している技術は観測した範囲では他の参加者とあまり変わらないのかなと思います。

提出したコードはそれなりに読みやすくしたつもりなので、もし詳細気になる方は↓

https://wn2017_1.contest.atcoder.jp/submissions/1981642


私もDNN使ってみたいなと思いましたが、処理時間の関係で難しそうでした。

気をつけたのは、それでも非線形な処理を使おうということでした。

DNNなら活性化関数がそれに相当しますが、条件分岐でもいいから、あまり線形和の操作をしないこと。

S/N比の悪い情報をまぜてしまうとかえって圧縮率が悪くなってしまう。だからイメージとしては「5分前の画像と比較して動きが大きい箇所か、そうでないか」という情報を利用しようとか、そういうイメージで考えました。

実際にはそこまでヒューリスティックに処理しているわけではありませんが。


圧縮できるっていうことは、データに規則性があるということで、この世界の秩序がつまっているということで、とても魅力的なトピックだと思います。

shinhさんがPNGより随分優秀なファイルフォーマットを紹介していましたが、一度フォーマットが決まってしまうとなかなか代替が進まないのが、圧縮という分野の少し切ないところかなと思います。

貴重な機会を提供して下さったAtCoder社とウェザーニュース社に感謝しつつ、おしまい。