Chokudai Contest 001 に参加しました
Chokudai Contest 001 に参加しました。
CodeVS でマラソンマッチ楽しい〜となったので参加したいと思っていたんですが, btk さんがチームメイト募集してたので一緒に参加しました。
@btk15049 一緒に出たい気がします(途中で抜けちゃうかもですが)
— マヨ子@大天使クサハエル (@mayoko_) 2016年3月20日
チーム「まよバター」で出ました。まよバターで大根(Choku"dai" "Con"test なので)に出る…料理だな！
最終的には btk さんのアイデアメインに貪欲法でスコアを伸ばしました。僕は遷移候補に対してビームサーチをするのを担当していたんですが全然ダメでしたね…
チームとしての方針を書きたいと思います。
まず, 一番大きい数から削っていくのが基本的に有利です。これは, 具体的な数列を見ていくとわかります。間にでかい数字があったら, それは先に削ったほうが良いですね。
で, その中で貪欲に「一番数を削れるパス」を選んで, そのパスを選ぶ。その繰り返しです。
ただ, パスを考える際,
8 7 6 6 5 4 3
とかいうのがあった場合, 8 から削るよりも 6 5 4 3 を 1 回削った後 8 から削るほうが一気に削れてお得なので, それは考慮しています。
パスの候補をいくつか試した後, 適当な評価関数を作ってビームサーチ, というのも試しましたが上の方針より遅いし点数も低くなるしで全然ダメでしたね。
一番点数が良かった奴の submit -> Submission #669579 - Chokudai Contest 001 | AtCoder
で, 反省点。でかい数から削っていく, という方針はまぁ正しいですが, 「一番大きい数から削っていく」というのはちょっとダメだったかもしれないです。上で「一番大きい数から削っていく」のが有利な正当性を書いていますが, これは「周りが自分より小さい数しかない時削っていく」ことの正当性にしかなっていないので, そっちも試すべきでしたね。
