失敗談:飛行機に2度乗れなかった話

日本のプロコンに参加するため、シンガポール→日本→シンガポールの往復チケット(55000円)で帰国しようとしたのですが、寝過ごしてしまい乗れませんでした。ばか。しかも、ギリギリ間に合わないとかではなく、出発時刻25分前に、家で目覚めるという、惜しくもなんともない状況だったので、空港にすら行きませんでした(←ポイント)。

しょうがないので、別のチケットを取ることにしたのですが、落ち着いて考えたところ、シンガポール→日本→シンガポールのチケットを持っているわけだから、行きのチケットだけ改めてとれば、最小限の被害で済むと思い、別の航空会社の片道のチケット(37000円)をとりました。それで、日本へ。しかし、これが最悪の判断となることに…。

4日後、

日本→シンガポールへ帰る日、インターネットでチェックインしようとしたのですが、なぜか受け付けてくれません。電話で問い合わせてみたところ、なんと、席はないとのこと!?行きのフライトに搭乗しなかったので、NO SHOW扱いとなり、帰りのフライトも自動でキャンセルされてました…。そもそも、チェックインって、行きのチェックインと、帰りのチェックインで、別々だと思っていました…。

なんとかならないか聞いたところ、「1日遅らせれば、追加料金13万円で帰りのチケットを用意できる」と言われましたが、もうそれって2.5往復相当の絶望的金額…。あきらめました。結局、別な航空会社で、帰りの片道チケットをとることに(37500円)。往復チケットでいいのに、バラで片道チケットを2つとった分、さらなる損を重ねることに。
(平日だったため、行き片道37000円+帰り片道37500円程度でなんとかなりましたが、仕事で当日に帰らないといけないとかだったら、とんでもない損害になってたと思います)

ちなみに、大遅刻して乗れなかった場合でも、念のため空港のカウンターに問い合わせたほうが良いです。追加手数料を払えば、帰りのフライトだけは搭乗できる場合があるとのこと。ただ、その追加手数料も数万円かかり、しかも片道のチケットも別にとらないといけないので、たいていの場合は、往復チケットを取り直したほうが安いかと思います。でも、距離や航空会社で条件は違うと思うので、行きの飛行機に乗れなかった場合でも、航空会社の空港のカウンターに行くか、問い合わせると良いと思います。

まとめ

  • 往復チケットで、「行きは乗らず、帰りだけ乗る。」は不可能。
  • 通常は、また往復チケットを取り直したほうが良い
  • 遅れたとしても、航空会社に問い合わせよう。

おまけ

  • 慰め突発オフが発生しました。ありがとうございました!
  • 成田空港のAIボットが慰めてくれるので、良いです。

TCO Announcement Fun Round - WaterfallFishingの反省

2017年5月の、ちょっと古いマラソンマッチですが、忘れないようにするために、書きました。

問題

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16930&pm=14615

川の幅 W (2≦W≦200)
川の長さ L (5≦L≦100)
川には、岩がある。(5≦岩の数≦W*L/10)。ただし、岩の場所は、分からない。

まず、D日間連続で、魚が上流から下ってくる(4≦D≦20)。

  • 5≦魚の数≦100
  • 魚は、魚群の中心の位置M・標準偏差Sの正規分布で、まず上流に配置される。(0≦M≦W-1, 2≦S≦W/4)。M,Sも分からない。
  • 魚はまっすぐ下るが、岩にぶつかると50%の確率で左に1マス、50%の確率で右に1マスずれて落ちる。
  • 魚が、下流に下ってきた魚の数は、場所ごとに分かる。

f:id:shindannin:20180103184334p:plain

(範囲になっている変数は、テストケースごとに、ランダムに均一に選ばれる)

D日間分の下流に下ってきた魚の数の情報を用いて、D+1日目に落ちてくる魚の場所を予測し、罠をしかけて、できるだけ多く捕れ。スコアは、(捕まえた魚の数)/(罠を仕掛けた数)で決まる。与えられた計算時間は60秒間。

方針

機械学習で予測した。ただ、この問題、データが足りなすぎる、かつ、あまり当てにならない。魚群の位置M,Sは毎日変わるので、ここの予想が外れると、ほぼ魚を捕れない。そういうわけで、機械学習は避けて、確率の知識などで解答した人が多かったっぽい。
ただ、自分は機械学習でごり押しした。データ不足を補うために、自前でデータを生成した。やり方は以下の通り。

