olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

Marathon Match 95

画像が与えられるので、指定された数の半透明な円を描いていって元の画像に近づけようという問題。

作成途中の画像の状態だけが重要で配置の順番はどうでもいいと思ったのでビームサーチ案を捨て、貪欲に円を配置していくことを考えた。

貪欲パートは、ランダムな位置にランダムな大きさ(大きさは進度に依存する)の円を描くことを考えたときに、変更前、後の各RGB成分の平均を取り、そこから求めた色を塗ることとした。

外側重視とか画像の隣接するマスの近似度とかを使おうと思っていろいろやっていたけどそちらはうまくいかなかった。(最終的に円は小さいので外側重視に意味があまりない?)(思いついたのが最終日の2時ごろなので時間がなかった)

0)1.2455719E7

1)1.6093684E7

2)2.5773614E7

3)1.1478683E7

4)7802575.0

5)1.1083905E7

6)4.0074287E7

7)2.4999824E7

8)1.981949E7

9)3.5520464E7

MM/MM95_loop.cpp at master · olphe/MM · GitHub