AHC012参加記録

こんにちは。競技プログラミングのコンテストに参加しているyunixです。 最近行われたAHC012に参加して33位でした。 コンテスト中にやったこと、考えたこと、やればよかったことなどを書いていきたいと思います。

この記事の内容

  • AHC012の概要
  • 解法
  • 学びを得たこと

AHC012の概要

  • AtCoder社は設立10周年を迎えたので記念パーティーを開きます*1
  • パーティーでは円形のケーキを高橋社長が手自ら切って参加者に振る舞います。
  • ケーキの上にはイチゴがたくさん乗っています。AtCoderを長く続けてくれた人に多くのイチゴをあげたいので、継続年数に応じてイチゴの数を決めることにしました。
    • AtCoderを10年続けた人には10個、9年には9個, ... , 1年には1個乗ったピースを与えたいです。
  • AtCoderをd年続けた人はad人参加しました(1<=d<=10)。
  • 高橋社長はケーキを真っ直ぐにしか切ることができず、また100回までしかケーキを切れません。できるだけ多くの人にケーキを行き渡らせるにはどのように切れば良いでしょうか?

図にすると以下のような感じです:

  • 円形のケーキを直線で切っていくと小さなピースに分けることができます。
  • この図では3回ケーキを切ったときにイチゴが9個乗ったピースが生まれています。
    • このピースは勤続年数9年の人に振る舞うことができます(9年の人にのみ振る舞うことができる)。

制約など

  • ケーキの半径: 104
  • 継続年数d年の人の数: 1 <= ad <=100
  • イチゴの個数: N は全員分ちょうどだけある
  • スコアは会場に来た何%の人にケーキが振る舞えたかで測定される
  • カット位置は始点と終点を-109~109の間の整数座標から選んでね

解法

基本的な方針

この問題を見たときに以下のことを考えました:

  • 斜めにカットはしたくない...!
    • 斜めにカットをするとピースごとのイチゴの数を数えるのが途端に難しくなりそう
    • できなくはないけど計算量かかりそう?
  • 縦横に並行な直線を引いて、直線の位置を微調整することでスコアを上げられないか?
    • 合計100本の直線が引けるので、50*50 = 2500くらいに分割できる。要求されるピースは最大でも1000なので、縦横に線を引くのは有望そう。
    • 並行な直線を多数引くことにすると近傍の定義を楽にできそう。スコアの差分計算も工夫したら高速にできそう。
    • ぱっと見た感じ状態をちょっとずつ変えてスコアを改善できそう。極端な局所解もなさそう。

縦横に並行な直線を引いてカットするとこんな感じになります。 円形のケーキなのにグリッド状に切っていてちょっと面白いです。

このように考えると方針はすぐに決まって、

  • 縦横に50本ずつ適当に線を引く
  • 線の位置をずらしたり線を消したり加えたりして、スコアが上がる方向に状態を変化させていく(焼きなまし)
  • スコアの差分計算の高速化や評価関数を工夫することで勝負する

という基本方針でいくことに決めました。結果としては悪くない方針だったと思います*2。

最終的には95.2M点まで上げることができました。

以下では焼きなましの近傍とスコアの差分計算の高速化の方針について詳しく書いていこうと思います。

焼きなましの近傍