(1) 「岩配置」と「下流に下ってきた魚の数のデータ」のペアを、問題と同じ方法で200種類生成。
(2) 「岩配置」から、下流に下ってきた魚の数の期待値を場所ごとに求める。上流の魚の確率分布は、1000万回シミュレーションして求めた(数学強い方なら解析的に求められる)。上流での魚の確率分布と岩の配置を用いれば、簡単な期待値DPで、下流に下ってきた魚の数の期待値を求められる。これを機械学習の目的変数(予測したい値)として使用。
(3) 「下流に下ってきた魚の数のデータ」は、機械学習の説明変数(特徴量)の生成のために使用。最終的には以下を説明変数として用いた。

  • 下流の位置 X
  • 川の幅 W
  • 川の長さ L
  • 魚の数

さらに、Xの近傍のデータも説明変数に追加した。近傍をY (X-3 <= Y <= X+3)として

  • D日間で、Yに下ってきた魚の総数
  • D日間で、Yに下ってきた魚の割合の和
  • D日間で、Yに下ってきた魚の総数とXに下ってきた魚の総数の差

(4) あとは、自前のランダムフォレスト(そろそろ、自前Gradient Boosting系のものを用意しておきたい…)で50秒間訓練。
(5) 全ての位置Xで、下ってきた魚の期待値を予測し、もっとも期待値が大きい場所1か所に罠をしかけた。

まとめ

他人の解法と、自分の解法がズレてたおかげで、まさかの1位!機械学習しても2位のスコアとの差は大きくないのですが、不確定要素が多すぎるこの問題においても、機械学習が有効だったのは、自分でも驚いた。データ生成の仕方が重要。

実は、このマッチはあまり時間の余裕がなく、また直前のマラソンマッチのミスでレートを大きく下げていて弱気になり、参加する予定はなかったのだけど、tomerun氏の無言の煽り励ましツイートで、参加することになったのでした。マラソンマッチは、最後まで何が起こるかわからないので、皆さんも参加しましょう!

マラソンマッチの簡単な解法

まえがき

この記事は、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を見て )、今は、最初に作りたい簡単な解法について、考えてみます。

簡単な解法(失敗例)

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

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

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

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となり、ひどく重くて動かないわけです。そこで対策というか、適度な手抜きが必要になります。

簡単な解法(改善例)

1.ランダム

ランダムは速い、何でも計算量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と激減します。解は良くないですが、簡単に書けますし、最初の解法としてはアリだと思います。

2.固定

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

3.粗くする

問題の特性上、粗くしても(画像を縮小して、色調も減らす)、それなりの解がでそうです。例えば、すべてではなく、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倍速くなります。もちろん解は悪くなるのですが、最初は粗くして速攻でイマイチな解を求めて、その解の結果を生かして、重要な部分を徐々に細かくしていくという方法も有効です。

簡単な解法(あまり簡単ではない例)

4.独立させる

この問題、得点計算の部分、色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になります。いつでも使えるわけではないですが、独立している要素がないかチェックしましょう。

5.前の計算結果を再利用

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

6.部分的な最適化

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

(重要:他にも、こういうのがあるよというのがあったら、教えてください!)

まとめ

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

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

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

あとがき

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

などがあります。

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

Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017の反省

AtCoderで初の本格マラソンマッチ。楽しかったです。13位/302。最近のマラソンマッチ不振を考えれば良い結果だったけど、反省点も多かったです…。
(方針の公開がOKになったので、公開します。2ndがあるので、ちょっと迷いましたが、北大日立さんにとって良い結果が出たほうが、今後さらなるマラソン開催にもつながるので、公開します。)

