HACK TO THE FUTURE 2019予選の反省

beta.atcoder.jp
7位/519でした。
今回は、意地でも定番解答にはならない問題をchokudaiさんが作ってくるかなと思ったら、わりと定番だった。見えることを1つ1つ改善していけば、点が増えていきやすいタイプ。
…と思いきや、後半に、いろいろ考察をちゃんとしてれば、加点できる要素があったので、上位から下位まで、実力が出やすい問題だった気もする。
tsukammoさん、chokudaiさん、ありがとうございました!

良かったこと

  • 天才解法を考える誘惑に負けず、簡単なところから行ったのが良かった
  • 決勝に出れないのは分かっていたけど、ちゃんと最後までがんばった。もう衰える一方の年齢なので、老化防止のために、がんばるべきときにがんばるのは重要。

反省すべきこと

  • 残り2時間で伸びなかったのだけど、条件が変わった後の再考察が足りなかった気がする。
    • 焼きなまし法のマスの状態遷移の調整(開始5時間経過あたり)で、"#TD"はいらないということに気づく。ここで、TD#がなくなったことで問題の条件が大きくかわったので、高速化できる要素等がないか改めて考えるべき。今回の場合、TD#がなくなったことにより、命令Sはマスが.LRどれでも直進1歩になったので、マス変更の影響がなくなる。
  • 2Dフィールドで、何かを動かすというのは、マラソンマッチでは定番。それなのに、経路を圧縮するのを思いつかないのは、ダメ。
  • せめて焼きなましの温度調整は、自動化したほうが良かった気がする。30ケースで軽いからと、自動化しなかった。
  • 一部ソースコードが大変に汚い(ムダなif文など)。コード汚いと、基本遅いし、また、いろいろ試すのをためらう原因になるので、ちゃんと書きましょう。

解法

マスを'..LR'の割合で遷移させる焼きなまし法。10万ループぐらい。5度→0度で線形変化。評価関数はスコアのまま。

やったこと

  • 変更マスを通ったロボットだけ、経路を更新する。
  • ロボット経路を保存して、ロボットの途中位置から計算
  • マスは1次元配列で持つ
  • 遷移状態の調整。TD#を使わない。
  • 焼きなまし、変化スコアが悪くなったら計算途中早期打ち切り。
    • わりと重要テクニックで。これで焼きなまし回数が2万→10万ぐらいまで増え、13万到達。

やったけどボツ

  • 中央付近にLR少なめ
  • 中央付近はあまり変えない
  • ロボット0の箇所の評価点を、最初は高めに
  • 初期盤面を、高スコアのときの割合の'L''R'に合わせて配置

やらずにボツ

  • ロボットが4個・5個重なるケースにわずかに加点。そもそも、初期状態でも、ほぼ4,5がなかった。でも、やって損はなかったのでは。
  • 'S'の数の偶奇でロボットを分ける(壁にぶつかると無意味)

気づかなかったこと

  • 移動コマンドの圧縮。
  • 変更マスを通り、回転するロボットだけの経路を更新する。(上記の説明)
  • 初期L盤面。


  • kimiyukiさんの解答によると、「中央にDで縦棒を引いて土管のようなものを作るとLが実質小さくなるので速い」。kimiyukiさん、面白い形状をつくった改善が得意な印象があります。

最重要

復習しないとムダ。復習しないとムダ。復習しないとムダ。

Marathon Match 100 のゴミメモ!

下書きで終わっていた記事が、残っていました。ゴミメモのままでしかないのですが、脱線に至るまでの経緯が、今見るとおもしろかったので、そのまま投稿。



50位以内だと、懐かしの旧TopCoder時代のTシャツがもらえるマッチでした。まだ現役なので、老兵どもに負けるわけにはいかないのじゃ!

結果:76位/280(遠くへ行きたいです)

最初のメモ(開始2日目)

当時のメモで、あまりよく覚えてないのですが…。

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

  • 近くからしかとらない・縦しかとらない・横しかとらないという条件であれば、いろいろできる
  • 斜めどりはかなり難しい。
  • ダイヤに穴をあけるようにしても、端からきれいにとっても、取れる箇所はほとんど増えない。
  • とったことにより、どれが取れるようになるかの分析が最重要。
  • 距離を限定して焼きなましするアイディアは面白いかもしれない。ただ後半の焼きなましは疑問。
  • ビジュアライザ、最終的にどれとどれをペアで取ったのかは、見たいかも。
  • 無害でとれる
  • ハマり形(はまり形を事前に知ってれば、避けたり、評価値に入れたりすることも可能。)
  • 焼きなまし解法。
  • 遅延セグ木

