カナダで就職する際にしたこと

はじめに

10年前にカナダのバンクーバーで就職活動をして仕事（シニアプログラマー）を得たのですが、最近、海外就職を目指すアカウントからフォローされることが多いので、古い情報ですが、自分がどうやって就職したのか簡単にシェアします。

状況

• 知り合いはおらず、コネは無かった。
• 会社を辞めた直後。
• ワーホリの年齢制限（30歳）を越えていた。会社からワークビザを出してもらう必要がある。
• 海外就職する予定はなく、日常的に英語の勉強はしてなかった。TOEICは705点（R 375 L 330ぐらい）。英会話は絶望。
• 貯金はそれなりにあった。

そこで、３ヵ月間バンクーバーの語学学校に通いながら、現地で就職先を探すという方法で、仕事を得ました。*1

英語力

英語力については、全然足りてませんでした。ただ、語学学校で気づいたのですが、日本人のTOEIC400～850点ぐらいまでの人がクラス分けされたとき、クラス分けテスト＆面接をしたはずなのに、分布はTOEICの点によらず、ほぼランダムでした。日本人英語事情をよく知っている語学の先生ですら、その差を見分けられない。つまり、このレベルの英語力は、外国人からは「無」と見なされているのに違いない！ということで、開き直りました。３ヵ月ではたいした英語力にはならないという前提で、就職活動をしました。*2

頭を使って、自分にあった就職活動を

一番言いたいことです。普通にやったらダメなので、頭を使って、ダメもとでも行動していくしかないです。例えば、自分がした工夫で、思い出せるのを４つあげます。

１）現地のプログラマーのイベントに参加

現地でのゲーム業界の情報を知るため、また技術英語に慣れるために行きました。しかし、実際には、もっと良いことがありました。
常にレジュメを持って歩いていたので、イベントの休憩時間に、近くの席の人にレジュメを見せたら、みんな興味をもって、いいかんじに添削してくれました。（語学学校の先生にもお願いしたのですが、専門用語がいまいち伝わらなった）。これは大きかったです。

２）電話面接を避ける小細工

電話面接、とくにカメラ映像がない面接は、厳しいです。電話面接を避けるために、あえて日中は狙っている会社の近くの喫茶店で待機していて、電話がかかってきたら、「たまたま近くにいるので、ちょっとだけ会って直接話さない？」と持ち掛けました。この方法で、２つ電話面接を避けれました。

３）ランゲージエクスチェンジ

失敗例。英語力の劇的アップを狙いネイティブの友達を作りたかったのですが、語学学校にいると、現地の友達を作るのは想像以上に難しいです。語学学校のある地域で、日本人なんて珍しくもないですし。普通にやっていてはダメなので、あえて現地の大学（ブリティッシュコロンビア大学）に行き、張り紙をして、募集しました。しかし、おっさんというハンディキャップは大きく、最初の連絡が来た時にはすでに２か月半が経ってました。遅かった…。

４）プレゼン作戦

相手から面接で質問されると英語力のボロがでるので、できるだけ自分が会話の主導権を握ったほうが良いです。そこで、レジュメ・カバーレター以外に、パワーポイントの資料も送っておきました。そして、面接では、それを使って簡単なプレゼンをし、自分が過去に作った担当パートの技術解説をしました。図入りで説明しやすいので、英語力不足も準備で補えます。

これらの工夫自体を勧めているわけではありません。あくまで自分の例で、２）なんて、長期的な英語力の点を考えたら、むしろおススメしません。でも、とにかく頭をつかって、自分の状況に合わせて、どんどん行動していくのが良いと思います。

その他の注意点

目的

目的は、はっきりさせるべきです。「世界的な活躍をしたい」だけなら別に日本でもできますし、「海外で技術を学びたい」「海外で生活してみたい」というのはよく聞きますが、雇う側からしたら、いまいちな回答だと思います。

仕事力

