Introduction to Heuristics Contest

• 問題
• 提出

3問もあるのかと思って大急ぎで雑な焼きなましを書いたりしていた……

• とりあえず1点更新だけの単純な焼きなましを書いた。(81730043)
• 温度が適当すぎたので調整する。(99859730)
• 遷移時のスコア再計算を素朴にやっていたのを速くする。(102493050)
• 定数倍高速化する。 (104637270)
• 初期解を貪欲で作る。(112775607)
• 初期解を2日先読みの貪欲で作る。 (115690469)
• 初期解を3日先読みの貪欲で作る。(116929121)

単純な先読みは3日が限界なので、次はビームサーチをするべきだろうなと思った。この辺でコンテストが終わった。

• （焼きなましの）ほかの遷移を考える
• 遷移の平均計算量は双方向リストっぽい持ち方でもう少し頑張れそう？

---

Bがチュートリアルとわかった時点で完全に無視していたのだけど、あとでCを見たら、一点更新の焼きなまし自体があまりよくないと書いてあった。そう言われるととそうだなという気持ちにはなるけれど、コンテスト中に見ても手が止まってしまっただけな気がする。

Chokudai Contest 002 A - 約数をたくさんつくろう！

• 問題

バチャをした。

最初のほうに考えたこと:

• 小さい範囲での全探索の結果は、偶数しかない。
• 例えば40があったら20を入れるのは意味なさそうだし、逆に20を入れるなら40を入れるべきという話にはなる。
  • 整除関係において極大な数に絞る？
  • 整除関係において極大だからといって、素数を入れる意味はなさそう。
  • いちばん大きな数の半分以下の数を調べなくてよい。（2倍を入れて損はないので。） とすると、$(5\cdot10^8, 10^9]$を探す感じか。
  • $(5\cdot10^8, 10^9]$の中の偶数から探すとすると、$2.5 \times 10^8$個を調べることになる。この程度ならひとつひとつ調べるような方針はありそう。
• ある程度$d(n)$が大きい整数の集合から愚直焼きなまし、はありえる？

そもそも約数の総数はどのくらいが相場だったかか覚えていない。$10^9$から下って$998000000$あたりまで調べてmaxを探す:

1000000000 100個
999999990 192個
999999840 576個
999999000 1024個
998917920 1080個
...

だいたい相場がわかったので、とりあえず約数が600より多い整数を100個見つけて並べると36000。すでにけっこう高い。

約数の数が700以上、で同じことをやる。(37000)

新たに整数を追加した時のスコアの上昇を調べる:

999999000 1024
999989760 576
999959040 552
999949860 720
999936000 468
999915840 454
999853470 488
999835200 522
999814200 540
999782784 469
999760320 463
999758760 576
999734400 601
999702000 420
999697920 388
999694080 506
999657120 466
999638640 582
999621000 372
999567360 323
999566568 369
999532800 320
999511920 454
999507600 395
999500040 440
999488160 360
999447120 388
999398400 392
999383616 315
999375300 464
999371520 278
999350100 354
999311040 440
999306000 409
999295920 404
999278280 528
999266400 312
999223680 340
999217296 356
999187200 354
999180000 444
999167400 304
999159840 434
999129600 335
999114480 423
999076680 296
999028800 486
999016200 420
998917920 378
998899200 337
998891712 298
998875800 252
998857440 332
998856144 274
998844000 374
998820900 312
998811000 273
998808720 324
998786880 309
998776800 344
998749440 220
998712000 356
998692200 292
998688600 272
998686080 343
998634000 228
998612160 312
998609040 350
998600400 295
998585280 460
998565120 279
998557560 408
998549370 238
998529840 331
998524800 393
998497500 252
998490240 260
998457600 270
998418960 329
998382528 228
998373600 276
998361000 333
998300160 273
998298000 339
998289600 268
998265840 270
998243400 282
998197200 361
998150400 210
998147520 241
998086320 321
998071200 301
998038080 285
998000640 224
997978800 238
997956960 296
997949160 216
997920000 218
997908912 239
997883040 222

追加される約数の数がだんだん減っていく。このカーブを適切に決めて、閾値を超えるものだけ取ればよい？

二次回帰して回帰曲線を超えるものだけ取ろうとしたりする。1時間半ほど経過したところで、そんなことをする必要はないと気づく。できるだけスコアが上がるような貪欲を${O}(N^2)$でやればいいだけだった。

$10^9$から下って約数を400以上持つ整数を6000個列挙して、約数がもっとも増えるものを貪欲に取っていくと41200くらい。そこから山登りして41500くらい。

---

リアルタイムでchokudaiさんのヒントがあったらしい。でも、気づいていたら逆にこれに囚われてしまって苦戦しそう。

CodeChef June Challenge 2020 - The Delicious Cake

• 問題
• AC

与えられた点集合の凸包を考えるとき、凸包上の点をいくつか省いて内側の多角形に使うことは不可能に見える。そこで、凸包を何回も取ってネストされたレイヤー（凸多角形）を作り、クエリで与えられた頂点がどのレイヤーに含まれるか調べるというのを基本方針として思いつく。

