RailsDM 2019 で登壇してきました

RailsDM 2019 で登壇

RailsDM 2019 で「Ruby のコード解析の「静」と「動」」というタイトルで発表してきました。

去年の年末あたりに平野さんから登壇依頼が DM 経由で来て「せっかくの機会なのでやるか！」と思い引き受けることにしました。（CFP 形式だと登壇してなかったと思います）

RailsDM なので Rails に関する話が出来れば良かったですが、自分はあまり Rails をそこまで触ってなかったので 普段 Rails を使っている開発者が知らないことを発表するのは少し難しそうだなと思い、Ruby のソースコード解析周りの話をしました。

静的解析、動的解析については過去にも色々発表があるのでそこまで新鮮味は無さそうな気もしましたが、2.6 の新機能の発表はまだ無さそうと思ったのでそのあたりを発表すればそのあたりは大丈夫かなという感じでした。

AbstractSyntaxTree とか TracePoint とか InstructionSequence の利用例を調べるためにローカルで https://github.com/akr/gem-codesearch の環境を整えて色々利用例を眺めてたのですが、結局時間の都合上あまり紹介することは出来ませんでした。（あとあまり調査が出来ていなかった）

発表に関しては正直 10人ぐらい来れば御の字だと考えていたので想像より多くの人に来ていただいて感謝です。ありがとうございました。

また、このような素敵なカンファレンスを開いていただいた RailsDM 運営スタッフの皆様ありがとうございました。

発表できなかった話題

以下は発表資料の中に入れてたけど時間を削るために省いた内容です。

RubyVM.resove_feature_path の不具合

RubyVM.resolve_feature_path ではパスを取得したいライブラリ名を読み込む前じゃないと動作しないという問題があります。(trunk では修正済み)

pp RubyVM.resolve_feature_path('prime')
require 'prime'
pp RubyVM.resolve_feature_path('prime')

実行結果

[:rb, "/Users/siman/.rbenv/versions/2.6.1/lib/ruby/2.6.0/prime.rb"]
[:rb, false]

なのでサンプルコードでさらっと 2.7 前提のコードを書いてましたが、そういう背景がありました。 あとこれはまだ確認はしてないのですが、 gem install 経由で入れたライブラリ名のパスについては取れない気がします。($LOAD_PATH で探して終わり)

iseq オブジェクトを自前で作成して差し替える

iseq を差し替える手法として別のファイルをコンパイルして差し替える方法を紹介しましたが、別の方法として iseq の命令列を作成してそれを Ruby の Cの関数を利用して読み込むという方法もあります。（こっちのほうが出来ることの柔軟性は高いと思います）

詳しくは下記の記事に乗っているので是非読んでみてください。

https://magazine.rubyist.net/articles/0053/0053-YarvManiacs.html

coverage

個人的に Ruby の coverage ライブラリは気になっていたので動的解析の部分で入れたかったのですが時間の都合上カットしました。2.5 で 分岐カバレッジ、 2.6 で oneshot カバレッジが利用できるので組み合わせたら色々出来そうな気がしますが、ネタが出てこなかったです。（なので動的解析部分が TracePoint だけになってしまいました。

標準ライブラリの使用例の調査方法

rubygems にあるような gem の場合は reverse_dependencies で調べることが出来るのですが、標準ライブラリはそれが出来ません。かといって GitHub の検索を使ってもあまりうまくいかないので、今回 gem-codesearch を利用しました。自分はセットアップに数日かかりました。

「gem-codesearch-setup all」を実行した後は知らない

— Shuichi Tamayose (@_simanman) February 1, 2019

やっと gem-codesearch の setup 終わったー pic.twitter.com/FVUSlFzhQ9

— Shuichi Tamayose (@_simanman) February 3, 2019

セットアップが終わったらあとは csearch [検索したい文字] で検索することが出来るようになります。

$ csearch RubyVM::InstructionSequence

今回作った gem

今回の発表準備の期間で作った gem です。

astree

自分は tree コマンドが好きなので色々 tree コマンド風に表示させることをしているのですが、今回はそれの AbstractSyntaxTree 版です。

ast2dot

AbstractSyntaxTree で得られた構文木を dot 言語で表現するやつ。発表資料の一部はこれで吐き出して少し編集したものを使いました。

ast_distance