ファーストインプレッション(2017/11/16)

  • どういうデータなのか?
    • 辺の数とか、平均でいくらぐらいなんでしょう? →辺は思ってたより多い。100本以上辺があるのは普通。
  • 最適解がわかるケースを逆につくれば便利。最適解を知っていれば、焼きなましをやってみたときに、うまくいってるかわかる。
    • King's graphから作る
    • 一定条件を満たせば、そこから辺を足しても最適解をキープすることは可能?より一般的&難しい問題が作れる
      • 三角不等式を満たすものは除去してもいい?
    • このときに意図的に最適解をつくる操作が、逆の操作が近傍として有力な可能性はある。
  • より簡単なケースで考えてみる。
    • King's Graphではなくグリッドグラフにマッピングする場合は?二部グラフに持ち込める?
      • 最大流かカット系で楽にできないか?
      • 使えなくても、初期解として有効な可能性があるので、無駄にはならないと思う。
  • 過去の反省
    • 類問の解法に固執しすぎ。
      • 今回のは、TCO17 MM Round 1 TCO17 Marathon Round 1 (GraphDrawing) の反省 - じじいのプログラミングに似てる気もする。そうすると優勝したchokudaiさん解の重力モデルか焼きなましの中間っぽいのが有効なのか?
      • ただ、ちょっと条件がちがっただけで、解法が全然違うことがある。まっさらでスタートしたほうがいいのでは。
  • 方針
    • ベタに行けばこの問題は、ただの焼きなまし。そして、最後に焼きなましの解をダメ押しでGreedyするの忘れずに。
    • 粗いグリッドで焼きなましから、徐々に細かいグリッドにして焼きなまし。
      • ただし、先日tomerunさんと似た解法だったのにもかかわらず、自分だけ大敗したので、ちゃんと敗因を確認すること。特に、細かいグリッドになったときに調整できるかどうかもポイント。
  • ランダムグラフの頂点間距離は使える?
  • 高得点辺だけを使ったのGreedy・焼きなまし
    • 1点や0点の辺は無視してもいいくらい。というか0点は最初から削っていいのでは。
  • 何を焼きなまし?(「近傍の種類の多さが重要」と昔Komakiさんが言ってた)
    • 頂点ベース
    • 頂点ベース(位置を気にする。近傍は近くの点)
    • 辺ベース
    • 15点→0点で、辺をじょじょに開放
    • 場所を後から、配置する解法はないか?よく、「置く場所を決める焼きなまし」→「何を置くか決める焼きなまし」のように、2段階に分けると良いこともある。

Submission 1 (2017/11/18) 52935点

同じ番号の頂点をマッピング。同点のみなさん多数。

その後、多忙で無事乗り越えたものの、休日に冷房病になってしまい、計1週間休み。すごく警戒してたのに…。

Submission 2 (2017/11/25) 129838点

場所2箇所の交換(頂点あるなしは気にしない)を100万回する山登り法。

Submission 3 (2017/11/25) 148673点

場所2箇所の交換(頂点あるなしは気にしない)を、9秒間する焼きなまし法。

Submission 4 (2017/11/26) 152871点

焼きなまし法の、温度を5度→1度にする。わりと効果があった。

ビジュアライザ

このタイミングでビジュアライザも追加する。 Siv3Dを今回も使いました。感謝→ Siv3D · GitHub)ビジュアライザは、

  • 押すボタンごとに、いろんな近傍への遷移をリアルタイムで試せる。
  • 頂点ごとに最高点と現在の得点を追加。ちなみに、最高点はベスト8の総和。

f:id:shindannin:20171130222251p:plain

ただ、ビジュアライザをつくっても、なぜ問題が起きてるのかにちゃんと着目した情報を表示して、本質を見抜けないと意味がないので、気を付ける。
このchokudaiさんの記事はおすすめ(というか、悪い例にでてくるモデルは、たぶんわしじゃ…。)
chokudai.hatenablog.com

焼きなまし法の温度と得点、統計情報(どの近傍で、どれだけ上がったか)等も、グラフプロットに追加すればよかった。

Submission 5 (2017/11/26) 159335点

動かす頂点Aと、元グラフでつながっている頂点Bの隣に移動。上位の人が多く使っていた有効な近傍。

セカンドインプレッション(2017/12/26)

  • 焼きなまし温度調整必須
  • 15点の辺だけ使って、辺を少なくして、橋・関節点で分けて、
  • 浮いている点の15とかは重要?
  • 15,15,15,15,15,15,15,15,15,15,15,15,15,15,5,5,5 みたいなときは代替があるので、あとで決めていい
  • 塊ごと移動できない?
  • 番兵で、範囲チェックのifを減らせ
  • 範囲広すぎだと、ダメかもしれない。60x60ではなく、範囲を狭くしたら。
  • 範囲なしにして、あとからくっつけたほうがいいかも。

Submission 6 (2017/11/27) 159913点

  • 元グラフでつながっている頂点Bは、高得点ベスト8の隣接頂点から選ぶ。かつ、焼きなまし法を2倍高速化

★★★★ 高速化がどれだけ効果的か検討する。
のも重要です。ためしに10秒だけやってる計算を、あえて100秒とかに伸ばしてみて、結果がどうなるか見てみましょう。

  • 時間をかければかけるほどスコアが伸びる
    • 高速化しよう&スコアが素早く伸びるように次の状態を決めよう。山登り法に変えるのも良い。
  • 時間をかけてもスコアが伸びない & スコアが高い
    • 最適解がでてる可能性が高い。計算を打ち切って、余った時間を他に使う
  • 時間をかけてもスコアが伸びない & スコアが低い
    • 次の状態の決め方、スコア関数の見直しを再検討する。焼きなまし法を使わない法がよいときもあるのも忘れずに。

