人生で 2 回目の、ヒューリスティックコンテスト（マラソン形式のやつ）に出ました。出ました達郎。
atcoder.jp
コンテストによって、開催期間が数日だったり時間だったりと色々ですが、今回は 4 時間でした。
結果は
パフォーマンス: 1363（水色相当）
レーティング: 559 → 813 (+254、入緑！)
ということで、アルゴリズム部門と同じくらいのスコアでした（アルゴリズム部門のレーティングも 1300 台）。嬉しい。
また、スコアで言うと結局トップの人たち半分くらいでした。トップ層すごいですね。
ちゃんと 4 時間ずっと集中しながら色々試行錯誤できて楽しかったので、4 時間の中でやっていったことをまとめていきます。
今回は、Scheme (Gauche 0.9.9) で解答を作成しました。
[目次]
- ちゃんと解答を出せるようにする（0 〜 17 分）
- 動作をシミュレートする関数を作る（17 〜 65 分）
- 盤面に対するスコアを計算する関数を作る（65 〜 120 分）
- 貪欲法を作成し、提出（120 分〜 133 分）
- 2 ステップ分の貪欲法を作成（133 分〜 170 分）
- ランダムを交えた 2 ステップ分の貪欲法に変更（170 分〜終わりまで）
- 振り返り
ちゃんと解答を出せるようにする（0 〜 17 分）
今回の問題は、対話形式のものです。
出力の後には改行をし、更に標準出力を flush しなければならない。 とかいう、よく分からない表記があります。
とりあえず、入力を受け、同じ文字を返しまくる関数を書いて提出するも、案の定 RE。
flush とやらができてないんだろうということで、「Gauche flush」とかで調べると、(flush-all-ports)という関数で flush ができるもよう。
それで再提出すると・・・無事に AC となりました。まずこれで形式に沿うことができるようになりました。
(define (read-n n) (if (= n 0) '() (let ((ele (read))) (cons ele (read-n (- n 1)))))) (define ColorVec (list->vector (read-n 100))) (define (simple-solve) (define (sub i) (if (>= i 100) 0 (let ((inp (read))) (begin (display "R") (newline) (flush-all-ports) (sub (+ i 1)))))) (sub 0))
提出してみた時のスコアは 28626229 でした。
動作をシミュレートする関数を作る（17 〜 65 分）
ここから、まずは起きる動作をシミュレートできるようにしていく必要があります。
最低限必要なのは、
- 新しい飴を置く
- 前後左右のどれかに傾けた後の結果を得る
- ある盤面に対するスコアを計算する
という関数です。
新しい飴を置く
盤面を、10 * 10 の二次元配列にはせず（面倒なので）、長さ 100 のベクトルとして持つことにします。何も置かれてなければ 0 、置かれている場合は 1 〜 3 を入れます。
置く場所の指定の仕方が独特で、「上の行から順に、同じ行なら左から順に、何も置かれていないところに番号を振っていく、そしてその番号で置く位置を指定する」という仕方です。何も置かれていないところをカウントしていって、置く場所を返す関数 color-set-index を作成することで、飴が置けるようになりました。
あと、今回は飴の『味』が 3 種類という問題設定ですが、「味って英語で何って言うんやっけ」という体たらくだったため、color という表現に変えています。
(define (color-set-index v i) (define (sub index count) (cond ((and (= (vector-ref v index) 0) (= count 1)) index) ((= (vector-ref v index) 0) (sub (+ index 1) (- count 1))) (#t (sub (+ index 1) count)))) (sub 0 i)) (vector-set! Table (color-set-index Table inp) (vector-ref ColorVec i))
前後左右のどれかに傾けた後の結果を得る
まず一旦は動作さえすればいいため、
- 右に傾ける関数
- 半時計周りに 90° 回す関数
を作って、それらを組み合わせることで前後左右の 4 方向へ傾ける関数を作ります。
右に傾ける関数は、各行の 0 でない成分のみでリストを作ったあとに、頭に 0 を cons していって長さを 10 にします。
回転は、一番左上の添字が 0 、その右が 1 、一番右まで進んで次の行の一番左が 10 で、、、と丁寧に追うことで作成します。
(define (right-shift v) (define (remove0 l) (cond ((null? l) '()) ((= (car l) 0) (remove0 (cdr l))) (#t (cons (car l) (remove0 (cdr l)))))) (define (fill0 l i) (if (= i 0) l (fill0 (cons 0 l) (- i 1)))) (define (get-ith-10 i) (define (get-n modulo-index) (if (>= modulo-index 10) '() (cons (vector-ref v (+ (* i 10) modulo-index)) (get-n (+ modulo-index 1))))) (get-n 0)) (define (sub i) (if (>= i 10) '() (let ((removed (remove0 (get-ith-10 i)))) (append (fill0 removed (- 10 (length removed))) (sub (+ i 1)))))) (list->vector (sub 0))) (define (rotate-90-left v) (define (sub junokurai ichinokurai) (cond ((< ichinokurai 0) '()) ((>= junokurai 10) (sub 0 (- ichinokurai 1))) (#t (cons (vector-ref v (+ (* junokurai 10) ichinokurai)) (sub (+ junokurai 1) ichinokurai))))) (list->vector (sub 0 9)))
これを組み合わせることで、各方向への傾けを書くことができます。
(define (fore-shift v) (rotate-90-left (right-shift (rotate-90-left (rotate-90-left (rotate-90-left v)))))) (define (back-shift v) (rotate-90-left (rotate-90-left (rotate-90-left (right-shift (rotate-90-left v)))))) (define (left-shift v) (rotate-90-left (rotate-90-left (right-shift (rotate-90-left (rotate-90-left v))))))
盤面に対するスコアを計算する関数を作る（65 〜 120 分）
これがかなりやっかいで、「縦横を見て、連結成分の個数を求めていく」のが必要になります。
各地点から、深さ優先探索を行うような方法で、なんとか書き切りました。これを作るのに 1 時間くらいかかりました。焦っていたこともあり、ごちゃごちゃです。
(define checkedv (make-vector 100 0)) (define (calc-score v) (define (sub startindex nowcolor nextchecklist nowvolume score) (cond ((>= startindex 100) score) ((= nowcolor 0) (sub (+ startindex 1) (if (= startindex 99) 0 (vector-ref v (+ startindex 1))) (list (+ startindex 1)) 1 score)) ((null? nextchecklist) (sub (+ startindex 1) (if (= startindex 99) 0 (vector-ref v (+ startindex 1))) (list (+ startindex 1)) 1 (+ score (* nowvolume nowvolume)))) (#t (let* ((nowpoint (car nextchecklist)) (nowlist (cdr nextchecklist)) (fpoint (- nowpoint 10))(bpoint (+ nowpoint 10))(lpoint (- nowpoint 1))(rpoint (+ nowpoint 1)) (fcan (and (>= fpoint 0) (= (vector-ref checkedv fpoint) nowcolor))) (bcan (and (< bpoint 100) (= (vector-ref checkedv bpoint) nowcolor))) (lcan (and (= (quotient lpoint 10) (quotient nowpoint 10)) (>= lpoint 0) (= (vector-ref checkedv lpoint) nowcolor))) (rcan (and (= (quotient rpoint 10) (quotient nowpoint 10)) (= (vector-ref checkedv rpoint) nowcolor))) (fdlist (if fcan (cons fpoint nowlist) nowlist)) (bdlist (if bcan (cons bpoint fdlist) fdlist)) (ldlist (if lcan (cons lpoint bdlist) bdlist)) (rdlist (if rcan (cons rpoint ldlist) ldlist)) (nextvolume (+ (if fcan 1 0) (if bcan 1 0) (if lcan 1 0) (if rcan 1 0) nowvolume)) (checked! (begin (if fcan (vector-set! checkedv fpoint 0) 0) (if bcan (vector-set! checkedv bpoint 0) 0) (if lcan (vector-set! checkedv lpoint 0) 0) (if rcan (vector-set! checkedv rpoint 0) 0))) ) (sub startindex nowcolor rdlist nextvolume score))))) (begin (set! checkedv (vector-copy v));checkedv というvectorを別に作る (sub 0 (vector-ref checkedv 0) (list 0) 1 0)))
注意として、今回のコンテストで指定されているスコア算出法と、定数倍ズレます。ただ、同じ問題に対し、定数倍ズレるだけで、よくなっているか or 悪くなっているかは、ちゃんと判定できます。
貪欲法を作成し、提出（120 分〜 133 分）
とりあえず一番最初に思いついた改良法として、貪欲法を試します。
「飴が置かれた後、最もスコアが大きくなる方に傾ける」という作戦です。
なぜか cond を使わず if でダラダラと、下記のように書きました。
(define (donyoku-solve) (define (sub i) (if (>= i 100) 0 (let ((inp (read))) (begin (vector-set! Table (color-set-index Table inp) (vector-ref ColorVec i)) (let* ((fscore (calc-score (fore-shift Table))) (bscore (calc-score (back-shift Table))) (lscore (calc-score (left-shift Table))) (rscore (calc-score (right-shift Table))) (max-score (max fscore bscore lscore rscore))) (if (= fscore max-score) (begin (display "F") (newline) (flush-all-ports) (set! Table (fore-shift Table))) (if (= bscore max-score) (begin (display "B") (newline) (flush-all-ports) (set! Table (back-shift Table))) (if (= lscore max-score) (begin (display "L") (newline) (flush-all-ports) (set! Table (left-shift Table))) (begin (display "R") (newline) (flush-all-ports) (set! Table (right-shift Table))))))) (sub (+ i 1)))))) (sub 0)) (donyoku-solve)
提出してみると、28626229 → 70521761 と、大幅にスコアが伸びました。
2 ステップ分の貪欲法を作成（133 分〜 170 分）
まだ時間があるので、とりあえず「2 ステップ先まで見る貪欲法」を書くことにしました。
「今、前後左右のどちらかに傾ける→その次にどこに置かれるか全てシミュレートし、そこから点数が最大になるよう傾ける」として、期待値が最も大きいものを取る作戦です。
(define for-donyoku2-v (make-vector 100 0)) (define (calc-next-kitaichi v left0count nextcolor) (define (sub i score) (if (> i left0count) score (begin (set! for-donyoku2-v (vector-copy v)) (vector-set! for-donyoku2-v i nextcolor) (sub (+ i 1) (+ score (max (calc-score (left-shift for-donyoku2-v)) (calc-score (right-shift for-donyoku2-v)) (calc-score (back-shift for-donyoku2-v)) (calc-score (fore-shift for-donyoku2-v)))))))) (sub 1 0)) (define (donyoku2-solve) (define (sub i) (if (>= i 99) 0 (let ((inp (read))) (begin (vector-set! Table (color-set-index Table inp) (vector-ref ColorVec i)) (let* ((fscore (calc-next-kitaichi (fore-shift Table) (- 99 i) (vector-ref ColorVec (+ i 1)))) (bscore (calc-next-kitaichi (back-shift Table) (- 99 i) (vector-ref ColorVec (+ i 1)))) (lscore (calc-next-kitaichi (left-shift Table) (- 99 i) (vector-ref ColorVec (+ i 1)))) (rscore (calc-next-kitaichi (right-shift Table) (- 99 i) (vector-ref ColorVec (+ i 1)))) (max-score (max fscore bscore lscore rscore))) (if (= fscore max-score) (begin (display "F") (newline) (flush-all-ports) (set! Table (fore-shift Table))) (if (= bscore max-score) (begin (display "B") (newline) (flush-all-ports) (set! Table (back-shift Table))) (if (= lscore max-score) (begin (display "L") (newline) (flush-all-ports) (set! Table (left-shift Table))) (begin (display "R") (newline) (flush-all-ports) (set! Table (right-shift Table))))))) (sub (+ i 1)))))) (sub 0)) (donyoku2-solve)
手元でやってみるとかなりスコアが改善されたため、いいんじゃない！？でも動作がモッサリで不安だわ・・・と思いながら提出したところ、TLE となりました。まぁ手元でも 10 秒以上かかってたもんね。そりゃそうか。
そのあと、「途中まで 1 ステップ貪欲法、途中から 2 ステップ貪欲法に切り替える」という作戦も取ってみたが、スコアは伸びず・・・
ランダムを交えた 2 ステップ分の貪欲法に変更（170 分〜終わりまで）
2 ステップ分を見るとスコアが改善されることは分かったので、これを「雑に、時間内に」動作されるコードを書くことにしました。
具体的には、「次の手で打たれうる位置のうち、一部だけ試す」作戦です。次のような関数を書き、input-list という引数で「どの位置を試すか」をコントロールします。
(define (calc-next-kitaichi-with-rand v input-list nextcolor) (define (sub l score) (if (null? l) score (begin (set! for-donyoku2-v (vector-copy v)) (vector-set! for-donyoku2-v (car l) nextcolor) (sub (cdr l) (+ score (max (calc-score (left-shift for-donyoku2-v)) (calc-score (right-shift for-donyoku2-v)) (calc-score (back-shift for-donyoku2-v)) (calc-score (fore-shift for-donyoku2-v)))))))) (sub input-list 0))
一旦、「次で打たれる手のうち、1 割くらいだけ試す」コードを書いて提出しました。上記の input-list に与えるものとして、このように生成することにしました。
(define (gene-10s maxindex) (define (hojo i) (if (> i maxindex) '() (cons i (hojo (+ i (max (quotient maxindex 10) 1)))))) (hojo 1))
そしてこれで提出すると、70521761 → 89149512 と、さらにスコアが伸びました。しかも実行時間は 2s ギリギリ。よしよし。
ただこのあと、一部の関数を高速化し、次の手の試す割合を増やしたりするも、スコアは改善されず・・・他の手法も思い付かず・・・これが最終スコアとなりました。
振り返り
このようなヒューリスティックコンテストには何度か出たのですが、そもそも毎回「n ステップ先までを全探索するコードを書き、n の値を落としていって実行時間に間に合わせる」というコードを書いています。
ここからスコアの伸ばすには、ちゃんと他の手法を知る必要があります。ヒューリスティックの解説もしてるという、鉄則本買おうかな・・・
終わりです。
