Hatena::Grouptopcoder

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

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

2014-03-01

日記を移行しました。

15:47

マラソンマッチの記事をすべて、はてなに移動させました。今後はこちらにまとめを書きます。

http://shindannin.hatenadiary.com/

ちなみに、SRM関係のリンクは、いままでどおり更新予定です。

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/

2011-07-22

Marathon 72

22:03

結果

22:03

7位/44 Rating 1694→1783

裏マッチだったので、強いのはcolunさんだけなのに、7位。結果のわりには、レートは上がったのは、たまたま自分より上の順位の人が新規の方ばかりだったから。結果を反省せねばなりません…。

問題

22:03

平文を圧縮してください。平文の文字列長は500ぐらい~100000。圧縮後の文字列の長さ(辞書みたいなかんじ)も決められてます。例えば、以下のようなかんじに圧縮してください。

S[1] = bpa4h2edn2b3k2d3z2e43b

S[2] = 3i3ufx4uku34gzfob4vlozd3m

S[3] = juquvqvrudlpqezzzchprdwi

S[4] = kozid3pvevaytgjxdmjpfbsfhxrtovqp

暗号の解凍アルゴリズムは決まってます。数字の部分xは、番号のS[x]の文字列に置き換えられます。解凍後の文字列が、元の文字列と同じであればあるほど高得点。その他、もとの平文はランダムで文字が置き換わる確率はテストケースで大きく異なります。

すごくざっくり言うと、「覚えられる単語数が極端に少ない辞書式圧縮で、劣化をできるだけ抑えよ」という問題です。

反省点

22:05

放送中に、chokudaiさん、yowaさんから頂いたアドバイスなどを元に反省。

  • 日記を書きながらやろう
    • 自分の考えが整理できます。
    • 最初のほうに思いついたアイディアを後で使いたくなったときにも使えます。
    • あとで日記を思い出しながら書く時間もはぶける(時間たってからの復習は、ものすごく時間がかかる)
  • 幅優先探索のメリット
    • 今回の問題は、深さ優先探索よりも幅優先探索のほうが有利。この問題では、「最初の単語を当てはめを間違うと、そのあとは全然ダメである。さっさと打ち切りたい。」 これに深さ優先探索を使ってしまうと、最初の単語の当てはめ方が良かったのかイマイチだったのかが分からないまま、どんどん深い方へ探索してします。幅優先探索であれば、他の候補と相対的に良い悪いを比較できます。最初の単語の当てはめ方が一番良かったものに、より多くの探索時間をかけるといったことも可能です。
  • 問題をよくよめ
    • 時間制限は毎回違います。今回は10秒と誤解してしまいましたが、本当は30秒でした。よく読みましょう。
    • 今回は数字の使われ方を理解してませんでした(必ず1種類につき1個~4個使われる)。普通のAlgorithmマッチでは、細かい条件も使える場合がとても多いので、よく読みましょう。
  • Marathonスコアが低い場合は、いいアイディアが思いついていないのではなく、基本的なアイディアに気づいていないだけ。
    • 一見いいアイディアがでてないようにみえますが、結果をみてみると大抵の人が思いつきそうなものをボロボロと落としていました。今回の問題もビューワを書いたほうがよかったかもしれません。
  • きめ細かくやる
    • 神頼みフェーズ手抜きすぎました。裏マッチでも意外とちゃんとやっている人が多かったです。特に相対スコアルールのとき、こういうところで点を落としやすいので気をつけましょう。

方針

00:56

  1. ボトムアップで、短い単語から、平文から数字に置き換えていく。
  2. トップダウンで、長い単語から、平文から数字に置き換えていく。(最終的に企画倒れ)
  3. 神頼みフェーズ(一番使われているのが多い文字で埋める)

ボトムアップで、短い単語から、平文から数字に置き換えていく。

  • S[x]の同じ長さの部分文字列の中で、たくさんでてくる「似たような」文字列を探す。探し方は以下の通り。
    • (このやり方より、「一番短い部分文字列は、必ず最初の32文字以内に現れる」の法則を使ったほうが、確実かつ高速だったと思います。全く気づけませんでした。ビューワ作ってれば気づいてたかも…)

