Hatena::Grouptopcoder

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

 | 

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でポチポチ設定して起動することもでき、その画面から同等のコマンドを取得することができます。

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

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/machy3/20180508
 |