usakdsteen

ゆうさくですてぃーん

topcodermarathonmatch96myapproachoffinalsubmit

コンテストの問題文 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17052&compid=58895

コンテストの順位表 https://community.topcoder.com/longcontest/?module=ViewStandings&rd=17052

↑のプログラミンコンテストで仮順位が12位になり

まぁ調子乗って post my approach なんぞしてみようかと思った次第でして

まぁ私プログラミンは素人の初心者レベルですが比較的頑張ったんじゃないかと自負しなくもないです、はい

 

では本題、

簡単に説明すれば

色を無視したとき各形状がだいたい同じ数ずつあることを勝手に期待した上で、できる限り敷き詰めるような感じで手動で線を配置してループを作って(要するに埋め込み?)、そこに色をはめ込んで、残ったパーツをループに継ぎ足すような感じで配置できそうなとこに配置する、みたいな

その埋め込みループのパターンを3種類ほど用意してて、そのうち一番スコアが良かったものを選択して出力する感じ

 

example testの結果はメールからのコピペでこれ

Example scores:
0) 0.0
1) 0.0
2) 0.9888
3) 0.9724
4) 0.95405350214417
5) 0.934640522875817
6) 0.9648526077097506
7) 0.9659863945578231
8) 0.9547911547911548
9) 0.9529616724738676

 

ここからは読む必要ない話になるけど(単なる自己満足的な語り)

最終サブミットコードの大雑把な説明

 

 まぁ3種類と書いたけど

そのうち2種類ほどを派生させたものを合わせて8種類

そして保険にもならなかったが別なアプローチのものもあって

実際は全部で9種類から一番スコアのよいものを選んでる

 

アプローチ名にそれぞれメソッド名あって

Approach, ApproachT, ApproachX, ApproachR

ApproachY, ApproachZ, ApproachS, TryHilbert, idea4

の9種類

3種類というのはこのうちApproach,ApproachT,TryHilbertのことになる

(なお、idea4内で使ってる処理と同等のものをidea4_partialというメソッドにして他の8種類のアプローチにも適用してる)

各メソッドに実行時間を設けていて

Approach,ApproachT,ApproachX,ApproachR,TryHilbertの5つは確実に実行されるように時間設定されていてこれらだけで最大時間使う場合もあり

ApproachY,ApproachZ,ApproachS,idea4は残り時間次第では実行されない

 

Seed= 10001~10500 の500件で各ケースで選択されたアプローチの総数は

Approach ... 76件

ApproachT ... 146件

ApproachX ... 19件

ApproachR ...  53件

ApproachY ... 49件

ApproachZ ... 4件

ApproachS ... 114件

TryHilbert ...  39件

idea4 ... 0件

となった

 

ループの継ぎ足し処理の部分はidea4_partialメソッドの担当で

↓こんな感じのやりたかったなーって…

f:id:neetsdkasu:20171231042209p:plain

左のが継ぎ足し部分の処理、直線の連結部分を作り変える感じで

中央のが継ぎ足せる直線の連結を作り出す感じで

右のが継ぎ足し用の色のパーツが足りなくなる事態を想定してときどきループ部分から交換して手持ちのパーツのバリュエーションを変える感じ

実装に何かどこか失敗してるぽくてあまりうまくはいってなさそうだったけど

 

以下、出てくる画像は全部 Seed = 10199 のものである

(当該Seedで最終提出コードが生成するであろう候補をそれぞれ出力した)

(ビジュアライザに -size 6 を指定して出力した)

手動でループ埋め込みなんで、まぁ画像のほうが説明にてっとり早いので

 

Approach

↓の画像のような感じでループを手動で引く

パーツが足りてることを前提として閉じてしまうためパーツ不足の場合、色の配置に失敗することがある

その際は手動配置したのを取り除き未使用パーツを増やしながらDFSで繋げられるか試したりする(それでも失敗するときがある)

(score 0.87817)

f:id:neetsdkasu:20171231042345p:plain

idea4_partial適用でこうなる

(score 0.96166)

f:id:neetsdkasu:20171231042432p:plain

 
ApproachT

Approachの配置の向きを変えた感じのもの