例えば、"ABCDEFABXDE"の中にある似たような部分文字列(長さ5)を知りたいとき

(1)連続する2文字のハッシュ値の登場回数をカウント

map[連続する2文字のハッシュ]++

AB 2点

BC 1点

CD 1点

DE 2点

EF 1点

FA 1点

BX 1点

XD 1点

(2)連続する文字列長xの間で、連続する2文字のハッシュが合計何回でてくるかカウント(合計はしゃくとり法で求めました)

ABCDE 2+1+1+2=6点

BCDEF 1+1+2+1=5点

CDEFA 1+2+1+1=5点

DEFAB 2+1+1+1=5点

EFABX 1+1+1+1=5点

FABXD 1+1+1+1=5点

ABXDE 1+1+1+1=5点

(3)最高得点のやつが、もっともよく出てくる似た文字列。(ただこの得点のつけ方だと長い文字列が必ず有利になるので、得点のつけ方は、若干調整してます。)

この場合、ABCDEが6点で最高。

  • これを深さ優先探索(←全然ダメ)でやりました。枝の数は、Sの数に応じて、調整しました。

トップダウンで、長い単語から、平文から数字に置き換えていく。(最終的に企画倒れ)

今回、問題が途中で変更になり、error値が大幅に大きくなりました。そこで、平文がerrorによりぐちゃぐちゃになっても、まだ残っている情報ってなんだろう?「実は長い平文のほうが、残っている情報が多いから、復元のチャンスがあるのでは?」と思い、やってみたのですが…

  • まず、同じ文字の間隔が多いところを探す

同じ文字の間隔を使えないか?

ABCDEFABXDE

A-A 文字の間隔 4

B-B 文字の間隔 4

D-D 文字の間隔 4

E-E 文字の間隔 4

よく出てくる単語は、同じ間隔がでてくる回数も多くなります。文字間隔が小さいと(特に26以下)役に立たないけど(鳩の巣原理)、文字間隔が大きいときは、実際の文字間隔だけが突出した値になります。平文が長ければ多ければ、誤差が大きくても正しい単語間隔が見つかりました。

  • 文字間隔から、実際の単語S[]の位置を探す

文字間隔dが既知となりました。文字間隔をdとしたとき、位置aと位置a+dが同じ文字になる場所を羅列します。横軸を単に順番のID(aの小さい順)、縦軸をaとしたとき、以下のようなグラフになります。

f:id:shindannin:20110816010843p:image

(エクセルシートのA列が、縦軸のaです)

このグラフを見ると傾きが平らな部分と、急でガタガタな部分にはっきりと分かれます。この平らな部分が実際単語がある部分、急な部分はたまたま同じ文字が現れた部分になります。というわけで、急な部文と平らな部分の境界が単語のスタート位置になるのが分かりますが、ここで問題がありました。

  • 単語の位置は少しでもずれて置き換えてしまうと、その後の結果がひどいことになる。
  • 意外と平らな部分とガタガタな部分の境界を正しく求めるのが難しい(1階微分・2階微分いろいろ試しました。)

というわけでトップダウンの方法は諦めました。ただ、この平らな部分の傾きからerrorを求めることができるので、それは副産物として使用しました。

個人用メモ

15:49

■ファーストインプレッションとその結果

    • 基本的には、dataの生成方法をヒントにすると、かなり簡単にできるかもしれない。
      • (結果)その通りだが、生成方法をちゃんと理解してなかった。
    • 見本のなかのerrorは予想できるのでは?
      • (結果)できた。そこそこ役にたった。
    • 必ずしも、見本どおりの圧縮をする必要はない。再現が高いほうが重要。
      • (結果)神頼みフェーズで使ったが、甘かった…
    • 必ずしも、圧縮文字列をすべて使う必要はない。短くてもOK
      • (結果)ぴったりじゃないと大体ダメなので…
    • トップダウン/ボトムアップ/両側探索それぞれメリットありそう。ケースによってかえれるので、1つにこだわる必要はない。
      • (結果)結局ボトムアップと神頼みだけになった。
    • トップダウンのときは、文字列の長さの予想が難しい
      • (結果)いろいろ試したが断念
    • いろんな区間長で調べる必要があるかも。
      • (結果)???。何ですか??
    • エラーの予想は、ボトムアップの1段階目でできないか?
      • (結果)できた。これでもまぁまぁの結果だった。
    • 答えSの読みこみ、Sの登場文字列数との比較はすごい重要な気がする。
      • (結果)やった。問題のinputでない値も、結果の比較用に積極的に使おう。

