cp note

日記やプログラミングに関する雑記

AHC025 参加記

 

# 参加結果

・AHC025 に参加した。目標は20位以内だったのでやや届かずだが、黄色になれたので嬉しい。

・問題設定がシンプルな割に最後まで何も分からないコンテストだった。

# 問題概要

・N 個の重さが分からないアイテムを、大小だけを判定する天秤を Q 回使うことで、D 個のグループに重さが均等になるように振り分ける。

・下動画は N=43, D=8, Q=395 の場合の私の解（seed=0027）。

 

# 解法の概要

・テストケースの難易度によって、二つの方針を切り替える解法を採用した。

 

## 簡単なテストケースの場合

・素朴に考えて、Q（天秤を使える回数）が大きいほど、アイテムを均等に振り分ける難易度は低くなる気がする。また、グループ数に対するアイテム数の比率（N/D）が大きい時も、細かい調整が効きやすいので難易度は低いはず。

・そのような場合は、以下のような解法を採用した。（上記 seed=0027 も参照）

  1. アイテムをランダムに二つの集合に分割する
  2. 片方の集合（Ａ）は、各グループに個数が均等になるように振り分ける

  3. もう片方の集合（Ｂ）は、マージソートを行い順番を確定させる
  4. 各グループを、重さの総和をキーとするヒープキューに入れる
  5. 重さの総和が小さいグループを一つ取り出し、Ｂのアイテムを重い方から一つ取り出してグループに入れ、ヒープキューに戻すという作業をＢがなくなるまで繰り返す
  6. 天秤をまだ使える場合、重さの差が小さくなるよう2点スワップ（後述）を繰り返す

 

## 難しいテストケースの場合

・難しいテストケースの場合は、以下のようなよりシンプルな解法を選択した。

 

  1. 全てのアイテムを、各グループに個数が均等になるように振り分ける
  2. 全てのグループをマージソートする
  3. ソートされたグループを 1, 2, … D-1, D とした時、(1, D), (2, D-1) のように、重いグループと軽いグループをペアを作る
  4. 各ペアについて、適当な回数スワップする
  5. Qが余っていたら 2 の手順に戻る

# 細かい工夫

## スワップについて

・グループAとグループBについて、それぞれから一部のアイテムを抜き出し、交換する操作を「AとBのスワップ」と呼ぶことにする。

・以下のように A = a + a’, B = b + b’ としたとき、a と b, a’ と b’ の符号が一致した場合にスワップを行った。比較回数は最大2回。

・画像のように b’ > a’ && b > a だった場合、グループA, Bの差は

(b’-a’) + (b-a) 

から、

(b’-a’) - (b-a)

になるため、確実に縮まる（(b’-a’) - (b-a) が負になる場合は (b-a) - (b’-a’) ）。

 

## 比較をしなくても結果が分かる場合の処理

・まず、同じ比較を複数回行うといったことがないよう、集合をそれぞれハッシュ化して、過去の比較記録を管理した。

 

・また、A ＜ B, B ＜ C の場合、A < C であるはず。このようなケースは、アイテム同士の重量関係をグラフとして捉えたうえで、重いアイテムから軽いアイテムへの有向辺を張っていくことで処理した。

 

・集合Aと集合Bを比較するとして、これらを過去に比較した集合同士のペアに分解でき、かつそれらの比較結果が一致している場合も、比較を行う必要はない。

## スワップする対象の選び方

・基本的には、各グループから一つずつ重さの近いアイテムを選びスワップを行った。

 

・Qが余る場合には、大小関係を逆転させた二つのスワップを組み合わせて実行した。アイテム間の差の差を取るイメージ。

## マージソートとクイックソート

 ・ソートアルゴリズムとして、初期はランダムケースの場合は高速とされるクイックソートを採用していた。しかし諸々試した結果、クイックソートによって比較回数自体が削減されることはほぼなく、特定ケースで比較回数が爆増するというデメリットのみが存在することが分かり、比較回数の安定しているマージソートに切り替えた。

・何度も読んだ記事

# 反省点

・難しいケースの場合のように、グループ間の大小関係を決める場合について、更新後に挿入ソートを行うことで比較回数を削減できることに気付けなかった。

【改善点】

・更新しながらソート状態を保つという時、ヒープのことのみを想定してしまい、挿入を考えられなかったのは、挿入処理に重いイメージがあったから。今回はＤが非常に小さいためその処理はほぼ無視できる。特定の変数が非常に小さいとき、普段あまり扱わないアルゴリズムが重要になってくることは今後もありそうなので気をつけたい。

 

・Largest Differencing method, Gibbs sampling, merge-insertion sort 等、既存の有用そうな知見が多々あった。