英語のハンディキャップがある分、さすがに平均以上の仕事能力は必要だと思います。仕事能力をアピールして、普通に就職できる*3のなら、そのほうがいいと思います。

おわりに

他にも就職に影響を与えた幸運な要素（例：現地での日本人開発者への信用が高い）もいくつかありましたが、自分でしたことはこんなかんじです。みなさん、ぜひがんばってください！

*1:なお観光ビザで入国しましたが、そもそも就職目的での入国はダメな国も多いので注意。 そこは最初は空気を読んで、「語学学校がメイン！あとは業界調査（あわよくば就職活動…）」みたいなかんじのスタンスでいきました。

*2:就職活動中に、英語力ペラペラになって、就職するというのは無理と悟っただけで、仕事で英語力が不要と言っているわけではありません。むしろ、英語力は、立場が上になればなるほど重要になります。

*3:当時ですら、海外就職したいけどできない人向けの怪しい商売がいくつかあったので、食い物にされないように注意。

失敗談：飛行機に２度乗れなかった話

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

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

そうか、往復をとる必要はないんだ！さらなる損を重ねるところだった！

— nico_shindannin (@nico_shindannin) 2018年3月7日

４日後、

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

なんとかならないか聞いたところ、「1日遅らせれば、追加料金13万円で帰りのチケットを用意できる」と言われましたが、もうそれって2.5往復相当の絶望的金額…。あきらめました。結局、別な航空会社で、帰りの片道チケットをとることに（37500円）。往復チケットでいいのに、バラで片道チケットを２つとった分、さらなる損を重ねることに。
（平日だったため、行き片道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マスずれて落ちる。
• 魚が、下流に下ってきた魚の数は、場所ごとに分かる。

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

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か所に罠をしかけた。

まとめ

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

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

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

まえがき

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

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

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

敗因：誰でも思いつくようなケースをほとんど試さなかった。

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

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

問題

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

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

以下は解法の例（アニメーション）です。
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大きくする場合は、青い部分を足すだけです。紫の部分は再計算する必要はありません。

または、差分（微分）は前計算でき、メインの計算量に影響を与えないことも多いです。それぞれの変数に対しての差分を一度は検討してみましょう。これは貪欲法だけではなく、焼きなまし法などの近傍を高速に求めるときにも有効です。

６．部分的な最適化

もし部分的にでも最適解が総当たりよりも高速に出せるのであれば、それで計算量を減らすことができます。この問題、実は、円の位置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さんの「競プロ用に作成したエディタのプラグインを紹介します」です。楽しみですね。それでは、また！

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

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

問題

- Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017 | AtCoder

反省会生放送