■キーワード(調べ物するとき用)

似た文字列は似たハッシュ値になってれば分類できる?

    • 近似近傍点探索手法 Locality Sensitive Hashing(LSH)
    • k近傍法
    • kd木
    • Metric tree
    • ハッシュ
    • continuos
    • Locality sensitive hashing (LSH)
    • 類似文字列検索アルゴリズム
    • Divide Skip
    • ハミング距離
    • 宇野毅明

2011-06-29

結果

00:55

136位/222 Rating 1795→1694

このRoundで敗退かつレーティング的にも大敗北…

問題

00:56

複数の点がだいたいランダムに配置されている(点の数は50~5000)。それらの点を結んで多角形を作れ。

  • 入力パラメータsidesDiff。1≦sidesDiff≦20。sidesDiffは多角形の各辺の、最小の長さと最長の長さの割合、もしsidesDiffが20だったら、最小の辺の長さは、最長の辺の長さの100-20=80%以上でないといけない。
  • 入力パラメータradiiDiff。1≦radiiDiff≦20。radiiDiffはは多角形の中心(点の座標の平均)から、各頂点からの距離の、最小の長さと最長の長さの割合。sidesDiffと同様。
  • 同じ点を2回以上使ってはいけない。
  • n角形につきn*n点もらえる。

点が少ないケース(Example1)

f:id:shindannin:20110630004059j:image

点が多いケース(Example7200)

f:id:shindannin:20110630004423j:image

このように、つくるべき多角形は正多角形に近い形になります。

方針

00:56

今回は反省点が多いのですが、まずは、良さげ見える(が実は良くない)今回の目標と方針を書きます。あとで、失敗した点を書きます。

目標

今までのマラソンマッチでは、最高点が伸びなそうなアルゴリズムだったので、中途半端な順位だった→

「今回はすぐに結果がでないくてもいいから、到達最高点が伸びるような、計算量もギリギリまで使い切るような、スケールの大きいアルゴリズムにする。」

方針が決まるまでの流れ

「たいていの人は頂点数Nが多いときに苦戦するであろう」

→「計算量がNにあまり依存しないアルゴリズムを考えれば勝てるのではないか?」

→「下記のアルゴリズムなら、O(中央の点の数*N)と、Nのオーダーは1乗。しかも、計算量も中央の点を(1,1)おきにとれば、700*700*5000=2450000000で10秒ギリギリぐらい?いけるかも」

→「しかも、この方針は、正10角形を求めるのも、正100角形を求めるのも、かかる時間はそれほど変わらないので、めっちゃ有利」

実際以下の方針を思いつくまでに、10日ぐらい消費してしまいました…

方針

1.まず、中央の点(cx,cy)を決めます。

f:id:shindannin:20110630004526j:image

2.N個の点を極座標に配置します。各点のr,θを求めるのは三角関数で簡単に求まります。

f:id:shindannin:20110630004524j:image

3.座標に分けたので、θ方向に等間隔の座標にあれば、正多角形に近い形になります。

f:id:shindannin:20110630004523j:image

f:id:shindannin:20110630004522j:image

4.結局は、r,θの2次元の座標に落とせるので、「もし、ある(dr,dθ)の範囲内に点があるか調べたい」ときはDPを使えます。

f:id:shindannin:20110630004521j:image

だいたい、「θの範囲、rの範囲がどれぐらいに収まっていれば、正多角形ができるか?」についての基準は、あらかじめ別なプログラムで、sidesDiffとradiiDiffごとに求めておきました(ある半径rのn角形の,範囲dr・dθに点をランダムに配置し、sidesDiffとradiiDiffを満たす多角形ができるか調べる)。実際にこの部分の精度については、かなり高かったので、うまくいってたと思われます。

反省点

00:56

目標が間違ってる

