2020年7月2日木曜日

天下一プログラマーコンテスト2013 予選B E - 天下一最短路コンテスト

天下一プログラマーコンテスト2013 予選B E - 天下一最短路コンテスト

一次元の問題として解ける。直線上に等間隔でp100,p1,p98,p3,p96,p5,...,p4,p99,p2p_{100}, p_1, p_{98}, p_3, p_{96}, p_5, ..., p_4, p_{99}, p_2と並べればよい。


思いつくのに二時間かかった。第一感でID順を工夫して頑張る問題と思ったのだけど、あまり筋がよくなかったかもしれない。

2020年6月28日日曜日

Introduction to Heuristics Contest

Introduction to Heuristics Contest

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

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

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

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

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

2020年6月25日木曜日

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

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

バチャをした。

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

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

そもそも約数の総数はどのくらいが相場だったかか覚えていない。10910^9から下って998000000998000000あたりまで調べて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(N2){\mathcal O}(N^2)でやればいいだけだった。

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


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

2020年6月15日月曜日

CodeChef June Challenge 2020 - Guessing Game

CodeChef June Challenge 2020 - Guessing Game

guessg1

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

満点の条件では120回の質問で突き止める必要があるが、上の方針では最終的な候補数が109×(3/4)603210^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[0,1]x \in [0 ,1]で区切るとする。このとき、G→Lでは3回の質問で空間がx+1/4x+1/4倍になり、G→Gでは2回の質問で1x1-x倍になる。1回あたりの改善率が同じになる条件は(x+1/4)2=(1x)3(x+1/4)^2 = (1-x)^3なので、x0.31586x \simeq 0.31586と求まる。計算してみると、120回の質問で足りることがわかる。


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

CodeChef June Challenge 2020 - Operations on a Tuple

CodeChef June Challenge 2020 - Operations on a Tuple

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

  • 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手で到達できる、にしたがって考えればよい。とりあえずppに対する「意味のありそうな加算・乗算」を全部並べてみる:

  • ppに整数を足してaaと等しくする (apa-pを足す)
  • ppに整数を掛けてaaと等しくする (a/pa/pを掛ける)
  • ppに整数を足して、apa-pbqb-qを等しくする (a+qbpa+q-b-pを足す)
  • ppに整数を掛けて、apa-pbqb-qを等しくする ((a+qb)/p(a+q-b)/pを掛ける)
  • ppに整数を足して、a/pa/pb/qb/qを等しくする ((aqbp)/b(aq-bp)/bを足す)
  • ppに整数を掛けて、a/pa/pb/qb/qを等しくする (aq/bpaq/bpを掛ける)
  • ppqqに同じ整数を掛けて、apa-pbqb-qを等しくする ((ab)/(pq)(a-b)/(p-q)を掛ける)
  • ppqqに同じ整数を足して、a/pa/pb/qb/qを等しくする ((bpaq)/(ab)(bp - aq)/ (a - b)を足す)

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

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

CodeChef June Challenge 2020 - Convenient Airports

CodeChef June Challenge 2020 - Convenient Airports

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

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

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

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

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

CodeChef June Challenge 2020 - The Delicious Cake

CodeChef June Challenge 2020 - The Delicious Cake

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

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

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