【改善点】

・アカデミックな領域における検索方法があまり分からない。仕事だったら人に聞くのだが、現時点で良い改善案があまり思い浮かんでいない。ギブスサンプリングはMCMC法を勉強していたら思いついたっぽい？

 

・総合的な反省として、パッと思いつく地味な改善を積み重ねることに終始してしまった。トップを取るような人は、理想のアルゴリズム、あるべき操作列等のイメージを固めて、具体的な方法は後から考えているのではないかという感触がある。今回で言えば、アイテムの重さをそれぞれ推定し、比較を通じて推定精度を上げていくやり方が強い気がしたが、イメージを膨らませることができなかった。

【改善点】

・過去のコンテストの復習等を通じて、地道に強いアルゴリズムに対するイメージを固めていくしかなさそう。

# 日記

 

# 23/10/14

・問題設定が簡単すぎてびっくりするが、意外と一手目が出てこない

 

## main_000

・最初、個数をできる限り均等にする形で、アイテムを全グループに割り振る

    ・5 個、4 個、4 個

・二つのグループ X, Y をランダムに選ぶ

・グループ同士の重さを比較（既に比較済みの場合はスルー）

・各グループから、1 ~ 3 個のアイテムをランダムに選ぶ

・それぞれのグループから選んだアイテムの重さを比較し、山登り

・絶対スコア 357483641

・相対スコアは 94,606,936,416 で、全体 8 位だ

    ・上々の滑り出し

 

## main_001

・交換時、小さいほうから選出するサブグループの個数として 0 を許容

 

## main_003

・1対1 あるいは 1対0 の交換のみに限定

・推移律をもとに、比較する必要のないアイテム同士を記録しておく

・相対スコア 91,046,979,865 で 17 位

    ・まだ強い人が全員は参加していないことを考えると、もうちょい頑張りたいかも

 

## アイデア

・一番大きいグループから一番小さいグループへの移籍を繰り返したい

・過去の比較情報を有効活用したい

・比較情報の新旧を記録しておこうね...

・グループごとにアイテム数を定期的に均等にしたくない？

    ・大きいブロックは動きにくいので

    ・個数が少ないやつの大きいやつを、個数が多いやつの小さいやつと交換

・大小関係カバレッジ

 

# 23/10/15

## main_004

・グループサイズが大きいものと小さいものを定期的にシャッフルする案を試す

    ・失敗、スコアは悪化

 

## main_005

・散歩中に考えた解法を試す

・重さが近いものだけを交換したい→大小関係でグラフを作ってトポソ、隣接頂点のみを交換

・伸びないが、可能性を感じる

    ・収束までが早い

・微修正、バグを直した

・87,389,728,097 で 61 位

    ・日曜日はやっぱり凄い...

    ・ビジュアライザを見た感じ、まだまだ改善点はある、全然戦える

    ・初投でトップクラスの点を出している人を見ると、方針レベルで筋がよい解法がありそう

・初期のやり方に固執して微修正でスコアを稼いでいる現状、良くないぞ！

    ・もっと幅広く解法を試していこう！

 

# 23/10/16

## main_005

・延々と散歩して、ほとんど解法を思いつかず

・一つ若干の改善案を試す

・100テストスコア 187924344

・86,819,587,634 で 78 位

・厳しい戦いだ...

 

・マージソートみたいにやりたい

・とにかく、ランダム要素を減らしていかないとスコアは安定しないぞ

・大小を確かめてから、片っ端から比較

 

# 23/10/17

・一旦クイックソートしてから考えるか

## main_007

・100テストスコア 728819198

・スコアが悪いのはまあいいとして、特に強味も見られなかった

 

## main_008

・各グループをヒープのように持ち、

    ・半分は数が均等になるようにグループに割り当て、

    ・もう半分はクイックソートをして、

    ・もっとも重さが小さいグループに、アイテムを重い順で追加していく

・86,168,269,230 で 82 位

 

## main_009

・最初にグループに割り当てる数を二分探索で求めた

    ・計算量オーダーでざっくり見積り、できるだけ沢山のアイテムをクイックソートに回せるように

・89,064,825,932 で 56 位

 

・でかい連中が同じグループに入った時に詰みがち

 

# 23/10/18

・大きいほうはソートしなくていいな

・大きいやつは各グループにちらばることが大切、小さいほうは大小関係を見ながらちゃんと分配していきたい

 

・このタスクは二段階に分けられる

    ・大まかにふりわける

    ・微調整

・微調整の方で頑張ってみないか？

    ・微調整の方でもヒープを持ち、最大のグループをばらしていく

 

