3月

 

いい感じに生きたってさぁ これっぽちしか稼げないしなぁ(9922)

 

見てて楽しいやつ

5秒で約2e6回まわるループの中で、1000回に一回書き出し、(おそらく)60fpsで描画したものを画面収録。

 

 はじめに

おや、もしやあなたはコンテスト参加中の私ではないですか?

であればこちらを見ると良いかもしれませんね。

 

そうではないあなたは・・・ご自由にゆっくりしていってください。

 

考察(過程)

ヒューリスティック系の問題を考える時、まず最初は自分が手でやるならどんなふうにやるかを考えます。

一番初めに思い浮かんだことは、(皆さんはpower pointなどに画像を貼っている場面を思い浮かべてもらって、)辺をつかんでサイズを変えるよりは角を掴んでサイズを変えるだろうなぁということです。

今回の場合これが実装できそうでそれなりに有効そうだったのでこれを実装し、一応辺をつかんでサイズを変えるものも実装しました。

つまり、近傍として「角を掴んでサイズを変える・辺をつかんでサイズを変える」の二種類を用意しようと考えたわけです。

大局的なアプローチとして、まぁつまりは乱択か山登りか焼きなましかビームサーチしか私の選択肢にはないのですが、そのどれを使ったかというと、今回は焼きなまし法を用いました。

他の手法が取れる以上乱択・山登りはナンセンスであり、ビームサーチは直感により却下しました。

直感をもうちょっと文字数の多い直感に書き下すと「局所解がとても多いがそれらの解答はある程度近くにあるような解空間になるだろうなという直感」になります。あってるかは神セカです。

以上の考察で、雑にいうと大局的手法として焼きなまし法、近傍として「角を掴んでサイズを変える・辺をつかんでサイズを変える」を使って解を求めることになりました。

 

補足をすると、近傍に平行移動は加えませんでした。これには明確な理由があり、一つ目は後ほど述べる近傍に平行移動の操作が含まれそうであったこと、二つ目は実装が面倒だったこと、三つ目はスコアが変わらないのであまり良い近傍ではないだろうなと思ったことが理由です。

 

もう一つ大事なこととして、広告の重なりをどう処理するかということがあります。

広告の破壊も重なりも許さないとすぐに局所解に陥ってしまうと思われるので、ここの対処は必須であると感じます。

自分は、最初は広告の重なりを許す方向で解こうと思っていました。

重なりを許さないのはなんとなく自由度が低くなる気がしたのと、重なっている広告の集まりからうまく重ならないように広告を選ぶという問題を、なんとなくいい感じにグラフを作れば燃やす埋めるで解けないかなという思いがあり、解けなくても重なっている部分でペナルティを付ければ良いかと考えたからです。

しかし燃やす埋めるで解こうとしてもうまくいかず、足りない頭で1日くらい燃やす埋める問題を調べた結果、心の中のさすらいのレッドコーダーが最小カットではなく最大カットになってしまって解けないよと耳打ちしてくれました。あんまり信用なりませんが、さすらいの競技プログラマーが言うならそうなのだろうと言うことでそこは諦めました。

そこで、重なっている部分の大きさでペナルティをつけて適当に回していたのですが、ここで記憶が途切れていて、気付いたら途中で一度も重なりを許さない方向にシフトしていました。

本当に記憶がないのでなんで変えたのか分からず書いている自分もびっくりなのですが、多分直感とか言うやつだと思います。

よって、それ以降、最後まで途中で広告が重なることを許さずに遷移していくことになりました。

 

広告の重なりを許さない以上、広告を破壊しなければ局所解に陥ってしまうと言うのは感じていました。 

 そこで、広告のサイズを変えて他の広告と重なった際「重ならないように自分を縮める・重ならないように相手を縮める」の二種類を用意しました。

 

考察(結果)

