知識も経験もないため、ヒューリスティックならではの技法を使った解法は全く思いつかず、シンプルな実装でどこまでいけるか頑張っていました。
進化の過程
第1段階
多くの人が最初に提出したであろう、x y x+1 y+1
をとりあえず出しました。
第1.1段階
ここで何を思ったか、x y x+2 y+2
にできる(そばに別の点がいない)ときはする、というロジックを加えて出しました。(考え方に発展性がない・・・。)
スコアはおおよそ4倍になりました。(それはそう
第1.5段階
ふと思い立って、r
が最大の点を0 0 9999 10000
で覆って、他を空いた隙間にとりあえずおいておくという実装をしました。
思いの外スコアが伸びて桁が一つ増えましたが、上位勢と3桁違うため、ほえーってなってました。(語彙
第1.9段階
ここに至ってようやく、全部の点が含まれるように縞模様を作ってしまえばいいんじゃないかということに思い至ります。まずは点のそばでザクザク切っていく、という実装をしました。
スコアの桁数が上位勢と並びました。(桁数だけ
第1.99段階
今まで一方向でしかやっていなかったのを、縦と横でやってスコアが大きい方を取るということにしました。
それだけで8億点ほど伸びました。
ここで初めて、スコア計算のロジックを書きました。(遅い
第2段階
上の画像の通り、単に切るだけでは無駄がおおいので、とりあえず赤いところをなくすように調整しました。
隙間なく埋まっている状態なので、まずは過剰な部分を削ることしかできないのです。
これだけで一番上の位の数字が一つ増えるくらい伸びました。
第3段階
過剰な部分を削ってできた隙間を不足部分の補填に使えるなら使う、という実装を足しました。上下の画像を比較して、無駄な隙間が少しだけ減っているのがおわかりいただけますでしょうか。
ここで一番上の位が上位勢と並んだので、ほぼほぼ満足してしまいました。(おい
第4段階(未遂)
満足度の計算式からは、面積ピッタリのものと全然足りてないものの組よりそこそこあっているもの2つの組のほうがスコアが高くなるので、境界線を移動させることでさらなる最適化を図ろうとしたのですが、何故かスコアが悪化しかせず、ここで投げてしまいました。
結果(暫定)
42,576,059,015点で暫定798位のようです。
結果(最終)
853,242,491,282点で772位でした。結構上がりましたね。
まとめ
こんな単純な考え方でも桁数だけなら上位と並べるしそんなに時間も頭も使わずに済むので(いや、頭は使おう?自分)、気軽にやってみるのもいいんじゃないかなーと思いました。
ただ、次回以降は徐々にヒューリスティックならではの技法も取り入れていきたいですね。