を試した。なんと計算時間を10倍にすると、30ケースあたり平均+5000増える!!(実際には30ケース*10セット)1位が狙える位置に行くことがわかる。

でも、10倍高速化するのは無理だろうなという考えと、まだ試してないアイディアがいっぱいあるので、まずそちらからやることにした。これが敗因の1つ…。
10倍で効果があるのだから、せめて、計算時間を5倍にしたら、計算時間を2倍にしたら、どれだけ増えるのか試して、それをみて高速化にどれだけ作業するか考えるか判断すれば良かった。

失敗したアイディア集

ここから点数がさっぱり増えなかった、ボツアイディア集。反省点の1つとして、結果の確認とまとめを、もうちょっとちゃんとしてれば良かった。失敗したアイディアの中では、点がほとんど変わらなかったものもあるけど、これは下手すると最終盤でちょっと点数を上げたいときに有効な場合もあるので。

初期値

初期値がわるいとダメなケースもある。特に、今回のは、わりとバラバラに頂点が飛んで非効率に見えたので、初期位置を中央に固めた。でも、すぐに結局バラバラに飛んで行って、スコアが上がらなかった。

バラバラにならないようにする。

中央に行くほどボーナス点をつけたり、KingGraphの隣に頂点があるときにボーナス点をつけた。バラバラになりにくくなったけど、スコアはだいぶ下がった。バラバラシャッフルっぽい動きは有効だったっぽい。

頂点Aを意図的に選ぶ。

頂点得点の最大値(頂点の辺ベスト8の合計)をあらかじめ計算しておき、交換する頂点を、以下のような基準で選ぶけど、これもだいぶ点が下がった。

  • 低得点率(現在の得点 / 最大値)
  • 得点差(最大値 - 現在の得点 )

yowaさんのなんか他の人の解法をみるに、全てを均等回数を選んだほうがいいという議論もあるらしい。


次回は要検討。

隣接頂点Bの選び方

Submission 6「元グラフでつながっている頂点Bは、高得点ベスト8の隣接頂点から選ぶ」の部分が、あまりに雑だったので、ここはスコアは伸びるかなと思ったけど、伸びなかった。辺得点x,y,zだったら、選択確率は、pow(x,t)/(pow(x,t)+pow(y,t)+pow(z,t))のようにして、tを調整した。tが0なら全部等確率1/3, tが∞なら最高辺得点のだけが確率1になる。でも、スコアは伸びなかった。

さまざまな近傍

「近傍をたくさん作ったほうが勝つ」と、Komakiさんが昔言ってたので、いろいろ足した。

  • 2-Swap
    • 隣り合う2点を交換。A→B, B→A
  • 3-Rotate
    • 三角の形で隣接する3点を、A→B, B→C, C→Aのように移動。ある頂点Aを固定すると、三角形の選び方は12パターンある。
  • 4-Rotate
    • 四角の形で隣接する4点を、A→B, B→C, C→D, D→Aのように移動。
  • スライド
    • 縦 or 横 or 斜めに一列にならんだx点(2点~4点)を一方向に押してスライドさせる。A,B,C,Dと並んだ場所で、A,B,Cが頂点があって、Dが空きのとき、C→D, B→C, A→Bと移動させる。

それぞれに対して、全てのマスが頂点埋まっているバージョンと、そうでないバージョンを試した。また、近傍については確率で選んで調整する(辺隣接ワープ 95%, 2-swap 4%, 3-Rotate 1%とか、そんなかんじ)

  • 空きマスが一部ある場合の結果は、概してよくなかった。
  • 2swapについては、低得点の際には効果があるように見えたが、マッチの終盤にはほぼ意味がなくなったので、最終的には、これらの近傍は全てボツとなった。

また、本当なら、別な動きをする近傍をいろいろ作ったほうがいい。今回の3-Rotate, 4-Rotateは、2-swapで2回,3回で代用可能かつそれなりの確率で起こりうるので、あまりよくない近傍(ただ、それでも1回は試すべき。)

レプリカ交換法

ほぼやけくそ。N個の焼きなまし法を同時に走らせる方法。それぞれ別な温度を固定でもつ。一度やってみたかったので、やった。
レプリカ交換法 - Wikipedia
得点差に応じて、温度を入れ替える(状態を入れ替えるより簡単。)
これは、あまり有効でない。中途半端な得点の解がたくさんできるだけだった。特に、今回のように時間をかければスコアが伸びるケースでは、時間が1/Nになるのはもったいない。1つに集中して時間をかけたほうがいい。ただ、並列計算とかできる環境であれば、有効なケースもあるのかも。