2 つの構文木を受け取ってその編集距離を出すやつ。ただ AbstractSyntaxTree の場合は少しのコード変更でもかなり変わりやすいのでなかなか有効活用は難しいかもしれません。

load_tracer

ファイル間の依存を調べる gem。 2.7 でしか動かない。まだ実験的な実装なので得られる結果が正しくないこともあります。

懇親会

懇親会では色々な人と話すことが出来て楽しかったです。以下は覚え書き（抜けている人がいたら申し訳ないです

yasulab さん

来月の RubyKaigi の部屋の話やここ最近取り組んでいたプロジェクトの話を聞いてました。 Airbnb の宿自体はかなり前から予約していたらしく、かなり費用が安いとのこと。（住宅宿泊事業法が施行された後ではかなり料金が上がったらしいです

kyuden さん

今回実装していた llrbtree の実装にあたって参考にしたものを聞いてみたらスライドの中で紹介されてた この論文 だけとのこと。スゴイ。Ruby にも優先度付きキュー欲しいですねーという話をした。あと、自分も試しに赤黒木実装してみますと宣言してしまったので来月の RubyKaigi までには実装してみます。（一応前にやろうと思ったことがあったので）

yono さん

「お久しぶりですー」みたいな感じで話してた。Redmine 開発辛いトークを hanachin さんと楽しそうにやってました。

秒速さん

去年の RubyKaigi 以来で「お久しぶりですー」みたいな感じで話してました。「Okinawa.rb やばい」という話をしてましたが多分サンプリングが悪いと思っています。

koic さん

発表資料の中にあった LT の概要が気になったので聞きに行きました。 TracePoint の利用事例として面白かったです。自分の場合すぐ良くない方向で活用することを考えてしまうので、もっと役立つ方向で広めていきたいというお気持ち。

joker1007 さん

TracePoint トークをしてました。

ブロック呼び出しをTracePointで引っ掛けて、bindingを取った後に即throwして、ブロック呼び出しを囲っていたcatch節に抜けることで、コード自体を実行せずにブロックのbindingだけを外から取得するという荒技を編み出したのだが、これちゃんとGCされるのか不安w

— ジョーカー 参戦！！ (@joker1007) March 10, 2019

このツイートの内容の詳細についてや、あと「AbstractSyntaxTree にパターンマッチほしいよねー」とか「TracePoint の b_call イベントで引数の値を取りたい」的な話など。

knu さん

SortedSet の話を聞きに行きました。実験的に実装したつもりがいつのまにか本体に取り込まれてしまったとのこと、自分は競技プログラミングをやっているので Ruby 本体で優先度付きキューが入ってくれると助かるのですが、厳しそうとのことでした（競技プログラミングでは 外部ライブラリを使うことが出来ないので本体に無いと使えない）

ujihisa さん

来月の RubyKaigi でローカル変数だけの話をする（ Play with local vars ）という話や今回発表していた内容について少し話しました。「Ruby でフリップフロップを実装出来るか否か」みたいな話になって、その場では答えられなかったのですが、後々考えてみると rubinius の実装を見ればなんとかなるのではと思いました。（自分はまだ見てないです）フリップフロップ構文はもう deprecated な機能になってしまったのでそれがつらいみたいなことも話しました。

yui-knk さん

今回 AbstractSyntaxTree を触ってて色々気になったところを伺いに行きました。一通り疑問が解決出来たので良かったです。 Ruby の実行オプションである yydebug オプションをオススメされましたが、自分がこのオプションを有効活用出来るようになるのはまだ先な気がします。あと ドラゴン本 を紹介されました。

今年作った gem の紹介 (2017)

この記事は Okinawa.rb Advent Calendar 2017 4日目の記事です。

自分は思いついたアイデアをすぐ gem にするようにしているのですが、今年は結構作った気がしたのでそれを紹介したいと思います。

spellcheck

主に技術系の単語にフォーカスしたスペルチェッカー、スペルミス候補を全部 Hash データで管理していてそれを増やすのが面倒になって放置。