Approachとはパーツの消費の仕方が多少変わるのでテストケースによっては有利不利が変わる

(score 0.83735)

f:id:neetsdkasu:20171231042726p:plain

これにidea4_patialを適用すると

(score 0.95671)

f:id:neetsdkasu:20171231042907p:plain

 
TryHilbert

4x4のHirbert-curveを敷き詰める感じで配置する

直角パーツと直線パーツの使用比率が3:2くらいになる

パーツ不足になりそうなかなり手前でDFSで繋いでループにしてる

テストケース次第ではこれのほうがスコア上がることもあった (score 0.61348)

f:id:neetsdkasu:20171231043320p:plain

idea4_partialを適用すると

(score 0.89425)

f:id:neetsdkasu:20171231043413p:plain

4x4単位で敷き詰めるので隙間が出来たりするので

敷き詰めたもの全体を位置を変えながらidea4_partialを適用させてスコアのいいものを選択する感じになってる

 

ApproachX

これはApproachのループ作成時、ループを閉じる最終部分(下側と右下側)を

手動埋め込みではなく、DFSによって繋ぐ感じのもの

(score 0.86889)

f:id:neetsdkasu:20171231044053p:plain

このループの閉じ方の違いでidea4_partialの影響が変わる

(score 0.94063)

f:id:neetsdkasu:20171231044245p:plain

 

ApproachR

ApproachからApproachXへ派生させたのと同様にApproachTから派生させてる

(score 0.82684)

f:id:neetsdkasu:20171231044654p:plain

idea4_partial適用で

(score 0.94434)

f:id:neetsdkasu:20171231044749p:plain

 

ApproachY

Approachから下側と右下側の線の引き方を変えてあるのと

パーツ不足時のDFS時のループの削り方が異なる

(score 0.87816)

f:id:neetsdkasu:20171231045928p:plain

idea4_partialの適用で

(score 0.96413)

f:id:neetsdkasu:20171231050044p:plain

 

ApproachS

Approachに対するApproachYと同様にApproachTに対しての派生

(score 0.83797)

f:id:neetsdkasu:20171231050357p:plain

同様にidea4_partialで

(score 0.96289)

f:id:neetsdkasu:20171231050607p:plain

 

ApproachZ

Approachにおいてループ手動作成の最終部分に関して

残りパーツ数が少なくなってきた時点でDFSで繋ぐことを試みる処理になってる

ハズだがなんかうまく挙動してないっぽい

(これでスコアが上がることは偶発的であり非常に稀だった、Seed=10199はその当該ケース)

(score 0.87879)

f:id:neetsdkasu:20171231051038p:plain

idea4_partial適用

(score 0.96536)

f:id:neetsdkasu:20171231051420p:plain

 

idea4

これが何をやっているかというと

中央に2x2の最小ループを作ったあとに

idea4_partialでやってるような処理を適用するだけ

他のアプローチがめいっぱい計算した後の残り時間だけで処理するため時間不足で2x2の最小ループだけ作って終わることも

なお、フルで時間使ってもスコア低い

各ApproachやTryHilbertの全部でループ作成に失敗したときの保険程度にしてたつもりだったが当該ケースがあるのかは不明

idea4という名前は2nd~3rdサブミットあたりで取り組んでたときのアプローチのうち4番目のアイデアでそういうメソッド名のまま最終サブミットにも持ってきてる

(score 0.67038)

f:id:neetsdkasu:20171231052038p:plain

 

以上。

 

 

素人の発想(解探索が非常に雑)でここまでの順位(仮ではありますが)になれたのは、期間が1週間しかなかったことと、年末の忙しい時期でクリスマスが間にあったことなどで、多くの強者たちがこのコンテストにあまり時間をかけられなかったんじゃないかと、予想してまする

 

コンテスト時のアイデアメモ

https://gitlab.com/neetsdkasu/TopCoder-MarathonMatch96-MySolution/blame/master/memo.txt

 

コード

gitlab.com

最初(1st)のフルサブミッションから最終(21st)のフルサブミッションまでの各コードでのexamples(seed2~10)の結果画像はこれ

https://neetsdkasu.gitlab.io/TopCoder-MarathonMatch96-MySolution/