ただ、与えられた点で1つのレイヤーの内部に含まれるものはそれ自身がいずれかのレイヤーに属さなければならないという条件がちょっと厄介に見える。縮退が起きている場合の扱いも書かれていなくてよくわからない。

しかし、とりあえず面倒なことは一切起こらないものとして、単純なコードを提出してみたら通ってしまった。（EPSすらちゃんと考慮していない）

CodeChef June Challenge 2020 - Convenient Airports

• 問題
• AC

辺をつなぎかえて2つの連結成分を1つの連結成分にするとき、サイクルをつぶしながらつなげばノーコストでつなげるので、連結成分ごとにサイクルの数のようなものを数えたい気持ちになる。何を数えるのか突き詰めると、結局「木と比べた時の余剰辺の数」を数えればいいことがわかる。

$K$個の連結成分のサイズを$n_1, ..., n_K$、辺数を$m_1, ..., m_K$とするとき、$m_1-n_1+1, ..., m_K-n_K+1$がそれぞれの余剰辺の数にあたる。連結成分が余剰辺の数に関して降順にならんでいるとする。これらを先頭から連結させていくとき、連結後の余剰辺は$\sum m_i - \sum n_i + 1$個であり、これが0になるまではノーコストで連結できる。余剰辺が0になるのは残っている連結成分がすべて木になる時で、以降は木同士をコスト2でつないでいく必要がある。

ただし、孤立点は（余剰辺のある連結成分に対してもノーコストでつなげないので）特別に扱う必要がある:

• 連結成分$C$に余剰辺が1つあると、2つの孤立点をコスト2で$C$につなぐことができる。
• 連結成分$C$に余剰辺がない、あるいは孤立点が1つしかない場合は、1つの孤立点をコスト2で$C$につなぐ必要がある。

さて、スコアを求めるだけではなく実際にシミュレーションしなくてはならない。最初にUnion-Findで辺を走査して、連結成分ごとに「ベースとなる木に含まれる辺」と「余剰辺」に分けた上で、余剰辺の数の降順でソートし、それらを（辺を組み替えながら）併合していった。孤立点は最初から分離しておいて、最後に併合した。

CodeChef June Challenge 2020 - Operations on a Tuple

• 問題
• AC

場合分けがかなりありそうだが、簡単なケースから考えていく。

• 0手で到達できるのは3対が最初から一致している場合
• 3手あればかならず到達できる
• 1手で到達できるのは次の5つの場合
  1. 2対が一致する
  2. 1対が一致して、残り2対の差が等しい
  3. 1対が一致して、残り2対の比が等しく、整数である
  4. 3対の差が等しい
  5. 3対の比が等しく、整数である

あとは2手と3手を区別する問題になるので、2手で到達できる $\Leftrightarrow$上の1-5のうちの少なくとも1つの状態に1手で到達できる、にしたがって考えればよい。とりあえず$p$に対する「意味のありそうな加算・乗算」を全部並べてみる:

• $p$に整数を足して$a$と等しくする ($a-p$を足す)
• $p$に整数を掛けて$a$と等しくする ($a/p$を掛ける)
• $p$に整数を足して、$a-p$と$b-q$を等しくする ($a+q-b-p$を足す)
• $p$に整数を掛けて、$a-p$と$b-q$を等しくする ($(a+q-b)/p$を掛ける)
• $p$に整数を足して、$a/p$と$b/q$を等しくする ($(aq-bp)/b$を足す)
• $p$に整数を掛けて、$a/p$と$b/q$を等しくする ($aq/bp$を掛ける)
• $p$と$q$に同じ整数を掛けて、$a-p$と$b-q$を等しくする　($(a-b)/(p-q)$を掛ける)
• $p$と$q$に同じ整数を足して、$a/p$と$b/q$を等しくする ($(bp - aq)/ (a - b)$を足す)

これらの8種類の加算・乗算を$p$には必ず適用するとして$q, r$に同じ操作を適用する/しないの4通りを調べ、それぞれの結果に対してあとで1手で到達できるかを上の基準で判定する。さらに、全体を$p, q, r$の順列6通りに対して調べる。

あとは、ゼロ除算が絡む場合の処理について検討する。「1手で到達できる場合」の3と5については場合分けするとして、後半の8種類の操作について考える。非ゼロ/0のように割り算が不能な場合については、その操作自体が不可能ということなので無視してよい。また、0/0が現れる場合は操作をせずとも目標とする状態が達成されているということなので、ほかの判定で拾われているはず……ということで、やはり無視してよい。

CodeChef June Challenge 2020 - Guessing Game

• 問題
• AC