サンプル (aplication がタイポしている

hello world.
I create aplication now.
good bye

$ spellcheck example.md

+----------+--------------------------+------------+-------------+
| Location | Text                     | Pattern    | Expected    |
+----------+--------------------------+------------+-------------+
| 2        | I create aplication now. | aplication | application |
+----------+--------------------------+------------+-------------+

result: 1 typo found.

typogen

英語の typo を生成するコマンド。

前に qiita で紹介したことがあるので詳しくはこちら。

https://qiita.com/siman/items/e3c8dfb72e37142b0b86

spellcheck の辞書データを作っていた時に、typo したときの単語一覧を手入力するのが面倒になった作成した。

$ typogen install

nstall
istall
intall
insall
instll
instal
nistall
isntall
intsall
insatll
instlal
instale

ripper_tree

ruby の Ripper.sexp の表示を tree コマンド風で表示させる。

$ rtree -e "1+2*3"

:program
 └──── :binary
         ├──── :@int ["1"] 1:0
         ├──── :+
         └──── :binary
                 ├──── :@int ["2"] 1:2
                 ├──── :*
                 └──── :@int ["3"] 1:4

今年作った gem の中では一番使っている。

tspec

TracePoint を使って Ruby で型チェックが出来るようにした gem。

require 'tspec'

def echo(str)
  puts str
end.receive(str: String)

echo('hello world') #=> ok
echo(123)           #=> TSpec::ArgumentTypeError

require 'tspec'

def echo(val)
  puts val
end.receive(val: [String, Float])

echo('hello')  #=> ok
echo(3.14)     #=> ok
echo(123)      #=> TSpec::ArgumentTypeError

ただ、挙動がちょっと怪しいので自分でも使うのをためらっている。

jt

JSON を tree コマンドっぽく表示させる gem

https://qiita.com/siman/items/a59a7ac80fba3e71ed38

rrpn

逆ポーランド記法の計算機と変換器

https://qiita.com/siman/items/d72854c4c4aaaf452868

rpn の名前空間ほしかったけど取られていた。（残念

hrm

ヒューマンリソースマシーンに出てくる命令を実装したもの。メモリの初期状態を設定するコードは実装していないかも。

ヒューマンリソースマシンは完全クリアした（ﾄﾞﾔｧ

rodir

Ruby のオブジェクト継承ツリーをディレクトリっぽく扱うもの

$ rodir
Ruby@2.4.0 /BasicObject$ ls
<M>   #<Module:0x007fb11a911388>
<M>   Kernel
Ruby@2.4.0 /BasicObject$ cd Kernel
Ruby@2.4.0 /BasicObject/Kernel$ ls
<C>   Object
Ruby@2.4.0 /BasicObject/Kernel$ cd Object
Ruby@2.4.0 /BasicObject/Kernel/Object$ pwd
BasicObject/Kernel/Object

実際に触ってみて 5分で飽きた。

open_class_alarm

オープンクラスに警告を出す gem

https://qiita.com/siman/items/cbc7b85ff45eb5fc58d5

いらない

proc_source

Proc オブジェクトのソースを表示する。

https://qiita.com/siman/items/9ad676cbb4f8afbd15ac

a = -> { 'hi' }
puts a.proc_source

-> { 'hi' }

lier

? で終わるメソッドの返り値を全て逆にする

https://qiita.com/siman/items/475d355fe22e34659149

エイプリルフールネタで作った。テストするときに rspec が壊れてやばかった。(Refinements で影響範囲を限定させた

rtg

Ruby で作ったタイピングゲーム

自分のコンソールの画面に合わせた配色にしたので、場合によっては文字が見づらいかも。

keyevent

keyevent を取得する gem。（Windows では試していない）

require "keyevent"

while input = getkey
  break if input == "Q"

  p input
end

rtg を作っていた時に分離できそうだったので分離した。

まとめ

結構 gem を作ってた。（使ってるとは言ってない

北大日立マラソン参加記

参加してました。

https://hokudai-hitachi2017-1.contest.atcoder.jp/

やったこと

とりあえず submit (52935)

左上から丁寧に並べる

焼きなましする (52935 -> 149624)

近傍は ランダムな2点の位置を交換する

温度管理を調整 (149624 -> 155183)

雑に設定していたパラメータをちょっと調整

遷移させるかどうかの閾値を設ける (155183 -> 156319)

確率的に遷移させるけど、あまりにもスコアが下がっていたら遷移を却下する。

近傍を変える (156319 -> 159568)

ランダムな2点の位置を交換する から ランダムな辺を選び終点の周辺マスを1つ選択する。既に点がある場合は交換、ない場合はそこに点を移動させる に変更。

これだと、必ずスコアに影響がある近傍になるので効率が良い。

初期解を変える (159568 -> 160152)

最初から中央に配置しておくことで移動のバリエーションが増える (気がする)

諸々高速化 (160152 -> 160950)

盤外判定を削除したりとか

if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;

高速化 (160950 -> 161572)

辺の重みを int で管理してたのを char にしたら速くなった

細かく確認してないけど、この時点での試行回数は 2億5千万前後ぐらいだったと思う。（3億は目指したかった）

パラメータ調整 (161572 -> 163024)

ひたすらパラメータ調整。（このときはまだ、システムテストとか無かったから適当に submit しながら調整してた）

辺の一部のみを採用する (163024 -> 163653)

全部の辺を使ってたけど、各頂点から生えている辺を重さ順で並べて、その上位だけを使用するようにした。

コード

https://github.com/siman-man/hokudai-hitachi2017

PoisonedWine 参加録

問題

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16944&pm=14636

複数のワインの中から、毒に反応する試験紙を使って「毒入りのワイン」を見つけ出し「毒入りではないワイン」をいかに多く集めることが出来るかという問題でした。（試験紙は毒に反応すると、次回以降に利用できなくなります）

方針

今回の方針です。

1. ワインを一通り検査する

まずは、各ワインを1回ずつ検査していきます。1回のラウンドで検査する範囲についてですが、以下の計算式で出していました。

n * (残っている試験紙の数 / 残っている毒の数) * (未チェックのワインの数 / 残りラウンド数) # nは任意の係数

そして、計算した範囲を試験紙の枚数で分割して、それぞれ検査を行います。

検査中に「試験紙が反応した数 == 毒の数」になった場合は、そこで検査を止めて、未検査のワインを全て保持するようにします。

また、毒に反応した範囲は 毒入りワインリスト に追加します。（毒入りワインリスト は範囲の大きいサイズから取り出す優先度付きキューです）

struct PoisonBarrel {
    vector<int> wineList;

    bool operator>(const PoisonBarrel &pb) const {
        return wineList.size() < pb.wineList.size();
    }
};

2. 追加のチェック

手順1で出した検査範囲だと「試験紙の数 < 毒の数」の場合はそもそも全部検査しきれずに終わることが多いです。逆に「試験紙の数 > 毒の数」の場合は全てのワインの検査後にラウンドが余るケースが発生するので、その場合は追加の検査を行っていきます。

追加の検査は試験紙が反応した範囲のワインに対して行います。

2.1 試験紙が反応した数 == 毒の数の場合

このケースでは「試験紙で検査した範囲に必ず毒が1個ある」という状態が確定しているので 毒入りワインリスト から試験紙が反応した範囲を取り出して、それを分割して検査します。m枚の試験紙を使って検査する場合はその範囲を m + 1 で分割します。m + 1 で分割している理由は、m枚の検査の結果から残りのワインの状態を確定させることが出来るからです。（いずれかの試験紙に反応すれば残りはOK、試験紙が反応無しだとOUT)

そして、毒が入っている範囲のワインを再度 毒入りワインリスト に追加します。

これをラウンドか試験紙がなくなるまで続けます。

2.2 試験紙が反応した数 != 毒の数の場合

このケースでは「試験紙で検査した範囲に複数の毒がある」という可能性があります。なので、この場合は m + 1 で分割しても、試験紙の結果から残りの状態を確定出来ません。

(もしかしたら毒かもしれないので確定できない)

このため、確定できなかったワインリストについては とりあえず保存領域 に置いておきます。

とりあえず保存領域 は、後の試験結果で毒が存在する箇所が全て確定した時にキープするワインのリストを置く場所です。

例えば「試験紙が反応した数 = 9, 毒の数 = 10」だとして、毒入りワインリスト から取り出した範囲から2個以上の試験紙の反応が出た場合。全ての毒の存在箇所が確定するので とりあえず保存領域 にあるワインを保存します。

このケースの場合はなるべく早い段階で複数の毒を検出したいので、試験紙の割り振り方を「m > 1」になるように調整しています。（例: [1, 1, 1, 1, 1] とあったら [3, 2, 0, 0, 0] となるように調整）

Examples

Example scores:
0) 0.01323285993742249
1) 0.20518911960377745
2) 0.009050017313019389
3) 1.0
4) 0.05072227596728843
5) 0.00401218710446807
6) 0.04226661200602016
7) 0.07289292284542803
8) 0.001466688380179619
9) 0.6574141709276845

