Hatena::Grouptopcoder

じじいのマラソン反省会@TopCoder

ニコニコ生放送:red.cliff.jp
TopCoderでプログラムしてみた(Algorithm Single Round Match専用):http://red.cliff.jp/topcoder.html
 | 

2011-10-29

Marathon 74

23:57

見えてないですよね?(万が一見えてたら、教えてください)

目次

マラソンスタートしました(10/29)

00:12

前回の反省を生かして、文章化することにしました。

ファーストインプレッション(10/29)

00:13

  • Anti..巡回セールスマン問題の最長路を求める問題かな?(注:間違いです!
    • 初期の点が何個かあるといえ、これって研究している人がいそうで、めっちゃ不利なネタな気がする…。
    • 2次元の巡回セールスマン問題って、ETSP(Euclidean (Euclidian) traveling salesman problem)というんですね。
    • 検索してみた。
      • http://www-or.amp.i.kyoto-u.ac.jp/algo-eng/db/demo/TSP/index.html
        • 最短路は線が交差しないようなので、最長路を目指すなら線が交差するといい
      • http://maven.smith.edu/~orourke/TOPP/P49.html
        • showed that the maximum TSP can be solved in time O(n) for rectilinear distances in the plane 2次元の最長TSPはO(n)で解ける!なんと論文があるとは… (注:これはrectlinear distanceです。euclid distanceではありませんので、実は全然違う)
        • いや、でも、これぐらいは作題者が気づくんじゃないか。テスターもTCOファイナリストだし。
        • 問題を読み直してみる。
        • 誤読してましたorz

問題

2次元巡回セールスマン問題。2次元平面に都市が何個かある。セールスマンは、スタートの都市から、すべての都市を1回ずつ訪問して、スタートの都市に戻ってきたい。普通の巡回セールスマン問題とは違い、このセールスマンは、まだ訪れていない都市の中でもっとも近い都市を訪れる(最短経路を通るアルゴリズムではない)。あなたは追加で都市をN個置ける。セールスマンの移動距離が最大になるように、都市を置きなさい。

  • Nはpower(10,X) Xは1.0~4.0まで均等。つまりN=10~100まで1/3,N=100~1000まで1/3,N=1000~10000まで1/3。
  • 元から配置されてる都市は3~min(10,N/3)
    • ほとんどのケースで3~10ってこと?かなり少ない印象。大きく影響を与えるんだろうか…
  • 相対スコア。得点は(あなたの距離/1位の人の距離)の4乗!
    • これは、ちょっとの距離差でも大きく点差が開きそう。前回の反省を生かして、Nにあわせて、きめ細かくやる。
  • 計算時間は10秒!。今回は間違えない!
  • 要するに、いまいちなアルゴリズムで動くサラリーマンを、わざとたくさん歩かせるように都市をおく問題。
    • いや、いまいちか?2次元平面上なら、単に一番近い都市をどんどん訪れるというのは、かなり最適解に近くなりそうだが。このアルゴリズムの弱点を突かねばなるまい。
  • 焼きなまし系のアルゴリズムは使えるんだろうか?計算量的にはいけそうだけど…。というよりは幾何の問題?
  • 1000000000*1000000000のフィールドをそのまま使うのがいいのか、量子化したほうがいい?
  • 点を何個かのグループに分ける。ただ、分けたグループの最適解は、全体の最適解とはぜんぜん近くならなそうな気もする。
  • 長時間計算すればするほど、結果がよくなるタイプの問題なんだろうか?もし、そうであれば長時間計算して求めた解の性質を探したいところ。
  • 問題を勘違いしたものの、ETSP max ETSPの解放はチェックしたほうがいいかも。ちょっと役に立つこともあるかも。
  • 単に格子点に都市をおいたら結構強い?

アプローチ1 じょじょに移動距離を増やしていく

f:id:shindannin:20111029143202j:image

  • まずは1次元で考えてみる。図1のように、点はまず端においたほうが距離が伸びる。ただ図3に注目。端に置いた後、真ん中に置くのは正しくない。できるだけいったりきたりするようにさせるためには、図4のように最初に動きすぎてはいけないことが分かる。
  • これを2次元に応用すると、図5のような形になるのかなぁ…。じょじょに移動距離が長くなっていき、2次元に展開にするには、こんなかんじかと。ただし、図6・図7のように、このうずまきの距離を大きくするために、うずまき間の距離を狭くしてしまうと、セールスマンが最短距離のところに移動してしまうため、うずまきにならない。
  • 図8は結構よさそう。つまり、うずまきを作る多角形の辺の長さと、うずまき間の頂点距離を同じにする。図8だと1,2,3,4が等距離、5,6,7,8が等距離になっている。1辺の長さをxとすると、かなり少ない点の数で8x(=4x+2x+x+0.5x...)ぐらいまでの長さが作れそう。
  • ただし若干端が無駄な気がするので、図9のような正多角形もあるかもしれない。いろんな形を試そう
  • また図10のように等間隔でなくても、ある程度いけるのかも…
  • いろんな幾何図形を考えてみよう。ネットで探したり、街中でものを注意してみたり、画像検索もありかもしれない。

アプローチ2 行き止まりに追い込み交差させる。

f:id:shindannin:20111029150000j:image

  • 線が交差するのは、距離が伸びるので基本的によいこと。また、等間隔に点をおけば、セールスマンの移動方向をコントロールできる(今回の問題で距離が同じ点の場合は、IDの小さいほう優先とあるので、IDはこちらで勝手に決められるので実質コントロール可能)。なのでうまく行き止まりに追い込めば、無駄に移動させることができるはず。
  • これも等間隔というのさえ守れば、いろんな図形が考えられるかもしれない。四角形・三角形は確かに充填率は高そうだけど。
  • 図11は四角形でおいた場合。思いつく限りでは、この例が行き止まりに持ち込めやすそう。ただ、行き止まり頻度が少なくても、行き止まりの脱出距離が長ければお得になるので、それは検討しないと。
  • 図12は三角形でおいた場合。1.18倍とわずかながら上。あと、こちらのほうが、同じ点の数でも図11より1辺の長さを大きくできそう。ただ、今回整数の座標にしか点がおけないのが、ちょっときついかも。
  • この思いついた2とおりだけでは、距離がいまいち伸びてない。ここは、BitDPでメモ化探索をして、試すのがよさそう。自分では尾もいつかなそうなので。計算時間がかかりそうなので、早めに仕掛けておく。

終了(11/8)

結局、実装に夢中になっていて、終わってしまった…。

まずは放送用にメモのみ。

  • 10/30 submission 1 単にグリッド上におくだけ15点ぐらい

-

  • じっさいに書いてみると、スカスカの部分が多いので、別の形に変更。
  • うしろからGreedy submission 2 40点。2時間ぐらいなので、意外と高得点。
  • 方針決定
  • 斜め移動の階層
  • うしろからGreedy
  • 四角移動の階層
    • 各エリアをどう通過するか、ハミルトン路を決める
    • それぞれのエリア内でビットDPをする
  • 土曜 ハミルトン路、どうやってもとめるの?
  • 39$バカ
  • 結局、自力で求められたけど。
  • 日曜
    • 実装、難しいとは思ってたけど予想以上に難しい
    • 斜め移動→四角移動の階層へ移動するときに、

--

  • 日曜深夜
    • 実装なんとかできたが低スコア
    • 原因:荒過ぎる。いろいろな階層数をためしたとしても、使用している点の数が、Nと離れていて、その分スコアを失う。
    • 対策1:足りない点は、他のメッシュで埋める。
      • 点が増えるが、前提が崩壊して点があまり伸びないケースあり。
      • しかも、座標の扱いに大きく失敗しているので、実装難。
    • 対策2:多すぎる点はまびきする。
      • 間引きできるパターンは限られる。あまり点が伸びない
  • 月曜朝わるあがき
    • ビューワで点をてきとうにドラッグ。「うしろからGreedy」から点が増えてるんですけど…
    • てきとーに山登りしてみる。submission 59点。休み3日以上使ったのに、てきとーな解のほうが圧倒的によい。

反省点

01:53

  • 最初は、広く浅く!
  • 座標の扱い方。
    • 2,3,4,5でたくさん割り切れる数字でやっとけば。27000の倍数とか。
    • 最初から決めうちは、あとで間違いにきづくときつい。
  • 長時間焼きなまししておいて、解を予想するという方法もあったのでは?特に、自分の頭だけで考えている時間、コンピューターにも考えさせよう。

他の方の解法

01:53

  • 後ろから、うそDP
  • ある点からもっとも近い点の判定。四分木・x軸のみソートとか

f:id:shindannin:20111108075257p:image

skwbcskwbc2012/11/17 03:59>>見えてないですよね?(万が一見えてたら、教えてください)
見えてます。

EstellaEstella2016/05/03 10:11Predivno Zondra ! Prema ovome sto sam ovde procitala i videla misim da bi Vi uzivali kod nas u Vrscu u vinskom podrumu kao i na Mokroj gori (ako niste bili) ! Uzivali biste ! Veliki pozdrav i jos jednom BRAVO za ove factastinne slike i jos bolji tekst! :-D

LolaLola2016/05/04 02:04Ah, the run you described sounded so nice : ) I’ve been fighting injury so I <a href="http://rvbstivt.com">ha2v#&n8e17;t</a> had a run like that in almost a year! I’m getting back to running now but it’s realllly hot here, which is not ideal. 50s-60s with a little sun peaking through some clouds is a perfect run for me

