5月

(コンテスト期間)が終わることも この胸は気のせいだって思っていた

 

まえがき

統計っぽい匂いがしたけれど統計の知識が何もないので気合と根性で殴った。

やったことはパスの長さの推定だけで、経路の構築は愚直にダイクストラで特に変なことはしていないです。

 

要点

パスの長さの推定でやったのは以下の二つです

  • クエリを一つ消化する毎に、今までに得た全てのジャッジ側が計算した距離と手元で計算する距離が近くなるようにパスの長さを変えることを行う。
  • クエリをいくつか消化する毎に、分割場所を[1, n)の区間で予測(n-1なら分割無し)し、同じHのパスはある程度同じ距離になるように調整する。

具体的なことはあまり書いていないですが、実際そんなに難しいことはしていないです。

ただ、それでもそれなりの得点を出せたのは、以下のようなことを行なったからではないかなと考えています。

  • ジャッジ側が計算した距離をプログラム内で使う際、使うときに[0.9, 1.1]の一様乱数を掛けてから使う
  • 分割場所を予測して同じHのパスをある程度同じ距離になるように調整する際、平均の距離をaveとして, [ave-D, ave+D]の区間に含まれるようにではなく、[ave-400, ave+40]程度の区間に含まれる距離になるようにする

一つ目は0.2G、二つ目は0.5Gのスコアアップにつながりました。

一つ目の方は過学習の抑制、二つ目の方はちょっと確信が持てませんが、Hの影響がDに比べて強いため、Dのことをあまり考えない方が良いのではないかなと思っています(よくわかりません)。

 

感想

以上の通りスカスカの考察と実装しかできませんでしたが、気合いで詰めてなんとか許せる程度のスコアは取れました。

正直最初の土日が終わってから手詰まりで、その後一週間は何度も枕を濡らし、ハンカチを噛み、涙が溢れ出して止まらない歌を聴きながら椅子を温め続けていました。

結構頑張って考えて全く何も思い浮かばなかったので他の人の回答がとても気になっていたのですが、完全に予想外というか、自分が知らない知識をいっぱい使っていて嬉しくなってしまいました。

特に一位の方の計算速度が足りないからAVX512で頑張ったりするなんてところは、本当に良いなと、自分もそういうことができたらなと、思っています。AVX512で頑張

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レートを一回で抜かす気分はいかがでしたか?

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

マラソン弱者としての戦い方と山型足し算のアプローチ

この記事にはマラソン全体へのアプローチと山型足し算へのアプローチの二つのパートが存在しています。

 

ラソン弱者としての戦い方

おやそこにいるのは初回提出で入賞スコアをとっているあなたではないですか。ここは競技会場ではありませんよ?

愚直or無作為なソルバーを書こう

何をするにもまず愚直or無作為なソルバーは書いた方が良いです。

ここでいう愚直or無作為なソルバーとは以下のようなものを言います。

入力

loop

    適当な解を作成

    解の評価

    解の更新

出力

このようなソルバーを作って提出し、ジャッジサーバーが計算したスコアとソルバーで計算した評価とを見比べることで、問題文の誤読や評価関数のバグなどに気付くことができます。

まともな得点であればそのスコアが基準点となります。

様々なアプローチをしていく中でこの得点よりも低い得点になってしまった場合、まずはバグを疑い、その次に実装者である自分を信じ、血涙を流してその手法は投げ捨てましょう。

もしその基準点を知らないままコンテスト時間の約半分を考察に費やして作成されたソルバーは一体どのような気持ちになるでしょうか?*1

 

強者は何をやっているのか?

一般的なマラソンマッチの問題は複数のアプローチが可能です。

この時どの道を選ぶかが運命の分かれ道です。

数時間程度のマラソンマッチでは特に顕著ですが、自分よりも圧倒的に考察/実装力が優れている人よりも良いスコアが出せることがあります。

そのスコアの違いは用いたアプローチの仕方の違いが生んでいることがほとんどです。

大局的な面はもちろん、どの部分を評価するかなどを少し変えただけで大幅にスコアが変化することはそれなりにあります。

 

考察/実装力に優れた彼らの方が良いアプローチを知っていると思っているかもしれません。

確かにそれは正しいです。

それでも、それがより良いスコアに結びつくとは限らないのです。

確かに彼らは様々なものを知っている。その上便利なライブラリをいくつも持っているし、問題の分割を容易くやってのけるし、部分的最適解を導出できるし、特殊な見方をして取得スコアを等差数列にしているし、フローに問題を帰着させている。

しかしながら、難しい操作をする事が最適解につながるとは限らないのです。

例え簡単な操作しかしていなくても、それが当たりのアプローチであれば、冴えないアプローチを己の能力で強引に躾けて出来たソルバーに勝つ事ができるのです。

 

あとは、お祈り。

そのため、普段から万物に感謝しお祈りをして良い解法を引けるようになる事がマラソン強者へ立ち向かう唯一の希望です。

弱者は自身の弱さを認めて神に祈るしかないのです。

己の肉体と技術に限界を感じ悩みに悩み抜いた結果彼がたどり着いた先が祈りと感謝の正拳突きであったことから、この事の重要性が分かると思います。

 

解法無料10連ガチャ

解法無料10連ガチャというのは、胸に手を当てて思い浮かんだ10個のアルゴリズムを無料で考察対象にできるお祈りのことです。

世のソーシャルゲームでは数回しか無料にならないことで有名な10連ガチャですが、このお祈りは何度でも無料でチャレンジすることができます。ためしてみてね。

 

Q. 弱者は何を磨けば良いのか?

A. 勘です。

 