MM92 Lighting 参加録

Marathon Match 92の「Lighting」に参加していました。

問題

SxS のセル状空間に光源の強さがDのL個のライトをいい感じに設置して、なるべくたくさんの空間を照らしましょう。

すごいシンプルでした。美術館問題に似た問題だなと思いました。

方針

大きく分けて次の3つを行いました。

• フィールドの拡大率をいい感じに決める
• 焼きなましで照明を設置する場所を決める
• 焼きなまし後にフィールドの拡大率をさらに上げて照明の位置を微調整する

フィールドの拡大率をいい感じに決める

最初に与えられたフィールドをそのまま使うと照明のシミュレーションの精度が粗いので、フィールドをある程度引き伸ばして精度を高めました。テスターの実装では拡大率が f = 100 で定義されていましたが、これをそのまま使うと後の焼きなましパートで試行回数が全然稼げないので、フィールドサイズが「縦 x 横 == 10000」ぐらいになるように値を修正しました。

SCALE = ceil(sqrt(10000 / (S * S))); // 端数は切り上げ

焼きなましで照明を設置する場所を決める

遷移は「照明を1つ選び任意の場所に移動させる（※ただし壁は除く）」を採用し、温度管理は「差分スコア / (任意の定数) * (残り時間)」で管理してました。