そもそも「計算量をギリギリまで使ったアルゴリズム」が高得点とは限りません。欲しいのはスコアです。大きく勘違いしてます。

スコア分析がだめ!

これ、すごく重要で、初回のマラソンでは出来てたのですが・・・。この問題を「正n角形で、できるだけnが大きい多角形をたくさん作ろう!」と考えているようではダメです。もうちょっと細かくみていかないといけません。例えば、6角形1個は36点、3角形4個も36点です。大きい多角形を無理してつくるよりは、多くの小さい多角形をつくったほうが良い場合も十分考えられますよね。スコアについて、ほんとによく考えたほうがいいです。

計算時間あたり・頂点数あたりなど、単位を意識した考察ができていない。

6角形1個つくるのに1秒、3角形1個つくるのに0.1秒だったら、断然3角形をつくったほうが、時間あたりの得点が高いです。同じように、頂点数あたりの得点なんかも考慮するべきでした。今回の自分のアルゴリズムでは、計算時間あたりの得点について全く考慮していません。単位を統一して考えるのは、アルゴリズム以前の重要な問題です。これがちゃんとしてないと、そもそもアルゴリズムの良し悪しの比較ができなくなってしまいます。仕事では、めっちゃ注意しているのですが(T T)

「頂点数Nに依存しにくいアルゴリズム」にする必要はない。

別にNによってアルゴリズムを変えるのは全然構いません。Nに依存しないアルゴリズムは、裏をかえせば「Nが小さいときの有利さを生かせない」アルゴリズムでもあります。(ただ、複数のアルゴリズムを用意するのは、実装の時間はかかるので、1つに統一するメリットもあります。)

実装時間も考えて計画をたてよう。

誰でも思いつくようなケースをほとんど試さなかった。

特に、時間がかからずに実装できるものは、絶対試したほうがいいです。仮に全然結果がでなかったとしても、その後のヒントになる可能性もありますし、条件によっては使えるかもしれません。今回、自分の考えたのは実装時間がかかるため、それが外れ方針なのに気づくのに時間がかかってしまいました。

このアルゴリズムの欠点

00:56

実は、計算量が多くなり、(cx,cy)を調べられる箇所が少ない。

当初の予定では700*700マス(中央がマス上にあるとは限りませんが)調べる予定でしたが、だいたい10000~100000点ぐらいしか調べられませんでした。実は、

(1)r,θを等間隔で細かくとった場合(dr=1,dθ=1)、矩形でO(1)を計算するため、DPで2次元部分和を計算するときが計算量がO(rの分割数(=350)*θの分割数(=360))となり、頂点数Nより大きくなり、そこがボトルネックとなる

(2)r,θを等間隔ではなく、n角形時のdr,dθにあわせてとると、ボトルネックは解消されるが、n角形ごとに計算しなければならない。

最終的には(2)の方針でいきましたが、計算量的にはきつく、多くの(cx,cy)を調べることはできませんでした。

(cx,cy)の位置についての工夫がない。

全く思いつきませんでしたが、多くの人は中央を先に決めるという手法を使ってました。

「(cx,cy)を変えるたびに、N点配置する」ということ自体が損

もし(cx,cy)によらずに、再利用できるデータがあれば、それでも高速化できたはずです。

まぁ、いろいろ試して失敗した点(ひどい焼きなまし法とか)や、反省点(10秒に間に合ってないケースが5つあった)とかは、まだまだありますが、これぐらいで。

2011-06-01

shindannin20110601

TCO11 Round 1

01:07

結果

62位/368 Rating 1754→1795

大反省点

  1. 調査してね(インターネットつかえます)
  2. 文字を置く・何か置く、やり直し(Undo)が可能な部分については、最初からやり直し可能な実装をしていかないと、だめです。
  3. 最初の解答ができるまで、とにかく、がんばれ。
  4. 前回の反省点を守ろう。同じ失敗をくりかえす自分は最悪です(>_<)
  5. マラソン開始日前に、もやもや要素をすべてとりのぞく。何も用事がない・借りがない状態でマラソンをスタートしましょう!
  6. マラソン期間中に、アクシデントにまきこまれない。普通の生活をしよう。
  7. Javaを自分の場合つかわないので、Javaでの採点部分や、scan部分などは、できるだけはやくC++に移植する。
  8. ちゃんとマラソンスタートしたら、はじめる。毎日安定してやる。
  9. はやめにスタートしたほうが、計算リソースを有効に使える。
    • ぎりぎりなってからだと常にパソコンでプログラムを書きたいので、計算結果待ちとかの時間が無駄。はやいうちにスタートしておけば、夜中に計算とか、出勤中に計算とか、有効に計算リソースを使うことができる。
  10. パソコン2台あるのを有効に使う

