inani_waonの日記

コンテスト覚書

Topcoder MM139 - PipeConnector 参加記録

TopcoderのMarathonMatch139に参加しました。

www.topcoder.com

問題はPipeConnector。組み合わせと経路最適化の問題でした。

結果は72人中29位でした。

 

問題

グリッド上に色付きのノードがあり、1~9の数値が付いているよ。

同色のノード2つをパイプで繋ぐと数値の積の点が得られるよ。

複数のパイプが重なるとペナルティが付くよ。

 

参加記録の前に

めっちゃ長い苦情です。口うるさいので気に入らない方もいるかと思いますが、ご了承ください。

今回はC++のサンプルコードで誤ってtester解が公開されるというトラブルがあり、N回に一度の酷い回でした。サンプルコードを告知なしに入れ替えたことでまた別のトラブルになっていましたね…。*1

もちろんこのトラブル自体は開催者が起こしたもので開催者が悪いのですが、*2参加者側も混乱を起こしてアウト寄りの行動が目立っていたように感じました。

まずこのコンテスト参加の前提として、他者と協力してはならない、公平である必要がある、というものがあります。そして、『コンテストの内容に関係があり、他者の解法に影響が出る発言』をするのは他者との協力にあたり、また『一部の人間が知る』>『全員が知る』で不公平になると考えています。

ただし他者との協力とはみなされない例外があって、それは問題を解決するための質問や報告です。そういう報告にも、全員が見ることが出来るフォーラム、もしくは全員が見ることができない管理者へのメールを利用しましょう。twitterで言及するのは見る人間が限られるうえに問題の解決に直接繋がらないため、目的・影響の両方の意味で良くないです。

(具体的には、サンプルコードに異常があることを明示・暗示する発言は報告としてフォーラムか管理者メールへ書くべき、サンプルコードの点数への言及も議論目的なら同様、議論目的でないならそもそも言うべきではないと思いました)

また、フォーラムに出た内容は全員が知る内容なので日本語訳して転載・引用すること自体は大きく問題視していませんが、それに対する言及・質問でフォーラムに無い内容への言及に繋がっているなぁというのも感じました。これは翻訳情報があるほど言及が増えますし、フォーラムを直接読まないけど日本語情報が欲しいという人がいるほど翻訳情報の需要が増えて発信が活発化してしまうので、どんどん言及が増える負のループになってしまうところがあります。(そもそも、フォーラムを読まずにフォーラムに無い情報への言及を避けて話すのは不可能なので、翻訳情報を見てあれこれ話すという流れはおかしいのです)

なので、コンテストを壊さないためにも頑張ってフォーラムを読みましょう。必要なのは翻訳サービスを立ち上げる頑張りだけです。投稿するのは…こちらも翻訳サービスがあるとはいえ、私もまだ気後れしてしまいます。それでも『1文を短くする』『単一の解釈しか出来ない書き方をする』といったテクニックを使うことで、いざという時には最低限の発信は出来るかなぁ*3と考えています。

駄文おしまい。

 

考察&実装

とりあえず、大きい値同士を繋げば実スコアが大きくなるし、近い頂点同士を繋げば交差を減らせる気がする。頂点の組み合わせを全列挙&評価して、スコアの降順に貪欲に辺を張らせるところからスタート。1000件で平均966点。

(え、交差って平行に重ねるのもアリなんですか…?)

既にある辺を考慮して遠回りとか出来ると強そう。辺を削除して再度経路探索すればいいかな。これを10回繰り返して、更に空いた場所に辺を張りなおしてというのを3回繰り返してみる。平均1034点。

(3日コンだから短期寄りに、単純な解法の方が良いかなぁ)

雑に焼いてみる。近傍は辺の追加、削除、辺1本の経路再決定。1秒焼いて1067点。

辺2本が交差しているので解消したいなとか、{7, 1}と{3, 3}を{7, 3}と{3, 1}に変更したいなーみたいなのが結構ある。これを追加と削除だけで遷移させるのは厳しいので、2-opt風に頂点を交換する近傍を追加する。

これはかなり苦労して、遠くの辺同士を交換しても意味が薄いので近場に限定するとか、近場ってどう判定するのというので辺*辺の枝刈り探索で前計算したりした。前計算に1秒以上かかることもあるので、1秒測定が信用できなくなってくる。1082点。

積が6以下のペアって無視しても良くない?という悪魔のささやきが来る。確かに良さそうなんだけど、結果的には{7, 1}と{3, 3}を{7, 3}と{3, 1}に変更したいときに{3, 1}を構築出来ないので変更できないというのでスコアが悪化して没。

ここから手元テストを100件で回すことにする。この時点で100件で995点。

あとは温度調整と高速化がメイン。それ以外だと、辺追加の近傍は頂点が空いてないと出来なかったのを、既存のを壊して追加するというのを入れた。

(遠い状態に遷移する力が足りないし、近くへの遷移もたまに取りこぼしがあるなぁ)

焼き鈍しは今まで偽物の焼き鈍し*4を使っていたので、本物(?)の焼き鈍し*5を使ってみた。スコアの絶対量に対して変化が小さすぎると反映すべきかの判定がきついよなーと思っていたんだけど、今回は辺1本あたり1~81点の加算と交差ペナルティの減算ということで、スコア差分だけ見て計算するのがやりやすかった。性能はちょっと上がったかな。差によって採択率を大きく変えて、高温から始めるのが良いっぽい?

高速化パートでは、優先度付きキューが実行時間の半分を占めていたのでDial's Algorithmに変更したら該当箇所が3倍速以上になったとか、StateのCloneが重い*6のでRollBack可能な方式にしたら20倍速以上になったとか。優先度付きキュー、地味にボトルネックになりやすいんだよね…。そしてStateは高速Cloneに対応した自作構造が強いがち。

最終的には手元100件で1068点。

 

感想

今回はコンテスト自体が大荒れだったので色々あまり参考にならず。

様々な機能を乗せるうえで、どういう構造にしてどういうアルゴを使えば上手く出来るかみたいな要素はありましたね。チューニングを始めると開発+アルゴ感が強かった。

速度も大事そうな問題でC++サンプルのリークだったのでC#使いの私は悲惨なことになるかなと思ったんですが、青の人には抜かれてないくらいで済んだので致命傷一歩手前でした。*7

*1:個人的には、一部の人間がアドバンテージを得てしまった以上は全員に共有するのが筋だろうと思います。

*2:前者は完全にミス、後者は方針の違いということでやや中立寄り。

*3:かなぁ?

*4:更新に失敗すると割とすぐbest状態に戻す

*5:基本best状態には戻さない

*6:DictionaryのCloneが重かった

*7:致命傷で済んだ。