TCO19 Marathon Match 107 参加記録 - seriruの技術屋ブログ

TopcoderのMarathon Match 107に参加しました。初参戦だったのもあってたいしたことは書けませんが、記録のために残しておこうと思います。

問題

https://www.topcoder.com/challenges/17405?tab=details

やったこと

1日目

問題を見る。
英語だ(当たり前)。とりあえず...

Grid内のsubgridが $Kmin \leq x \leq Kmax$ の範囲で色を塗る。
塗ったマスに書かれている数字の合計値が得点になる。
この得点を最大化せよ。

という問題だと読み解いた。

方針を考える前にviewerを動かして見る。
問題ページにリンクが貼ってあるのでダウンロード。
ついでにc++の解答例もダウンロード。

$ java -jar tester.jar "<command>" -seed <seed>

で動かせるらしい。実行すると問題ページと同じものが出てきた

f:id:ryo_seriru:20190131144127p:plain

いちいちコンパイルして, viewerを実行するのも面倒なのでMakefileとスクリプトを書いて

$ ./build.sh <seed>

でコンパイル & シード値指定の実行をできるようにした。

ここから方針を考える。

$H * W$ のGrid内に $h * w$ のsubgridは $(H - h + 1) * (W - w + 1)$ 個ある。
1つのsubgridにできるだけ $Kmax$ 個に近い数, マス目の色を塗ることができれば得点は高くなる。
当たり前だが, 色を塗るマス目もできるだけ大きい数字を選びたい。

これらを踏まえて, 各subgridに対して貪欲に大きい方から $Kmax$ 個色を塗ってみる。
subgridの全探索は四重ループで再現できるので, 実装は時間がかからなかった。
これをやると

seed = 1
H = 8, W = 8, h = 3, w = 4, Kmin = 0, Kmax = 5
60856174
75928915
89719086
16627659
32982909
13815950
55717858
91260290
Subgrid starting at (0,0) contains too many painted cells
Score = -1.0

1つのマスに色を塗ると他のsubgridにも影響出るしそりゃそうだよねという感じに。

なら塗り終わった後にsubgridの $Kmax$ を超えていたら, 塗られているマスの中で一番小さいものを消すという操作を追加してみる。

これをやると $seed = 1$ は通るようになったので公式のサンプルを実行してみる。(結果メールで来るのびっくりした。)

seriru13,
Your test for the problem PointsOnGrid has completed.

Example scores: 
0) 165.0
1) -1.0
2) 4146.0
3) 1489.0
4) 2150.0
5) 1587.0
6) 1631.0
7) -1.0
8) 6103.0
9) 923.0

2つのテストケースでscoreが-1になってしまった。
でも正の点数はもらえそうなので提出。

seriru13,
Your test for the problem PointsOnGrid has completed.

Overall score: 641379.51

とりあえず正の点数はもらえたので寝た。

2 ~ 6日目

卒論やばくない？となる。
さらに実験もしようと言われる。
それに加えて卒研発表のプレゼン練習もしないといけない。
時間が足りずあまり考えられなかった。

最終日

score = -1になる理由を考える。
といっても原因は簡単でsubgridの一部が $Kmin$ だけ塗られていないことだった。

それを踏まえて,

(1) subgridを選ぶ。
(2) subgridの塗られているマス目が $Kmin \leq x \leq Kmax$ であったら(1)に戻る。
(3) $x \lt Kmin$ だったら塗られていないマス目の中で最大のマスを塗る。(1)に戻る。
(4) $x > Kmax$ だったら塗られているマス目の中で最初のマスを消す。(1)に戻る。