eyonasulejiqeyonasulejiq2017/05/08 21:49http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

iloxizusucamiloxizusucam2017/05/08 22:00http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

owedezuietaiowedezuietai2017/05/08 22:21http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

onotuiwaesauxonotuiwaesaux2017/05/08 22:27http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

igubfazcobeigubfazcobe2017/05/08 22:33http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

ucazuzfuijdfucazuzfuijdf2017/05/08 22:52http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

itovakuobitovakuob2017/05/08 22:55http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

ehxoyedaehxoyeda2017/05/08 22:55http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

ilkaetaruyilkaetaruy2017/05/08 23:12http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

ohueatasiqaohueatasiqa2017/05/08 23:16http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

emidekelemidekel2017/05/08 23:17http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

apyocegoqoapyocegoqo2017/05/08 23:20http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

abobivalisiabobivalisi2017/05/08 23:23http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

okavimimokavimim2017/05/08 23:35http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

ibuaxomuwosicibuaxomuwosic2017/05/08 23:42http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

ulehivonuviulehivonuvi2017/05/08 23:46http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

aiduxyiaiduxyi2017/05/08 23:51http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

onefaxugonefaxug2017/05/08 23:54http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

emihorihoemihoriho2017/05/09 00:03http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

omirinouliqeomirinouliqe2017/05/09 00:06http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

