マラソンマッチの簡単な解法 - じじいのプログラミング

まえがき

この記事は、Competitive Programming Advent Calendar 2017 - Adventar 18日目の記事です。

最近は、簡単にやるべきことでも、難しくやってしまうことが多く、それがマラソンマッチでの不振につながってるので、「簡単な解法」をネタに書きます。

昔、自分でこう言ってました。

敗因：誰でも思いつくようなケースをほとんど試さなかった。
特に、時間がかからずに実装できるものは、絶対試したほうがいいです。仮に全然結果がでなかったとしても、その後のヒントになる可能性もありますし、条件によっては使えるかもしれません。今回、自分の考えたのは実装時間がかかるため、それが外れ方針なのに気づくのに時間がかかってしまいました。

はい、その通りです。でも、その最初に作りたい簡単な解法が、年々思いつかなくなってきているので、復習しようと思います。マラソンマッチ初級者向けの記事です。

問題

Topcoder Marathon Match 95 CirclesMix を取り上げます。

できること
- 好きな位置・大きさ・色の円を指定個数置けます。最初は真っ黒のフィールドで、円を置くと、(置いた円の色＋フィールドの色)*2になります。
条件
- （平均的な条件は）円の数=500, 座標=0～500, 色赤青緑=0～256
スコア
- 目標になる画像に近い画像を作った人が勝ち（スコアは、目標画素と作った画像の画素の絶対値の差の和で、低い程よい）。

f:id:shindannin:20171219080724p:plain

以下は解法の例（アニメーション）です。
https://www.topcoder.com/contest/problem/CirclesMix/2.gif

この問題のベストな解法はおいといて（MM 95 - Togetterを見て）、今は、最初に作りたい簡単な解法について、考えてみます。

簡単な解法（失敗例）

例えば、
「平面を４方向に動くロボットを動かして、落ちているコインを集めよ！」
という問題だったら、コインまでの近さをスコアにして、上下左右４方向について試して、もっとも高スコアな方向に動かすとかやれば、それなりに動くでしょう。これで良いと思います。

ただ、この問題で、貪欲で一番良い選択肢に、円を１つずつ置いていくといっても、とりうる選択肢が多いときは、計算時間が間に合わなくなりがちです。（「解空間が大きい」という人もいます）

貪欲法をそのままやるとすると、

for(int circle=0;circle<500;++circle) // 円の番号circle
{
  // 円をスコアが最も上がるベストなところに置く。
  for(int cy=0;cy<500;++cy) // 円の中心座標cy
    for(int cx=0;cx<500;++cx) // 円の中心座標cx
      for(int r=0;r<500;++r) // 円の半径
        for(int R=0;R<256;++R) // 塗る色 赤R
          for(int G=0;G<256;++G) // 塗る色 緑G
            for(int B=0;B<256;++B) // 塗る色 青B
            {
              // 塗る点ごとに得点計算
              int score = 0;
              for(int y=cy-r;y<=cy+r;++y)
                for(int x=cx-r;x<=cx+r;++x)
                {
                   score += ....
                }
            }
}

みたいなかんじのコードになって、forループの回数が、ざっくり500*500*500*500*256*256*256*500*500となり、ひどく重くて動かないわけです。そこで対策というか、適度な手抜きが必要になります。

簡単な解法（改善例）

１．ランダム

ランダムは速い、何でも計算量O(1)にするので、すごい。この問題だったら、最初にやるべきです。

for(int circle=0;circle<500;++circle) // 円の番号circle
{
  // 100箇所試して、スコアが最も上がるベストなところに置く。
  for(int turn=0;turn<100;++turn)
  {
    cy = rand()%500;
    cx = rand()%500;
    r = rand()%500;
    R = rand()%256;
    G = rand()%256;
    B = rand()%256;

    // 塗る点ごとに得点計算
    int score = 0;
    for(int y=cy-r;y<=cy+r;++y)
       for(int x=cx-r;x<=cx+r;++x)
       {
         score += ....
       }
    }
  }
}

これだけでも、ループ回数は500*100*500*500と激減します。解は良くないですが、簡単に書けますし、最初の解法としてはアリだと思います。

２．固定

ばかげていると思うかもしれませんが、この問題であれば、円の半径rについては固定でも、それなりの解は作れます。まずは簡単な解でいいので、固定も全然ありです。

３．粗くする

問題の特性上、粗くしても（画像を縮小して、色調も減らす）、それなりの解がでそうです。例えば、すべてではなく、10おきに調べるようにすれば

for(int circle=0;circle<500;++circle) // 円の番号circle
{
  // 円をスコアが最も上がるベストなところに置く。
  for(int cy=0;cy<500;cy+=10) // 円の中心座標cy
    for(int cx=0;cx<500;cx+=10) // 円の中心座標cx
      for(int r=0;r<500;r+=10) // 円の半径
        for(int R=0;R<256;R+=10) // 塗る色 赤R
          for(int G=0;G<256;G+=10) // 塗る色 緑G
            for(int B=0;B<256;B+=10) // 塗る色 青B
            {
              // 塗る点ごとに得点計算
              int score = 0;
              for(int y=cy-r;y<=cy+r;++y)
                for(int x=cx-r;x<=cx+r;++x)
                {
                   score += ....
                }
            }
}