1つのセルを16分割して細かく移動出来るようにしています。

　　　↓

高速化

一度照明のシミュレーションをした座標については「照らすことが出来るセルの位置情報」をキャッシュして、次回以降はそれを取り出すようにしました。

照明の位置を微調整

焼きなましパートで照明の位置を決めた後に位置を微調整を行いました。処理的には任意の照明を1つ選んでちょっとだけ動かしてスコアが改善していたら採用という感じで山登り的に行いました。シミュレーションの精度を上げるために事前にフィールドを焼きなましパートのときより少し拡大しています。

それぞれのパートの時間の割り振りは

• 焼きなまし(15秒)
• 微調整(5秒)

としました。

感想

0.1%のスコア範囲で争ったのは初めてかもしれない。みんな大体同じ戦略になってそう。

Example scores:
0) 0.9987473684210526
1) 0.8922939051918736
2) 0.7014297413793104
3) 0.382128527607362
4) 0.15465865921787708
5) 0.13367932926829268
6) 0.98818025477707
7) 0.9328539007092198
8) 0.7149500729927007
9) 0.7206551724137931

ソースコード

RubyのEnglish.rbソース読み

Rubyの標準ライブラリを読んでいく、前回は3年前に ostruct を読んだ

• RubyのOpenStructソース読み

今回は English.rb を読んでいく。

English.rbとは何か

English.rbはRubyの特殊変数に対してわかりやすい別の名前を付与するライブラリである。Rubyの特殊変数は通常 $ + 記号 の形で与えられており大変読みにくい。そこでこの English.rb を取り込むことで読みやすい別名を使用することが出来るようになる。

require 'English'

"hogefugapiyo" =~ /fuga/

p $PREMATCH   #=> "hoge"
p $MATCH      #=> "fuga"
p $POSTMATCH  #=> "piyo"

中身を見てみる

基本的に alias を使って別名を割り当てているだけ

# The exception object passed to +raise+.
alias $ERROR_INFO              $!

# The stack backtrace generated by the last
# exception. <tt>See Kernel.caller</tt> for details. Thread local.
alias $ERROR_POSITION          $@

# The default separator pattern used by <tt>String.split</tt>.  May be
# set from the command line using the <tt>-F</tt> flag.
alias $FS                      $;

1つ気になるところ

読んでいて1個所気になったのはこの部分

module English end if false

絶対に実行されない謎のコードが入っていたので「なんだこれは」と思っていたのだがどうやらRDocのparseのために追加しているらしい。

参考URL

• library English

TCO 16 Round3参戦記録 - TerrainCrossing -

TCOMMの最終ラウンドが終わりました。

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16704&pm=14283

問題文

縦横長さが S あるフィールドがあります。フィールド上にはN個のアイテムとN個の目的地が存在しています。あなたは全てのアイテムを各目的地に運ぶ必要があります。この時、各目的地には1つのアイテムしか届けることが出来ません。（複数のアイテムを同じ目的地に置くことは不可）

フィールドの移動についてですが、現在いるセルから隣接するセルへ移動が可能です。また、各セルにはコストが割り振られており、そのセル内での移動では「移動した距離 x セルのコスト」のコストがかかります。さらにセル間の移動については以下の計算式によって追加コストが発生します。