方向性の決定はとても大事です。一度間違った方向に進んでしまうと短時間のマラソンマッチでは時間的にきついですし、期間の長いマラソン全体であっても、別の解法にたどり着きにくくなってしまいます。

もちろん、理想は一発で当たりの解法を考え出してそれに全力を出すことです。

しかしながら我々は弱者です。神に祈るしかない弱者なのです。

そんな我々にできる、祈る事以外の唯一のことは、当たりを嗅ぎ分ける嗅覚を養うことです。

様々なアプローチを考えていく中で、どれが当たりかを嗅ぎ分ける嗅覚/勘を鍛える。弱者が強者に立ち向かう武器は、もうこれしか残されていないのです。

 

ただし、考察だけしているのも自分は良くないと思っています。それは実装してみないとわからないこともそれなりにあるからです。 

 

天に祈っているだけでは物足りなくないですか?

そう思ったあなたはすでに強者への第一歩を踏み出しています。

己を信じて頑張ってください。

 

 顧客に本当に言いたかったこと

アプローチの仕方次第でスコアはかなり変化します。

一度実装する前に胸に手を当てて考えて、実装しながらキーボードに手を当てて考えて、結果が出なくて頭に手を当てて考えて、当たりを引けるように頑張りましょう。

当たりを考え出した上で限界まで詰めてくる本当の強者には勝てませんが、それなりには戦えるようになるはずです。

 

 

山型足し算のアプローチ

 2020/12/30現時点で全提出中最高得点をとる事ができました*2。現在は他の方に抜かれています(さすがです)

せっかくなのでやったことなどを簡単にまとめたいと思います。

 

はじめに

@tsukammoさんの「競プロ解法紹介~レベル別マラソンの戦い方~」をとても参考にしました。

ありがとうございました。

 

自明なソルバー

本当に自明なソルバーは0を出力して終わるものですが、それでは芸がないのでもう少しちゃんとしたものを作ります。

基本的にはtsukammoさんの記事通りのことをします。

実際のコードはこれ、疑似コードは以下のようなものです。

 

適当な初期解を生成

loop

    ある(x,y,h)の組みを選び、それぞれを±1の範囲で動かす

    評価

    スコアが上がるなら採用。それ以外は不採用

 

これでスコアは約9998~くらいまでいきます。

ただし、愚直に実装してしまうとあまりループが回らずにもう少し低いスコアになってしまうと思います。

気をつけて実装をすると230万回くらい回す事ができます。

 

高速化

以下の点に気をつける事で、高速化をする事ができます。

  • (x,y,h)の山の影響範囲は縦横共に約2hであること
  • 変化させたときの評価をする際、欲しいのはスコアの増減値だけなので、全体の評価をすることは必要ないこと
  • 解の更新が起こらない回数より起こる回数の方が少ないので、評価時についでに現在の状態を変化させ、解の更新が起こらなかったときに戻すという手法をとらず、評価は評価で行い更新が起こった際にだけ現在の状態を変化させこと
  • #pragma GCC target("avx2")
  • #pragma GCC optimize("O3")

最初の3つは最後2つに比べると誤差みたいなもんです(チョット嘘)。

とりあえず最後の2つは貼りましょう。c++最高!

 

焼きなまし

自分は焼きなまし初心者なので詳しくは検索してもらうか、もしくは同じく@tsukammoさんの「競技プログラミングにおいて焼きなまし法に堕ちずに落とすコツ」を読むと良いと思います。

 

スコアが上がるときにのみ解の更新を起こしていると局所解に陥る問題があります。

今回の問題ではスコアが上がるときのみでもそれなりに更新は起こるみたいですが、それでもたまには下げた方が良い結果が得られるようです。

このようなときには焼きなまし法を使うと良いっぽいです。計算回数で殴ってもそれなりのスコアが出ることから、ビームサーチとかよりは焼きなまし法の方が適していると思います。

焼きなましにおいて重要なのは評価関数と遷移関数、それらで用いるハイパーパラメータだと思います。

詳しくは実装したものを見て欲しいのですが、以下の特徴のある焼きなまし方を適用しました。

  • 評価関数はそれぞれのマスにおいての山の高さの差の二乗
  • 遷移関数は(ループ回数ではなく)時間が制限時間に近づくほどスコアが下がった時の遷移確率を低下させる

そんなに変わった焼きなまし方はしていないですね。

ハイパーパラメータの調整については天才的な手法を用いました!とても自信があります!!

 

ハイパーパラメータ調整

ハイパーパラメータ調整にはoptunaを使いました。

Preferred Networks様最高!

ありがとうございました。

 

 

初期解の生成

焼きなまし法の良さは初期解にあまり依存せずに良いスコアが出せることだと思っているのですが、限界を狙いたいので初期解も賢い方法で生成したいです。

今回やったのは「今最も誤差の大きいマス目を選び、その誤差をまだ作っていない山の数で割り、それに良い感じの値をかけたものをhとする」という方法です。

 

他にやったこと

最も良かった解をメモしてそれを出力する。

実際、最も良かった解と最終的に作られている解を比べると数十~数百程度の差がある事が多かったが、なんか微妙にスコアが下がった。

計算回数が落ちるためと理由をつけることもできるが、多分ランダム性から来る誤差だと思う。

 

以上です

ほとんどoptunaのおかげです(チョット嘘)。

初期解や変更する山の選択、焼き鈍しのやり方などを考えることでもっと良い感じになると思います。

また、サンプルケースを手元で60秒くらい回してみたら誤差が16kちょいで落ち着いたのでこれを埋め込むと数千くらいの改善にはなると思います。