これだけで、10*10*10*10*10*10の1000000倍速くなります。もちろん解は悪くなるのですが、最初は粗くして速攻でイマイチな解を求めて、その解の結果を生かして、重要な部分を徐々に細かくしていくという方法も有効です。

簡単な解法（あまり簡単ではない例）

４．独立させる

この問題、得点計算の部分、色R,G,Bは独立していました。そういう場合、バラで計算すればforループをバラすことができます。

for(int circle=0;circle<500;++circle) // 円の番号circle
{
  // 円をスコアが最も上がるベストなところに置く。
  for(int cy=0;cy<500;++cy) // 円の中心座標cy
    for(int cx=0;cx<500;++cx) // 円の中心座標cx
      for(int r=0;r<500;++r) // 円の半径
      {
        for(int R=0;R<256;++R) // 塗る色 赤R
        {
          int scoreR = 0;
          for(int y=cy-r;y<=cy+r;++y)
            for(int x=cx-r;x<=cx+r;++x)
            {
               scoreR += ....
            }
         }

        for(int G=0;G<256;++G) // 塗る色 赤G
        {
          int scoreG = 0;
          for(int y=cy-r;y<=cy+r;++y)
            for(int x=cx-r;x<=cx+r;++x)
            {
               scoreG += ....
            }
         }
        for(int B=0;B<256;++B) // 塗る色 赤B
        {
          int scoreB = 0;
          for(int y=cy-r;y<=cy+r;++y)
            for(int x=cx-r;x<=cx+r;++x)
            {
               scoreB += ....
            }
         }

}

解は同じですし、計算量は256*256*256⇒256と、1/65536になります。いつでも使えるわけではないですが、独立している要素がないかチェックしましょう。

５．前の計算結果を再利用

以上のケースでは、スコアを毎回１から計算していましたが、例えば、半径や塗る色などそのままで、cxとrを+1大きくするとしましょう。ほとんどの範囲は被るので、その範囲の計算は端折ることはできるはずです。下図左のcxを+1大きくする場合は、青い部分を足し、赤い部分を引く。下図右のrを+1大きくする場合は、青い部分を足すだけです。紫の部分は再計算する必要はありません。
f:id:shindannin:20171219073716p:plain
または、差分（微分）は前計算でき、メインの計算量に影響を与えないことも多いです。それぞれの変数に対しての差分を一度は検討してみましょう。これは貪欲法だけではなく、焼きなまし法などの近傍を高速に求めるときにも有効です。

６．部分的な最適化

もし部分的にでも最適解が総当たりよりも高速に出せるのであれば、それで計算量を減らすことができます。この問題、実は、円の位置cx,cyと円の半径rが固定であれば、色RGBの最適解は、円の範囲内で(2*目標画像-現画像)についてのヒストグラムをつくり、色の中央値が塗る色の最適解となります。（ヒント：スコアを塗る色で微分し、それが0になるところが最適解。微分のかわりに塗る色を+1するとスコアがどう変化するかを考えるとわかる）
そのほかにも、二分探索・三分探索・動的計画法などSRMで使えそうなアルゴリズムも考慮するといいです。焼きなまし法などの最適化アルゴリズムも高速化の手段の１つですが、最初の簡単な解法とは、だいぶ離れてしまうので、まずは1～5を考えてみてください。

（重要：他にも、こういうのがあるよというのがあったら、教えてください！）

まとめ

というわけで、貪欲法を実現するにも一苦労です。でも、解は悪くてもいいので、最初の解法までは、早くたどり着いたほうがいいと思います。
なお手法は６種類だけだとしても、何に対してどの手法を適用するのかと考えると少なくありません。少し例を挙げただけも、いくらでも作れそうなのが分かると思います。

円の位置cx,cyと半径rは粗くして、色RGBだけランダムを使う。
RGBはforループでまわして、円の位置cx,cyと半径rについてのみ最適化アルゴリズムを適用。
円の半径rは固定して、円の位置cx,cyはforループですべて試す、色RGBについて部分的な最適化。

上位者が「解法は、〇〇はランダムで△△は貪欲でした」と簡単に言ってたとしても、そこに至る過程でいろんな選択肢があったうえでベストなのを選んでいるわけで、決してそこは簡単ではないんですね…。

あとがき

それがマラソンマッチの奥の深さ・難しさ・楽しさでもあるので、ぜひみなさんも参加しましょう！最近のですと、

AtCoderのWeathernews Programming Competition - Weathernews Programming Competition | AtCoder 2017年12月15日正午から2018年1月15日正午まで
Topcoderの Marathon Match 96 2017年12月21日11:00から28日11:00まで。

などがあります。

明日の12/19のCompetitive Programming Advent Calendar 2017 - Adventar は、shisashiさんの「競プロ用に作成したエディタのプラグインを紹介します」です。楽しみですね。それでは、また！