なんか、うまい取り方を考えようとしてたっぽいですね!(なんで遅延セグ木と書いてるんでしょう…)

反省点:ファーストインプレッションの前に簡単な解法を提出せよ!!

まず、この問題のポイントとして、ほとんどのケースで全部とれます。最初に簡単にそれに気づくはずなのに、その条件なしで考えはじめると、複雑な条件で考えないといけなくなります。無駄に時間がすぎる。

あ、でも、いつも簡単な解法をやらずに失敗しているので、今回は絶対に簡単な解法を書こうと思ったんですよ。でも、なぜか感覚が麻痺していて、

  • せめて貪欲法で書きたいなぁ
  • なんらかの評価関数がほしいなぁ
  • これは取れる個数ができるだけ多くなるように
  • めっちゃ重くならない?
  • というか、これはどこから取るのがいいんだろう?
  • 考察へ移行

という感じで、簡単な解法すら思いつかず、なんか脱線するわけですね、自分をコントロールできない!すでに自我がない!あなたの生きている意味は?

そういうときは、ランダム!O(1)で最強!!
というか、超簡単な解法リストでも作って、機械的にやったほうがいいような気もしてきました。思いつかないんだから。












ファーストインプレッションの前に、簡単な解法

ランダムでとるのが思いつかないんですね…簡単な解法



(ビームサーチ解は捨てる!)

焼きなまし法(最終日)

評価関数

  • 解決されていないやつは、後半にとるやつのほうが被害が少ない。
  • エリアが広いこと自体をマイナスとしてもいいかも。(すぐに他のやつが入りこむので)

評価差分

囲われフラグは、orderは無視したもの。

  • 全盤面評価はひどいので直す。

- Swap Pos -> それぞれのRectごとに、スコアをキャッシュしておく。Rect別再計算
   →Orderも考えると、
→今囲んでいるやつ、各点の囲われフラグを解除
→新しく囲んだら、各点に囲んでいるフラグを追加

- Order change -> OrderをかえたRectの再計算。囲われているRectに対して+1,-1
点ごとに、囲われているRectを持つ必要がある。→これは問題!!!

 - Order Changeはなしにして、定期的にOrder計算と最終結果計算を行う方法はあるかも。
  面積でソートすれば、それなりに



- そもそも距離2のは無条件にとって良い。order無意味。

- Orderほんと必要?一意に決まるのに。
 - 分割エリアごと orderなら毎回

  • Forward形式に変更

近傍

  • SwapOrderをChange Orderにする(orderはfloatかdouble)
  • 移動をprogression ratioに合わせて、徐々に小さく(Swap Pos・Change Order両方)
  • Posを移動面積距離が大きい順にソートして、近くしか移動
  • だめな部分を狙って変更する?

温度管理
→ats式がよさそう。

大きい近傍

  • 分割統治(やるなら、端からとったほうが良さげ)

わるあがき

  • はじを優先的にとるランダム
  • 後半単純に遅いかも。
  • 失敗したやつを優先的のとるランダム(これは簡単なので、先にやっていいかも)
  • 焼きなましの結果を使う
  • 高速化版ランダムGreedy解法
  • ランダム途中からスタート解法

初期解

  • 最寄りペアからスタート
  • 貪欲解からスタートのほうがいいのでは!?まぎれが少ないし、一定の得点は保証される。逆より全然良い。ただし、

電ファミニコゲーマーの、手動ディープラーニング記事について

電ファミニコゲーマーで「1987年に手動でディープラーニングをしていた驚異の麻雀ゲームがあった」
news.denfaminicogamer.jp
という記事が多くの人に読まれたのですが、実際の内容はディープラーニングではありません。にもかかわらず、ディープラーニングというバズワードを持ってくる釣りは良くないという話です。

これについて、はてなブックマークなどを見ると、何割かの方は、おかしいということには気づいたようですが、特に修正される様子はありません。また、このインタビューを企画した、三宅陽一郎氏は、日本でゲームAIの第一人者として知られてます。おそらく、日本のゲーム開発者は物申しにくいと思うので、自分が書きました。