ohewopisagoohewopisago2017/05/09 00:24http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

ilasilatuyoqeilasilatuyoqe2017/05/09 00:26http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

ejitizkucimuejitizkucimu2017/05/09 00:27http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

itahonihitahonih2017/05/09 00:55http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

etjujabogetjujabog2017/05/09 00:59http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

uyuoiboduyuoibod2017/05/09 01:00http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

ofudijuliyofudijuliy2017/05/09 01:19http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

aqgaogiikuvikaqgaogiikuvik2017/05/09 01:21http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

umaxtaqliuhumaxtaqliuh2017/05/09 01:37http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

ikadesebbeikadesebbe2017/05/09 01:42http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

amumweicoamumweico2017/05/09 02:01http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

iepoflubsiepoflubs2017/05/09 02:03http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

igesazantejaligesazantejal2017/05/09 03:16http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

irujtiljinoirujtiljino2017/05/09 03:58http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

ecabivojpifecabivojpif2017/05/09 13:47http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

uiqusiruiqusir2017/05/10 03:45http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

obagehiyunobagehiyun2017/05/10 04:42http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

equrazeqorequrazeqor2017/05/10 06:22http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

asajysexeziasajysexezi2017/05/10 06:48http://100mgcheapest-price-viagra.com/ - 100mgcheapest-price-viagra.com.ankor <a href="http://tadalafil-buy-5mg.com/">tadalafil-buy-5mg.com.ankor</a> http://20mgprednisone-order.com/

 |