プロファイラで高速化。

この時点で、最終日で、残り4時間ぐらいになってしまった…。Visual Studioの標準機能のプロファイラを使って、高速化する。しかし、時間が足りず、結局、以下の2つは高速化せずに終わってしまった。

  • 番兵で範囲チェックをなくす
    • ファーストインプレッションにも書いたのに。時間がなくなってしまった。番兵など、最終盤で、高速化するにはバグを埋め込むリスクが高いところは、もっと早めに高速化やったほうがいい。
  • 焼きなましのexpの式
    • あわててテーラー展開したやつを書いたけど、点が下がったので、怖くなったので、やめた
    • 焼きなましのexpの式なんて毎回使うのに、高速化を最終盤にしようとして、おざなりになるのを繰り返してるのは、本当にダメである…。効果が少なくても、1度作れば一生使えるのは、暇なときにしっかり作りましょう。

自分のは、7000万回程度しか回らなじゃった。他の人は2億~4億ぐらい回っている。その中でもっとも怪しいのが、ケチらずintとかdoubleとか大きい方を使っていたこと。一般に、プロファイラはボトルネックにはすぐにきづくが、全体的に遅くなってる要素には気づきにくいので、要注意。ただ小さい型を使うのが、これだけ早くなるのは意外。キャッシュミスあたりが予想されるけど、今回のフィールドは小さいので、過小評価してた。自分がなんか誤解している可能性も高い。要調査。

その他

  • お尻に火がついたのが、いつもより少し早かった。
  • 若くないので、体調管理は大事。冷房病は徹底した温度管理で避けよう。
  • 昔は、夜遅くなっても次の日なんともなかったけど、今はリバウンドがくるので、ちゃんと早めに寝たほうがいい。
  • AtCoderさん、ありがとう!マラソンマッチでこんな問題を受注できるとは、本当にすばらしい。

Topcoder Arenaを起動する方法とJavaブロックの回避

はじめに

Topcoderで競技プログラミングをする場合、以下の2つの方法があります。


ウェブ版はずっとベータ版で開発終了停止している模様なので、懐かしのアプリ版を立ち上げたいところ(パスワード平文疑惑がありますが…)。でも、昔参加していた人が戻ってきても、ホームページが大改造されていて、はまりやすいのでメモ。Topcoderの登録は無事できているものとします。

アプレットArenaをダウンロードする

直接リンク Competition Arena

ちなみに、本家ページは以下の場所から行けます。一番目につくCOMPETE→COMPETITIVE PROGRAMMINGと行ってしまうと、ウェブ版(ベータ)が立ち上がるので注意
f:id:shindannin:20171129101957p:plain

アプレットArenaをダウンロードする

そのままですと、「セキュリティ設定によってブロックされたアプリケーション」というエラーで、Javaにブロックされて起動できません。以下のように、例外サイトにhttp://www.topcoder.comを追加しましょう。

f:id:shindannin:20171129102230p:plain

f:id:shindannin:20171129102432p:plain

最小カットを使って「燃やす埋める」問題を解くスライドのフォロー

この記事は競技プログラマー向けです。

はじめに

以前、最小カットを使って「燃やす埋める」問題を解くというスライドを書きました。

www.slideshare.net

これに対して、tokoharuさんから、『燃やす埋める』よりも『Project Selection Problem』を使うべきという、提言がありました。
『燃やす埋める』と『ProjectSelectionProblem』 - とこはるのまとめ
続:『燃やす埋める』と『ProjectSelectionProblem』 - とこはるのまとめ

この記事は、それに対するフォローの記事です。

  • tokoharuさんの記事では、解法と問題名の双方について指摘されてると思いますが、この記事ではスライドの解法についての意見だけ書きます。(問題名については、twitterで別に考えを書きます。)
  • スライドに載っているのは、私の解法や解釈で、元の『燃やす埋める』の記事に載っていた解法とは違うので、ご注意ください。そちらに押しかけないように。
  • 「全部一緒でしょ」と思う人は、おそらく理解している人だと思うので、この記事を読む必要はないと思います。

解法について

解法の種類

主に以下の[A][B][C]のような解法があります。

[A] スライドの解法
  • カットする辺が選択に対応します。小問題を並列に、選択肢を直列に並べます。
  • 最小カットになる辺の容量の合計が総コストになります。

スライドP14
f:id:shindannin:20171115014923p:plain