何が間違っているか?

  • 手動ディープラーニングではなく、評価関数の手動調整である」という説明で十分だと思います。例えば、宮路氏自身が良い動作に対するなんらか評価方法を持っていたとして、それに対して「手動山登り法」「手動焼きなまし法」等ということなら特に問題ないですが…。
    • パラメータ調整で、教師つき学習の手法をとることもできます。ただ、それをディープラーニングというのであれば、まだ無理な解釈をしないといけない点が4つぐらいあり、普通に考えると最適化をしたとしか思えません。
    • また、そもそも論として、評価関数を使った場合、たいていの人がゲームの結果をみてパラメータを調整するという作業を行います。これを手動ディープラーニングと認めると、おそらく1980年代からその他のゲームも手動ディープラーニングしていた!という話になってしまいます。
  • 些末ですが、記事にでてくるメタAIは、三宅氏がよく使う分類に基づけば、メタAIではなく、キャラクターAIでしょう。キャラクターの中で閉じているので。

良い点・同情できる点

  • インタビューの内容自体は興味深く素晴らしいと思います*1。 また、企画を提案した三宅氏も、ゲームAIのエヴァンジェリストとして、大変評価できます。
  • インタビューということで、宮路氏に気分よく話してもらわなければならないという事情は理解できます。仮に「手動でディープラーニングしてたんですよ」「いいえ。これは評価関数を手動調整しているだけで、評価関数(=効用)は、1980 年代から現在に至るまで継続的に用いられています。*2」と答えたら、それは宮路氏が気分を悪くするでしょうし。でもまぁ、やんわり何か指摘することはできたとも思いますが。

なぜ問題なのか?

しかし、これらを加味したとしても、わざわざ間違っている部分をタイトルに持ってきて、釣るのはどうなのか。おそらくタイトルが普通であれば、「宮路氏はディープラーニングを勘違いしており、まぁこれは評価関数の手動調整だけれども、それでも内容は大変素晴らしい」で、特に問題なく終わったでしょう。

電ファミニコゲーマー

まず、電ファミニコゲーマーは、意図的に、誇大タイトルをつけているので、明らかに良くありません。たくさん記事が読まれないと商売にならないのは分かりますが…。
記事の最後をみると、電ファミニコゲーマーは、ゲームAI用語辞典を作り、ゲーム業界の新しい時代の開発者たちのために、貢献しようとしています。その心意気は大変良いことなのですが、それであれば、なおさら、科学の最も基本的なルール、「嘘は良くない」「誇大タイトルは良くない」というのは気にしてほしいです。

三宅氏

三宅氏は、ある意味被害者といえなくはないですが、この記事は三宅氏の提案でなされたインタビューなので、さすがにタイトルのチェックは、できたのではないでしょうか。(OKと判断した可能性もありますが。これに関連した話は、次の記事で述べます。)

近年、ゲーム技術が専門化するにつれ、他の業界と共有できる技術問題も増えてきました。産学連携が大事ということは、以下の三宅氏自身の記事でも述べられています。

そして、大学へのアプローチも重要です。若い人には、大学でゲームAIを学びたい人が多いんです。ただ、日本の大学教官がこの分野に手を出すとイロモノ扱いされてしまうし、教えられる人もいない。ゲーム産業の方から地道なアプローチと継続的な貢献が必要です。

通常の研究者は、産学連携でも研究としての価値を求めます。そこで、このタイトルをみたら「間違ってるうえに、誇大広告。ゲーム業界は、科学的ではなくレベルが低い。かかわらないことにしよう」と思うかもしれません。それこそ、イロモノ研究者しか集まってこないのではないでしょうか?ぜひ、修正依頼してほしいです。

おわりに

もう1つ記事を、書く予定です。

*1:自分もぎゅわんぶらぁ自己中心派MSX版の1と2を持っていましたし、だいぶ遊びました。記事にでてきたネタも分かります。待ち時間でテンパったかがバレバレでした。

*2:三宅氏自身の記事、「ディジタルゲームにおける人工知能技術の応用の現在」人工知能学会誌 30巻 1号 pp.45-64

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

はじめに

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

状況

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

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

英語力

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

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

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

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

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

2)電話面接を避ける小細工

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

3)ランゲージエクスチェンジ

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

4)プレゼン作戦

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

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

その他の注意点

目的

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

仕事力

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

おわりに

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

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

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

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

失敗談:飛行機に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さんの「競プロ用に作成したエディタのプラグインを紹介します」です。楽しみですね。それでは、また!