hotpepsiの練習帳

CodeIQ 最適解を目指せ！！

21:19

tomerunさんのマラソンに挑戦。

1回目

• サンプルを見る
• 乱数で埋めるbenchmark1.cppが774点、1-9のうち重複の少ないものを選ぶbenchmark2.cppが11541点。まずはこれを超えるのを目標にする
• 数独を解くプログラムとかをチラ見するが、3x3の制約が違うので使えないかもと思う
• 評価関数をちょっと速くしたりとか、無駄な時間を過ごす。
• 完全ランダムよりbenchmark2のほうが素性が良さそうなのでベースにする
• 範囲を限定してランダムに置換し、評価値がよくなったら更新してみる
• 20000点くらいになりやっとサンプルを超えたのでひとまず提出
• 8/7の中間発表で圧倒的最下位

2回目

• とりあえず10万点は超えるのを目標にする
• 良いパターンで埋める→ランダムで小改善、は基本とする
• discrete_distributionとかは使いこなせなかったので、普通のrand()に戻す
• 縦ラインのみとかより、以下のようなブロック単位で埋めるほうが良さそう。横と縦の点数が稼げる
  123456789
  456789123
  789123456
  234567891
  567891234
  891234567
  345678912
  678912345
  912345678
• ブロックの大きさ(3x3や6x6)、開始位置(456からはじめたり)などをいくつか試す
• ランダムに範囲を選び、新しいパターンで置き換えて、前後の場所を含めてスコアが良くなるのであれば確定、を10万回くらいループ
• 10万点くらいになる
• 縦と横と3x3のスコアを見ると、3x3がかなり低いので、改善を試みる
• 2行目は456/789/234で0点なので、以下のようなブロックにしてみる
  123456789
  456789123
  789123456
  231564897
  564897231
  897231564
  312645978
  645978312
  978312645
• あとランダム置換
• 16万点くらいいったので提出
• 8/22の中間発表で16位、まあまあ

3回目

• 気がつくと締め切り前日
• せっかくなので20万点の壁を超えるのを目標にする
• ブロックの位置をランダムにしてしまうと、ブロックの境界でスコアが伸びないのでいまいち
• なので全体は単一の割と良さそうなパターンでまず埋めて、小改善を試みる
• 固定値になっているためにスコアが失われているところを代替したら改善しそう
• 数値Aを書きたかったが、固定されていて数値Bになっているところを覚えておく
• 固定されていなくて数値Bを書いたところに数値Aを書いてみる
• 横の場合の例として、元データが200000000で223456789と埋めたときは、213456789にするという感じ
• 横、縦、3x3それぞれで、スコアが良くなったら決定する、を32x32の範囲で30ずつスライドさせて全範囲で行う(これで18万点くらい)
• ただし全体の評価値を上げるために、評価は50x50で行う
• それが終わったらランダムに数値を置き換えて良くなったら置換
• パターンを2通り+開始位置をずらすのも試す(2000点くらいしか効果はない)
• 20万点超えた!
• 提出(AM 3:45)
• ちょっと書き直した
• https://github.com/firewood/topcoder/blob/master/codeiq/tomerun.cpp

結果

203711点で14位。

提出の締め切り前後でしかやっていないのが反省点。プログラムより自分のスケジューリングに課題がある。

最初のわからなさ加減からすると相当楽しめた。