TopCoderでプログラムしてみた 第2365回(北大日立マラソン第１回反省会生放送）

ファーストインプレッション(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点で、辺をじょじょに開放
  • 場所を後から、配置する解法はないか？よく、「置く場所を決める焼きなまし」→「何を置くか決める焼きなまし」のように、２段階に分けると良いこともある。

Submission 1 (2017/11/18) 52935点

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

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

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の総和。

ただ、ビジュアライザをつくっても、なぜ問題が起きてるのかにちゃんと着目した情報を表示して、本質を見抜けないと意味がないので、気を付ける。
この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は、高得点ベスト８の隣接頂点から選ぶ。かつ、焼きなまし法を2倍高速化

• この時点で、焼きなまし法のコツ Ver. 1.2 - じじいのプログラミングに載っている、

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

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

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

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

失敗したアイディア集

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

初期値

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

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

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

頂点Aを意図的に選ぶ。

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

• 低得点率（現在の得点 / 最大値）
• 得点差（最大値 - 現在の得点 ）

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

同じく最初にシャッフルしたあと順番に舐めてた。たしかTopCoderマラソンの↓この回(KnightsAttacks)の感想戦で「焼きなましで変更加える箇所、ランダムじゃなくて順番でいいんじゃね？」みたいな話が出てたのを思い出した

| TCO17 Lighting MM - Togetter - https://t.co/jAG3dXsMvd

— yowa (@yowa) 2017年11月30日

次回は要検討。

隣接頂点Bの選び方

Submission 6「元グラフでつながっている頂点Bは、高得点ベスト８の隣接頂点から選ぶ」の部分が、あまりに雑だったので、ここはスコアは伸びるかなと思ったけど、伸びなかった。辺得点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になるのはもったいない。１つに集中して時間をかけたほうがいい。ただ、並列計算とかできる環境であれば、有効なケースもあるのかも。

プロファイラで高速化。

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

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

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

その他

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

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

はじめに

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

• ウェブ版（ベータ）TopCoder Arena
• アプリ版 Competition Arena

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

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

直接リンク Competition Arena

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

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

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

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

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

はじめに

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

最小カットを使って「燃やす埋める問題」を解く from shindannin

www.slideshare.net

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

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

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

解法について

解法の種類

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

[A] スライドの解法

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

スライドP14

[B] プログラミングコンテストチャレンジブックの解法

• カット後の頂点が、s側に属するか、t側に属するかで、選択を決めるという考え方です。
• 最小カットになる辺の容量の合計が総コストになるのは[A]と同じです。

[C] Project Selection Problemのよく知られた解法

• tokoharuさんの記事の説明通りです。
• 講義スライド　http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/07NetworkFlowII.pdf のProject Selectionの引用です。

• 基本は、2N+2個の頂点を持ち、中央の部分で、必要条件の依存関係のグラフ（prerequisite graph）をつくるかんじです。
• 本：https://books.google.com.sg/books/about/Algorithm_Design.html?id=GORecgAACAAJ&redir_esc=y
• 元の論文：Jean-Claude Picard (1976) MAXIMAL CLOSURE OF A GRAPH AND APPLICATIONS TO COMBINATORIAL PROBLEMS

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

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

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

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

最小カット問題を定式化すると以下のようになります。（Max-flow min-cut theorem - Wikipedia から引用です）

辺をカットする・しないを選択肢に対応させると、

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

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

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

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

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

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

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

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

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

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

評価

自分の考えでは、

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

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

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

おわりに

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

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

解法[B]のメリット（解法[A]のデメリット）

yosupotさん

ARCに最小カットを出したら最小カットが結構話題になったっぽいんですが、最小カット問題を「辺を選ぶ」問題、つまり辺をいくつか選んでS, T間のパスを消す問題、と認識してしまうと、かなり(プロコンにおいては)損だと思います

— W521 (@yosupot) 2017年11月14日

基本的に「グラフを非連結にするように選ぶ」っていうのはかなり難しい条件だと思っていて，燃やす埋めるのように条件が複雑に絡み合っていくと，「頂点に値を割り振り+罰金」形式の方が考えやすいと思うんです(もちろん燃やす埋める，Project selectionのようにフレームワークを

— W521 (@yosupot) 2017年11月15日

tmaeharaさん

具体的な問題に対してどちらが考えやすいか、という話なら問題依存（∴両方できるべし）になりそうです。理論屋は (1) 頂点変数に取ると任意の部分集合が実行可能になる、(2) 頂点変数のほうが関数の性質が良い（枝から頂点を定められる条件が複雑）、という理由で頂点変数にとることが多いです。

— Takanori MAEHARA (@tmaehara) 2017年11月15日

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

southerwolfieさん

A or Bでなんかコストがついている最小カットは全部同じものと認識していて、そうでない最小カットの問題は時々面白い問題がある

— AGCは天才以外お断りパズルコンテスト (@southerwolfie) 2017年11月14日

最小カットはDiv1Hardを漁っていると時々妙なグラフを作る問題があるのが面白いです。s-[N頂点]-tとかs-[N頂点]-[N頂点]-tみたいなのしか作れないと後々苦労するので変なのに出会うといいと思います

— AGCは天才以外お断りパズルコンテスト (@southerwolfie) 2017年11月14日