嘘がない場合と同様に、二分探索で範囲を狭めていけそう。まず、上図の[A]のように全体の1/2の位置にある数を尋ねてGと返ってきた状況を考える。（赤線とその隣にあるアルファベットが、質問した位置と答えを表す。LIEは「真の数を含んでいるとすると答えが嘘である」区間を表す。）その次に全体の1/4の位置にある数を尋ねると、二回連続で嘘をつけないという条件により、3段目で×をつけた区間は除外できる。同様に、1回目でLが返ってきた場合は3/4の位置にある数を尋ねると同等の結果が得られる。2回の質問で可能な空間のサイズが3/4になっているので、これを繰り返せば部分点が取れる。

満点の条件では120回の質問で突き止める必要があるが、上の方針では最終的な候補数が$10^9 \times (3/4)^{60} \simeq 32$程度にしかならない。そこで、上図の[B]のようにG→Lという答えが返ってきた場合に、追加で3/4の位置にある数を尋ねるとサイズが1/2になることに注目する。この比率が毎回達成できれば間に合う計算だが、G→Gの場合にうまい追加質問がない。つまり、この区間割ではできればG→L, L→Gと答えてほしくてG→G、L→Lは望ましくないということになるが、それは割り方が最適でないということを意味する。

そこで、区間の割り方を調整して、G→LでもG→Gでも同じレートで空間が縮むようにしたい。2回目の質問で1/4の代わりに位置$x \in [0 ,1]$で区切るとする。このとき、G→Lでは3回の質問で空間が$x+1/4$倍になり、G→Gでは2回の質問で$1-x$倍になる。1回あたりの改善率が同じになる条件は$(x+1/4)^2 = (1-x)^3$なので、$x \simeq 0.31586$と求まる。計算してみると、120回の質問で足りることがわかる。

---

想定解の改善率は2回あたり33%だった。2回の質問を1セットとして、G→Lの場合には次のセットで前の結果を利用できるらしい。

BBC 004 E - simple finalization

• 問題

（引き分けを除いて）ちょうど$k$回戦後に$M$人が残る場合の数を考える。最後に残るプレイヤーの選び方が$\binom{N}{M}$通りで、残りの$N-M$人に$k$回のうちのどこで負けるかを割り振る必要がある。これは写像十二相の「ボールも箱も区別できる・各箱に少なくとも1つのボールが入る」場合にあたり、第二種スターリング数で書くなら$k! \cdot S(N-M, k)$。あとは$k$回の各じゃんけんで勝ちになった手がそれぞれ$3$通りありえるので、全体としては$\binom{N}{M}\cdot k! \cdot S(N-M, k) \cdot 3^k$通りと計算できる。これを$k=1, 2, ..., N-M$について足せばよい。

計算量はスターリング数の求め方次第で、Min_25さんの記事によると${O}(N\log N)$でできるらしい。

第三回 アルゴリズム実技検定

• 問題
• 提出

リアルタイム受験した。A～Nを解いて辛うじてエキスパートだった。（しかもNはオーダー的に間違っていると知りつつ枝刈りで通した……）

K

次の4つの配列を持ってシミュレーションする:

• $\operatorname{bottom}[x] :=$ 机$x$の一番下にあるコンテナ
• $\operatorname{top}[x] :=$ 机$x$の一番上にあるコンテナ
• $\operatorname{prev}[y] :=$ コンテナ$y$の下にあるコンテナ
• $\operatorname{next}[y] :=$ コンテナ$y$の上にあるコンテナ

もっと楽にできるらしい。

L

優先度付きキューを二つ用意して、一つは先頭の商品全部が入っている状態を保ち、もう一つは二番目までの商品全部が入っている状態を保つ。（どちらかのキューに既に買われた商品が残っている、は問題ない。買われたものを記録しておいて、既に買われたものを取り出した場合は飛ばせばよい）

N

$x$をスワップするクエリが来ると、区間$[x, x+1]$の順序が乱れる。順序が乱れたところを記録しておいて、ソートクエリが来たらそこだけソートすればよさそうだが、計算量的に「正しい」やりかたを書けなかった。例えば$[10, 30], [40, 50], [100, 120]$が乱れているとして、$[20, 110]$のソートクエリが来たら、$[20, 30], [40, 50], [100, 110]$だけソートすればよい……のだが、それによって正しい順序に戻るのは$[40, 50]$だけで、$[10, 30], [100, 200]$は全体としては乱れたままなのが困りごとだった。（つまり、素朴にやると中途半端な区間を何度もソートさせるような入力でオーダーが改善していない。）　この例でいうと、$[10, 30]$のうち$[20, 30]$がソートされたら、もう一度$[20, 30]$や$[21, 30]$のソートクエリが来ても何もする必要がないとか、列を平衡二分木などで保持しておいて、$[18, 30]$のソートクエリが来た時に、$a_{19}, a_{18}$だけ挿入しなおすような処理ができればならしで間に合っているとか、部分的なアイデアは思いつくものの全体としてうまく動くようにまとめきれなかった。（しかし、終了直前に不完全なまま出したら通ってしまった。）

「中途半端なソート」でも転倒ベースで見ればうまく扱える、確かに。しかし、それでも実装はまあまあ大変に見える。