[B] プログラミングコンテストチャレンジブックの解法
  • カット後の頂点が、s側に属するか、t側に属するかで、選択を決めるという考え方です。
  • 最小カットになる辺の容量の合計が総コストになるのは[A]と同じです。
[C] Project Selection Problemのよく知られた解法

f:id:shindannin:20171115003256p:plain

[A][B]の本質はほぼ一緒ですが、分かりやすさについては、若干[A]が上回ると判断し、また[A]で対象の問題が全て解けたので、スライドでは[A]で統一しました。(当時、[C]は名前は知っていたのですが、誤解してました…。)

解法[A]のメリットとデメリット

[A]には以下のようなメリット・デメリットがあると思います。

【メリット1】定式化された最小カット問題と、直接結びつく。

最小カット問題を定式化すると以下のようになります。(Max-flow min-cut theorem - Wikipedia から引用です)
f:id:shindannin:20171115015238p:plain
(u,v)をカットする・しないを選択肢に対応させると、

  • d_{uv}=1のカットする辺が、「選択する」
  • d_{uv}=0のカットしない辺が、「選択しない」
  • 辺容量c_{uv}は、選択した場合にかかるコスト
  • 目的関数は \sum c_{uv}d_{uv}、かかるコストの総和、これを最小化する選択肢の組み合わせを探すということです。
  • 制約条件は、カットの条件で、小問題ごとに選択肢を1つ選ばなければならないのに対応しています。

最小カット問題とグラフが、特に変形などもせず、直接結びついています。これは以下のメリットにも、つながります。

【メリット2】選択肢の入れ替えをして良いというのが、分かりやすい。

選択肢の入れ替えは、制約条件が追加するにあたって、重要テクニックになってきます。スライドのP34~の内容です。その際、[B]のような解釈をすると、そもそも小問題ごとに選択肢を自由に入れ替えていいのか?という点で、少し迷うと思います(実際は可能です)。
f:id:shindannin:20171115024636p:plain

[A]の解釈であれば、(制約条件の辺を追加する前であれば)選択肢の順番が、最小カットに影響を与えないのは明らかです(どちらのケースでも、コストの最小値は20+30=50です)。
f:id:shindannin:20171115025114p:plain

【メリット3】3択以上でも適応可能というのが、分かりやすい。

[B][C]の解釈ですと、s側とt側の2つなので、3択には適応できないのでは?と、少し迷うと思います(実際は可能です)。
[A]の解釈であれば、3択以上に拡張しても問題ないというは、明らかです。(実際には、3択の場合、制約条件の追加が限定されて難しいのですが、それは、おそらく[A][B][C]どれも一緒だと思われます。)
f:id:shindannin:20171115025915p:plain

【デメリット】負辺の処理で間違える可能性が残る

tokoharuさんの指摘にあった、解法[A][B]のデメリット、負辺で間違う可能性がある(解法[C]では負辺がでてこない)ので間違えないということでした。それは正しいのですが、ただ、このスライドを読んだ人で、このP21が理解できず引っかかる人はあまりいないような気がします、自分はデメリットは些細だと思っています。
f:id:shindannin:20171114235119p:plain

また、[C]でも制約条件で負辺にあたるものが出てきた場合、どちらにしてもこの部分は理解してないといけない気がします。

評価

自分の考えでは、

  • 慣れた人にとっては、これらのメリットもデメリットも些細。
  • 慣れてない人にとっては、[A]がわかりやすい。

という印象です。
また、[A]と[C]は、「メモ化再帰」と「動的計画法」の関係みたいに、問題により若干有利不利はでてきますが、だいたいどちらでも解けるというかんじだと思います。複数の解釈を知っていたほうが、理解が深まることがあります。
さらに、[A]は、最小カットの式に素直に対応していて、一部にしか適応できない変なテクニックというかんじでもありません。

もちろん、[C]の解法は、もっと広まっていいと思うので、自分のスライドで出てきた問題をすべて[C]で解いてみる記事や、[A]と[C]で同じ問題を解いて比較する記事があればいいなぁと思っています。

おわりに

・念のためですが、この解法で解けるのは、最小カットの一部の問題のみです。一般性がすごくある解法と誤解せぬように。他の最小カットの問題も分類した記事があるとうれしいです。
・スライドは、自分の実力よりもだいぶ背伸びした内容になってます(この問題より、ずっと簡単な問題でも、解けてません…)。でも、気にせず記事を書きましょう。
→ぜひ、アドベントカレンダーへ(2枠目が過疎…)
adventar.org