焼きなまし法についてはtsukammoさんがとてもわかりやすい記事を書いています(https://qiita.com/tsukammo/items/b410f3202372fe87c919 )。

今回は2種類の近傍を用意できました:

  • 縦横の直線のうちからランダムに1本を選択して、それを隣接する直線との間でランダムにシフトさせる
  • ランダムに1本の直線を選択して消す or ランダムな場所に直線を挿入する

直線のシフトの近傍

これらの操作によって元の状態とは微妙に違う状態を作って、その成績が良ければaccept, 悪かったらreject、と言った感じで徐々に状態を改善していきます。今回評価関数はスコアそのものを使いました。

近傍操作で徐々にスコアを上げていく

また、これらの近傍のうち、後者の方は状態を比較的大きく変更してしまうことがわかります。 特に、焼きなましの後半で盤面が整ってきたときにいきなり直線を消されたり挿入されたりしてもスコアが改善する見込みはかなり低そうです(多分...)。 そこで、後者の操作はかなり失敗する確率が高いと予想されたので、直線の挿入・削除の近傍操作は14回に1回だけにしました。

スコア計算での工夫について

スコア計算の高速化について少し丁寧に書こうと思います。

そもそものスコア計算のやり方

二分探索ベースで行います。 縦線と横線のx, y座標をそれぞれベクトルにソートされた状態で保持し、各イチゴが所属するグリッドを探します。

計算量はイチゴの数をM、直線の数をKとしてO(M(log K)2)です。大体Mが2000~3000くらいなので、多分5*104くらいですね。 また、イチゴの位置をソートしておいて尺取法の要領でスコア計算をやると、logを1つ取ることができます。僕はこちらを採用しました。

なお、イチゴをカットしないように直線を引く位置を工夫するようにしましょう(https://twitter.com/iwashi31/status/1543543775678451713 )。

近傍操作におけるスコア計算

焼きなまし法では近傍に遷移するたびにスコアを計算しなければいけません。 全てのイチゴについて毎回計算するのはかなり無駄がありそうです。例えば直線のシフトであれば、移動させる直線の周辺のイチゴだけを考えれば大丈夫なようにしたいです。

制限時間が3秒だったら大体109回くらいの計算ができると思いますが*3、遷移のたびに全てのイチゴを計算し直していたらどんなに頑張っても104回くらいしか遷移を試せません。焼きなまし法では基本的に遷移の回数が多い方が有利なので、これはどうにかしたいです。

そこで、以下のような状態管理をしてスコア計算を高速化することを目論見ました*4。

  • 各種類のピース(0個のイチゴが載っているピース、 1個の...、10個のイチゴが載っているピース、11個以上のイチゴが載っているピース)の数をベクトルとして保持しておきます
    • スコア計算にはこの情報だけがあれば十分ですよね
  • 近傍操作によってこのベクトルを更新します
    • 直線をシフトさせるときにはそのシフトをさせる直線の周辺のイチゴだけを取得して、ピースの数のベクトルを更新します(図を参照)
    • シフトさせる直線の周辺のイチゴだけを選ぶためにあらかじめイチゴのxyをソートしたベクトルを持っておきます。
    • 計算に関与するイチゴの数が大幅に減るので差分計算を高速化することができます
  • この方法は移動させる直線が縦方向でも横方向でも使うことができます
    • xyとyxのベクトルを両方作っておく感じですね...
  • また、削除や挿入についても同様の方法で差分を更新することができます

直線のシフトでの状態の差分計算。図は説明のためにとても大袈裟に書いています。また、イチゴの数が7以上のピースについては省略しています。各種類のピースの初期値も適当に決めたもので特に意味はありません。

この工夫をすることで焼きなましの遷移を大体4*105回まで増やすことができました。 元々の計算に比べて数十倍くらいになっていて目論見を達成することができました。

学びを得たこと

問題を単純化して対処すると良いことがあった

ケーキを好き勝手な方向に切るととても問題が難しくなります。なんとなくこういう幾何の問題って昔のABCのFくらいの高度典型に出てきそうなイメージがあります。 とても4時間で手に追えそうになかったのでケーキを切る方向を限定して対処することにしました。

結果としてこれが良い判断で、スコア計算の単純化、近傍の単純化など色々な恩恵を被ることができました。 解の自由度を制限することになっても実装・探索の面でとても有利になったという感じですかね。

スコアと異なる評価関数を作る

今回は結構実装をバグらせてしまって、評価関数にいじる余裕がありませんでした。 最終的なスコアを焼きなましの評価関数にしていたので、10個のイチゴがのったピースのケーキをたくさん分割して多くの人に分け与えるようなことをやりがちで、10年続けた古参勢が犠牲になってしまいました。 極端なことを言うと1人の10年続けた古参を犠牲にすると、10人の1年の新規加入勢が満足することになります。

いなにわ💉💉💉 on Twitter: "新規ユーザーは苺1個しか貰えない格差社会 →実は1年ユーザ10人の要求を満たすために10年ユーザーを1人切り捨てる世界 で倫理観が高速回転してた" / Twitter

これでも最終的なスコアとしては悪くないのですが、もっと高得点を得るためには、評価関数で過剰な数のピースがあったらペナルティを課すようなことをしなければならなそうです。 この辺りに気を配るだけの時間的余裕がなかったのは実力だなあと思います。

バグらせてからリカバリが効いたのは良かった

スコア更新のための処理でバグが取れなくて結構時間を使ってしまいました。最終的にバグを完全に解決することは諦めて、バグが起きるような操作は行わないようにすることで対処しました。 かなり気持ち悪いのですが、コンテスト中の立ち回りとしては悪くなかったかなと思います。

方針が割とすぐ浮かんで良かった

方針が割とすぐに思い浮かびました。こんなふうに焼けそうだなあというのがすぐにわかってヒューリスティクスのアルゴリズムに慣れてきた感じがあってちょっと嬉しいです。

一方で、方針を決める前の考察は問題の性質と照らし合わせてしっかりやるべきで、実は運が良かっただけなのではないかという疑念が拭いきれません。 一応山登り系の方法でうまくいきそうなことはなんとなく感じていて、実際にうまくいくことをすぐにチェックできたのでそんなに悪くないとは思うのですが。

例えば、2017年の日本橋ハーフマラソン予選とかはなんとなく焼けそうな気がするのですが、これはもっと問題の性質を考えないと高得点が取れません。 焼けそうとかビームサーチできそうではなく、問題の性質についてまず考えなければいけないということは忘れないようにしないといけませんね。 atcoder.jp

オンラインのスコア計算システムがあまり役に立たなかった気がする...

前の記事に書いたAWSでのジャッジ環境があまり役に立たなかった気がします。 一応ハイパーパラメータのチューニングに役に立ったと思うのですが、短期コンだとスコアの計算に使う問題の数が少ないので、パラメータをある程度目星をつけたあとは何回か投げて高い点が出るのを祈ることをやればよさそうです。

このシステムは長期コンで可視化とか記録をつけたりするときに役に立つと信じています笑 AWS上にマラソンマッチ用のジャッジ環境を作った - yunix_kyopro’s blog

闘争が足りない...

来週の水曜日からTopCoder MM 138がありますね。 TopCoder MMは前回初参加だったのですが、大変面白かったです! AtCoderに比べて参加人数が少ない?みたいなので、ぜひAHC面白かったという人は参加して盛り上げていきましょう! Community - Events

*1:大変めでたいですね。おめでとうございます。chokudaiさんをはじめ、AtCoder社の方々の尽力で競技プログラミング界が盛り上がってきたのだと思います。AtCoderがなければ僕も競技プログラミングに出会うことはなかったでしょう。次の10年でもっと競技プログラミングが盛んになるといいですね。楽しみにしています。微力ながら応援しています。

*2:とはいえ、この方針が機能するかは結構ドキドキでした。とにかく小さな改善をしていくことでスコアを上げることができることを確認することを急ぎました。開始から50分くらいで山登り法で85Mを出せたのでこの方針で良さそうだと確信できて良かったです。

*3:ちょっと自信がないですがこのくらいですよね?

*4:ちなみに他の人たちはもっと高速化をしています。後で復習しよう。