## main_011

・失敗...

・微調整の方でヒープを使う案、コストのわりにメリットが薄い

 

・比較する配列同士のペアをハッシュ化して管理することにした

    ・c++ の標準のハッシュ関数はかなり厳しい

    ・ローリングハッシュっぽくやってみた

 

## main_12

・平方分割。ソートは早くなるが精度が低い。使い方しだいかな...。

 

# 23/10/19

## main_014

・最大値の最小化だ！朝起きた瞬間気付いた。なんでこんな簡単なことを...。

・スコアは上がらない...なんで？

 

## main_15

・難しい場合と簡単な場合でアルゴリズムを完全に変えてみる

    ・簡単な場合は従来通り、ヒープ構造を使って小さいグループに突っ込んでいく

    ・難しい場合は、最大グループと最小グループ間での交換を繰り返す

・90,798,491,385 で 47 位

    ・ちょっと盛り返してきたか！？

 

## main_16

・chokudai サーチをやろう

・駄目でした...

・微調整パートは必須だ

 

## main_18

・2対2 のトレードをやろう

    ・topological で並ぶペアを二つ選ぶ

    ・大小が逆だとする

    ・それらを組み合わせてみよう

・91,250,266,236 で 49 位

 

・しょうもないパラメタチューニングでやったつもりになっているのが一番よくない

    ・問題の本質を掴む努力をするべき

    ・何をすればいいんだ...？

    ・本を読むとか？

 

## main_19

・大、小のアイテムを残さず拾えるようにした、意味なし

    ・最終的に拾いたいアイテムの半分をランダムに選んでソート、その最大値、最小値よりも外にあるアイテムを拾っていく

 

# 23/10/20

・大・大、小・小で表現されるグループは、比較しなくても重さが分かる、でもどうやって管理する？

 

・基数ヒープというものがある。使える？

    ・https://nyaannyaan.github.io/library/data-structure/radix-heap.hpp

・使えない...

 

・大きさを確率的に扱えたらいいんだけどな～～

 

## main_20

・天才というか、今更すぎるアイデアを思いついた

    ・大きさが前後しても差が縮まる交換法

 

・difficult game の方、ソートに時間かかりすぎじゃない？

 

・29位になった

・手元とローカルテストで結果がかなり違うが、これはまあ、気にしないことにしよう

 

# 23/10/21

・最終日という気持ちでやっていきたい

 

・クイックソートの研究で無駄に時間を溶かした

 

・遺伝的アルゴリズム、今回のタスクとは相性が悪いかな？

    ・交叉の方法が分からなさすぎ

・二つのグループに分けて、大小をクロスして組み合わせたらどう？

    ・意味ないかも

    ・両者の分散は必然的に大きくなる

 

・部分ソートも試したいなぁ

    ・良くならない

    ・上位 n 個と下位 n 個を同時に求めるのは無理？

    ・上位 n 個内の序列が大事っぽい

 

## main_23

・かなり自明な改善が残っていた

    ・スワップ、大きいものを小さい方にくっつけるだけで良い

    ・93,725,345,166 で 32 位

 

・集合同士の比較の効率化、できるよね？

    ・一旦、不発、しかしこれから役に立つはず...

    ・difficult の方では役に立った

 

・ヒープで遷移するやつ、不発

    ・邪魔なので消す、main_24 に残骸

 

## main_25

・集合同士のあれこれを整備し、バグを直して提出、微増

    ・アイテムを重複して入れてしまうというかなりあれなバグがあった

    ・93,543,540,669

    ・34位

 

# 23/10/22

・最終日

    ・1000 テストケースでハイパラチューニング

    ・2000 テストケースでバグチェック

・三つスワップ

    ・意味なさそ～

・グループ同士の大小関係を推論する

    ・意味なかった、ソートって上手くやれてるよな

 

・延々とハイパーパラメータチューニングをやっていた

    ・この辺、仕組化したい

    ・oputuna を使おうね

    ・結局本当に微妙にしか改善しなかった、懸けていたのに...

 

## main_26

・最終提出は17:40

    ・新しい解法案もないし、さすがに滑った時に怖い

 

・ヒープに回す分とクイックソートに回す分の式、もう少し練る必要があった

    ・トレードオフ関係が発生してしまっていた

    ・log, 多項式を適当に入れたうえで、線形回帰をするべきじゃなかったですか？

 

・暫定 34 位でフィニッシュ。まあ今回のコンテストはシステムテストでかなり順位が入れ替わりそうなので、ただ待つ。

 

・何ケースかTLEしている。一週間の努力が消えると思うとちょっと泣きたくなってくる。