2017/11/26 追記(特にためになったご意見です)

解法[B]のメリット(解法[A]のデメリット)

yosupotさん


tmaeharaさん


これらの問題では差がない。

southerwolfieさん


TCO17 Marathon Round 1 (GraphDrawing) の反省

問題と1位の方(chokudaiさん)の解法

TCO2017R1

結果

  • 力学モデル(バネ)で、長さ比に応じて力を加える。その後、貪欲法(一番悪い辺の点を、最も高得点になる場所へ移動)で解を改善。
  • 45位/146位 652,515.28点。30位ぐらいの人ともかなりの点差が開いていて、敗北感ある…。

敗北までの流れ

ファーストインプレッション

  • 方針
    • 力学モデル
    • 焼きなまし
    • よさげな頂点同士をマージしながら構築
  • 問題の穴
    • 木の足の部分はどうでもよい。
    • 距離が近くになる点どうしは、まとめて動かしてもいいかも。
    • 三角形などサイクルの形で、辺が絶対につながらず満点が取れないケースもあるので、こういうケースでは理論上最高得点を求めて、最高得点にあわせて、目標長さの条件も緩めたほうがいいのでは。
    • MAX_RATIO / MIN_RATIOなのに注意。全部言われた長さにせよとは言ってない。全部スケールしても得点は変わらない?
    • 三角形って何個あるんでしょう。位置関係が確定する気がする。
    • 長さが整数値になることを使ったHackはなさそう。

ざっくり焼きなまし

  • 近傍
    • ランダム移動、だんだん移動量を少なく
  • 評価値
    • 最小値だと、差分を使いづらく、雑に書くとO(E)、良くてO(logE)ぐらいな気がしたので、とりあえず重み付きの和で対応

Submission 2 得点 248563.14
上位の得点が、70万点近くなので、恐らくハズレ方針だと思い、あきらめる。

力学モデル(バネ)

メモ
  • 微分せよ。
  • ズレ0のやつで、位置があうか比較する。
  • インラインアセンブラがききやすい
  • 論文(良い初期位置とか)
  • Logをつけてみては?
  • 引っ張る力を比ベース
  • たぶんランダムな力とかは筋がわるそう。
試したこと
  • 普通のバネで引っ張る
    • バネモデル、意外とバネ定数により、発散しやすい。
    • 枠外でも力を加えて、枠に入れたほうが高得点になる。
    • 今回は目標の長さとの比が得点にかかわるので、長さ比に比例した力を加える(普通のバネは差に比例した力を加えるので、)
    • バネの力により簡単に発散するので、バネ定数の調整と、pow()をつけた調整を試す。
      • powやlogを付けた調整は発散しやすかった。
    • 距離の短い辺が、強い力でずっと動き続けて足をひっぱる。
  • 序盤は遊びを入れて、自由に動けるようにする。目標得点を0からスタートし、目標票得点内に収まるのであれば力は加えない。そして徐々に目標得点を増やしていく(拘束も強まる)
    • →これは極値にハマる可能性を大幅に減らせる有力な方針だと思ったけど、そうでもなかった。結局同じような場所でハマる。
  • エネルギー最小化

差ベース
// energy = integrate k*(x-a) dx from x=a to b ====> k * (a-b)^2 / 2

比ベース
// energy = integrate k*(x/a-1) dx from x=a to b ====> k * (a-b)^2 / (2*a)
// energy = integrate k*(a/x-1) dx from x=b to a ====> k * (a * log(a/b) + (b-a) )

    • 本当だったら、高速化のためKamada and Kawai多変数のニュートン法で = 0系の連立方程式を解くのだけど、まずは遅くてもいいので、エネルギー最小になる点を全探索で試すことにした。バネより結果が悪いのであきらめる。
  • このタイミングでビジュアライザも作成。正しくは動いているっぽい。
  • ズレなしで満点を取れるテストケースを試す
    • それでも満点がとれない。
    • どうやら初期位置が悪いと簡単なケースでは、ダメなことが分かる。
    • 逆にチートして、初期位置を知っているものとしてやると、バネでも高得点が取れる。
  • 簡単なわりには低得点になるケースを探す
    • 変な三角形とか、田んぼの田とか、いろいろと手作業でいろいろと作るも見つからず。

Submission 3 得点 475556.16

恐らくバネ方針も良くないのだと思い、あきらめる。

強引な貪欲法

もう一番得点が低い辺の頂点の片方を、700*700の移動先を全部試して一番良いところに移動させる。というか、なぜこれを最初に試さない。

  • 高速化する。得点ハイトマップを作成して、関数形を見る限り、そんなに山の数が多いかんじではないので、焼きなましで探していいのでは?(ドーナツを重ねてくり)