ポイント

(いろいろあったのですが、マラソンRound2前に書く時間がなくなってしまったので、すごいてきとーです・・・。せめてツールの画像だけでも。本当は画面右側に文字情報のリストが表示され、選択中のものだけ色を変えたりすることもできます。)

f:id:shindannin:20110601092551j:image

f:id:shindannin:20110601092550j:image

基本的には重なる黒のマスが多い文字からおいていったのだが、上のIのように、TLEはIに負けたりする。つまり、

「実際にはかなり合ってるのに、登場することができない不幸な文字があるのでは?」

と思い

  • 外れている文字を使ったら選ばれにくくする
  • 答えにあるのに使わない文字があったら選ばれやすくする

というのを多くのテストケースでまわし、文字の選ばれやすさの重み付けを決めるという方針で行った。

しかし、結果はほぼ効果がなかった。実際には、ほとんどの文字の「当たっているのに選ばれない」=「当たっていないのに選ばれる」の確率はITLEなどを除き、ほぼ一緒になってしまった。

Marathon Match 68

00:51

結果

9位/147 Rating --→1754

大反省点

  1. 開始日になんでもいいから提出して追い込む!
  2. 準備完了までは集中!
    • ちゃんとスコアがでるようになると、面白いので集中できる。準備の段階が面白くないので脱線しやすい)
  3. 異常を早めに察知するために、ときどきArenaにいって、サブミット&まわりの人のチェック(提出時間・得点)
  4. テストケース50個では少なすぎ
    • 誤差でまくり論外!!!テストケースは最悪でも300,500は必要
  5. 疲れているときにできること、疲れているときにできないことにタスク分けして作業をすすめる。
  6. 10秒間の計算時間があるのを有効に使ったアルゴリズムにする
    • 最後のほうまで、即終わるアルゴリズムだったので…

反省点

  1. サブミッションの問題(1時間30分次の提出ができないのでお早めに。
  2. 早めに知ってれば、「へび」配置をいれるかいれないかも含めて調整できたのに・・・。
  3. タイマーの問題(10秒)Clock関数。とくにアリーナ上では、時間がかかるよう。
  4. gettimeofdayのほうがよい?
  5. 序盤の準備にわりと時間がかかる。
  6. やってみて気づくことはたくさん。なので、後で追い込むのではなく、最初から少しずつやってったほうがいい。
  7. ソースは丁寧に書く。リファクタリングは、時間に余裕があるときなら、多少眠くても疲れててもできる。
  8. ネット切断は効果的だったけど、たまにはアリーナものぞくべきだった。

ポイント

「回」型の配置パターンで62.5ptsは取れるのは予想がついたけど、「回」型の配置に気づくのが遅すぎた。また、正方形のときにしか対応できないアルゴリズムを書いてしまったので、「田」型への応用が難しくなってしまった。

唯一良かったのは、大きさの違う正方形「回」を組み合わせることにより、rcFillingScoreが満点のままで「田」型にする方法を思いついたこと。これのおかげで、上位になんとか食い込むことができた。

例えば、3等分の「田」にしたいときは、横幅がN%3==0,N%3==1は以下のような配置にできる。普通の「田」だと隙間の行ができてrcFillingScoreが下がってしまうが、これならOK.

f:id:shindannin:20110601085352j:image

4等分の「田」にしたいときは、以下のような配置もある。

f:id:shindannin:20110601085359j:image

あと、上位の方は

  • 「回」「田」以外でも点対称な配置はいろいろあった
  • 置き換えが可能なアルゴリズムにしていた。

といった点で大きく差がついた。