セル(x, y) -> セル(nx, ny) への移動
addCost = pow(fieldCost[x][y] - fieldCost[nx][ny], 2)

アイテムの回収についてですが、プレイヤーがアイテムの座標から距離0.001以内のフィールドに到達すると自動的に回収されます。アイテムの保持数については上限があり、上限を超えてアイテムを保持することは出来ません。また、アイテムの設置については回収と同様に目的に0.001以内のフィールドに到達すると自動的に配置されます。アイテムを保持していない場合は設置は行われないので注意してください。

また、経路の開始地点と終了地点についてですが、開始時は任意のマップの端から0.001以内の距離にある座標から開始し終了地点も同様にマップの端から0.001以内の距離を指定してください。なお、連続している経路の間隔は0.001より大きく、かつ座標が存在しているセルのマンハッタン距離が1以下になるようにしてください。さらに始点と終点を除いた各経路の座標はセルの端から0.001より離れた場所を指定してください。

最終的にコストの消費を少なく全てのアイテムを目的地に届けて下さい。

今回の問題、細かい制約のせいでたくさんのバグを埋め込みました。 あと参加した中で一番疲れました。

戦略

今回は「各オブジェクト間のコストを計算」「巡回セールスマン問題を解く」「山登りで経路を修正」と大きく分けて3つのフェーズに分けて処理を行いました。

各オブジェクト間のコストを計算

まず最初にフィールドに散らばっている「アイテム」と「目的地」それぞれの経路間のコストを求めます。基本的には各オブジェクトからダイクストラ法で経路を生成しました。

なるべくコストが小さくなるように移動。

今回はこのコストをどう計算するかでかなり頭を悩ませました。というのも、下の図のようなフィールドが存在し

このフィールドを次のように移動した時に、図の経路だと「1 + 1 = 2」と計算するのですが、実際には

この移動が可能なので1.41ぐらいのコストにしたい、かといってこの状態でさらに右に進んだ場合

今度は赤線の経路が最短になり、前回時点での最短を固定してしまうとロスが発生してしまう。

このロスは経路を進めれば進めるほど発生するので、このロスをいかに減らすかが難しかったです。

自分は通常のコストの計算時に追加コストを通常の2倍で計算を行いました。（これは評価値としては微妙な気がしなくもないですが

また、Sが小さい場合は、1つ進める毎に今までの経路に対して後述する山登り法を適用して経路のコストをその都度再計算していました。

巡回セールスマン問題を解く

求めたオブジェクト間のコストを元に巡回セールスマン問題を解きます。経路には以下の制限をつけました

• アイテムが0個の状態で「目的地」に到達してはいけない
• アイテムの所持数が上限の状態で「アイテム」に到達してはいけない

巡回セールスマン問題を解いた内容については前回の予選の感想ブログで書いた内容とほぼ一緒なのでそちらをどうぞ

simanman.hatenablog.com

簡単に説明すると、現在の経路に対して以下の操作のいずれかを選択します。

• 2点間のオブジェクトを入れ替える
• 2点間の交差を削除する
• 1点を取り出し任意の場所に追加する
• 連続した2点を取り出し任意の場所に追加する

また、仮に経路のコストが増加しても一定の確率でその経路を採用します（焼きなまし法

山登りで経路を修正

最終的な経路が確定したら、経路の座標をランダムに選択し、ランダムに動かしてスコアが改善されたらそれを採用する、という処理を行いました。

この様な経路が存在している時に

始点と終点とアイテムと目的地を除いた座標をランダムに1つ選び動かします

スコアが改善された場合はそちらを採用します。

セルを飛び越える移動も有効にしています

感想

まさか同じ予選で巡回セールスマン問題を2回も出題されるとは思いませんでした。点をばらまいてそれをくっつけたり切り離したり移動させたりする案もあったのですが、時間が無くて断念しました。序盤の「オブジェクト間のコストを算出」する部分が精確に出せなかったのが心残りです。

Example

Example scores:
0) 8.106127476192645
1) 85.36355804638156
2) 384.75769417466637
3) 5627.9464135616445
4) 551.6884483017363
5) 311.8191310808154
6) 313.3568643271177
7) 921.3633059194917
8) 1493.4400096579031
9) 664.7891337391771