f:id:shindannin:20170511103243p:plain

    • 250回ぐらいの焼きなましループで、最適解(=700*700)を90%ぐらいの正解率
  • 得点は伸びたが、上位の70万点には程遠い。
  • 貪欲→バネ→貪欲→バネを繰り返せば、極大値にハマらないのではないか?
    • ハマる

Submission 4 得点 606403.67

焼きなまし

貪欲でいいのなら、焼きなましもやっぱり行けるでしょうと思い、焼きなましの戻る

メモ

評価値

  • 最小値(問題のスコアと一緒)
  • 足し算
  • 重み付き足し算(ペナルティはV倍とかにしないとダメ)
  • 分散

近傍

  • 頂点どうしの位置交換
  • 悪い頂点のとなり
  • 辺対称
  • 大ランダム移動(たぶん大きい移動が入った時点で負け)・小近傍移動
  • 速度つき近傍(慣性)
  • 粗いグリッド⇒細かいグリッド
実際にやったこと

評価値

  • 最小値
  • 足し算
  • 重み付き足し算(に比が1から離れていれば離れるほど、さらに悪くなる)
  • 分散
    • O(1)で計算できるし、2番目に悪い点、3番目に悪い点も実質考慮できるので、よいかなと思ったけど、だめだった。

近傍

  • 粗いグリッドに分けて、ざっくりした位置を決めたのち、徐々に細かいグリッドにしていく。2*2→4*4→8*8→…
    • 32*32を最高にスコアが落ち始めるので、あきらめる。←これはもったいなかった。32以降は別方針にするとか、2段階の解法で高得点いけた

Submission 2と同レベルの得点しかとれないので、やめる。

Beam search系

迷走する。書くほどでもないか…

反省点

部分最適(極値にハマる)理由を考察するのを第一に考える。

シンプルで統一的な解法にこだわりがち。

  • シンプルで統一的な解法でないと高得点が取れないと、その後複雑な解法にした際も、最終的には点が伸ばせないと考える癖がある気がする。
  • それ自体はいいのだけど、どうもシンプルな解法をいろいろ試すものの、それぞれの解法への考察が雑になり、点が伸ばせる解法を、謝って枝刈りしてしまっている気がする。
  • 悪いところを考察したうえであれば、例外的な対処も入れて良い。部分的対応をどんどん入れていってよい。
    • 力学解法でも、焼きなましでも、高得点は取れてたっぽい。
    • 悪そうな解法でも、部分的にでも良いところを探すようにする。
    • ちゃんとした物理に従う必要はないですよ。
      • バネモデルで、たまにワープさせたって構わない
      • バネモデルで、全部のやつに同時に力を加えなくたって構わない。(一番悪いやつだけとか)

評価関数を状況に応じて変える

(分かってるつもりなのですが…)

  • 例えば、焼きなましのグリッド解法は、高得点を取ってる人はいるので、良い方針だったはずなのだけど、2*2のときも、700*700のときも、似たような評価関数を使っているのは、大変良くない。
  • そもそも、段階ごとの目的に意識がいってない気がする。粗いグリッドのときは、「正しいセルに振り分ける」のが目的、細かいグリッドのときは「高得点取れるようにする」なのに、評価関数が1つというのは良くない。それぞれの段階での目的をはっきりさせて、評価関数をつくろう。
  • これは焼きなましに限らない。Beam Searchの前半と後半で評価値を変えたりもするし、目的ベースで、柔軟にかえる

頭の悪さは、ビジュアライザとランダムテストで補おう

  • 極値にハマる、単純なケースを、自分でテストケースを作るものの、見つけられなかった。
    • ランダムで単純なテストケースを大量に作って、試せばいいだけ
    • せっかくビジュアライザもあるんだから、考察も簡単にできるのだし

スコアに大きな影響を与えるものを、必ずしもアルゴリズムの最初に確定する必要はない。

  • 今回は短い辺が、低得点の原因になるけど、その場所を先に確定させると高得点にはならない。
  • 短い辺は確かにボトルネックになるけど、アルゴリズムの後半でGreedyとかやれば必ず治せる。
  • 似たようなテクニックとして、「後で決めても辻褄が合っていればよい。(Peg Jumpingとか)」というのもある。

このブログは、マラソン開催中に非公開で書くべし

  • 絶対にマラソン中に書いたほうが効率がよい。
  • 他の人の解答をまだあまり検討していない⇒復習としては最悪!