ここまでを整理すると、大局的アプローチとして焼きなまし法を用い、近傍として「角を掴んでサイズを変える・辺をつかんでサイズを変える」を用い、その際に広告同士が重なったら「自分を縮める・相手を縮める」の選択肢を用意しました。

 

大雑把ですが、結局この方針は最後まで続きました。

角を掴んでサイズを変えることは辺をつかんでサイズを変えることを含むので、辺を掴む操作を消したり、重なりができて縮めた結果面積が小さくなってしまった場合、別方向に伸ばせるなら伸ばしてみたり、一度に変えられる長さに制限をかけてみたり、初期解をいい感じに作ってみたり、最後に確実に改善する操作を行ってみたりなど、微調整を加えて改善して行きました。

 

小ネタ

自分の実装だと、広告が重なっているかの判定をめちゃくちゃする必要がありました。エディタにCLionを使っていたので、CLionで使えるプロファイラで見てみると、約7割程度の処理がそこに当てられていました。(最適化をかけるともしかすると変わるかもしれませんが。)

ある広告とある広告が重なっているかの判定はいくつか手法があると思いますが、まず最初に明らかに重なっていないもの(広告1の右の辺より広告2の左の辺の方が右にある場合など)を最初に判定し、そこが通ればちゃんとした評価を行うようにしました。 

 以下のような感じですね。

return !(another.br.x <= tl.x || br.x <= another.tl.x || another.br.y <= tl.y || br.y <= another.tl.y) && ((tl.x <= another.tl.x && another.tl.x < br.x) || (another.tl.x <= tl.x && tl.x < another.br.x)) && ((tl.y <= another.tl.y && another.tl.y < br.y) || (another.tl.y <= tl.y && tl.y < another.br.y));

 

一番最初の()の中身はなくてもちゃんと動くのですが、このようにすることで1e6程度のループ回数が2e6程度となり2倍になったため、スコアの改善に繋がりました。

 

なんらかのデーが構造を使ってもう少し高速化ができるかなと思っていましたが、Nの数が小さかったのと、交差判定がかなり高速にできるため今回は見送ることになりました。

 

次に向けて

  • 今回は忙しかったのもあって最初3日程度は考察に絞っていたが、それがかなり良かったのだと思う。忙しくなくてもそうしよう。
  • 焼きなまし法のコツを熟読した。次も読もう。余裕があればまとめよう。

  • 順位がモチベーションになっているところはあるから提出したくなる気持ちはわかるが、1日一回くらいにしよう。AtCoder社さんごめんなさい。
  • ハイパーパラメータの調整は確かにスコアが上がるけど、一度をそれをしてしまうと改善したかどうかの確認にハイパーパラメータの調整まで含まれてしまうから、最後にやるようにしよう。余程ひどかったらやっても良いかもしれないけど。
  • 高速化は重要だけど重要じゃない(ラノベ感)ので、あんまり早くからやらないようにしよう
  • 焼きなましにビジュアライザは大事らしい。なんとかして用意しよう。(最初のはOpenSiv3Dをいじった. 猫は可愛いので残した)
  • 更新が起こらなさすぎると一番良かった時に戻すと言うのを解説生放送で聞いたけどそれが使えるかもしれない
  • 今回は最後だけ確実に改善する操作を入れたけど、評価時にそれを行っても良いかもしれない(計算回数とトレードオフだけど)
  • 今回は改善したかの評価に固定5ケースを用いたけど、結果にばらつきがあるから、もっと増やした方が良かったかもしれない。強い人は1000ケースとか試してたみたい。
  • 偏りのある乱数が使えるかもしれない
  • 今回がめちゃくちゃ良かっただけなので、次同じくらいの結果が出なくても落ち込まない。楽しんでください。
  • タスク管理はしっかりしよう
  • #pragma

 

 

 おわりに

2年弱頑張ったアルゴのhighestレートを一回で抜かす気分はいかがでしたか?

以上でこの記事を終わります。