1.はじめに
初めて記事を書きながら参加します
だらだらと書くかと思いますので、適宜読み飛ばしてください
2.問題
https://atcoder.jp/contests/ahc025/tasks/ahc025_a
天秤を使って、できるだけ等しい重さでアイテムを分割する
入力：アイテム数N, 分割数D, クエリ回数Q
質問：左の天秤に乗せる数, 右の天秤に乗せる数, 乗せるアイテムのインデックス
出力：各アイテムをどの分割に属させるかを1列で
3.1日目(10/14土)
インタラクティブな問題で難しそう...
分割と言うから、分割位置を指定するかと最初思ったが、それぞれのアイテムを任意の集合に分けられるようで自由度は高そう
ランダム要素は無いが、分割数とクエリ回数によっては完璧に判断できるパターンもありそうなので、複数の解法を採用するのが最終的には良さそうですね
天秤問題は世の中にありそうなので検索で知見を集めつつ、貪欲解をまずは考えることから始めます
ビジュアライザを触ってから気付きましたが、クエリの回数は使い切らないとエラーが返されるようで、そこのケアをすることは忘れないようにします
アイテムの重さをW0~Wn-1とおいて、クエリで得た不等号式に合うように重さを解くことを考えると、ソルバーが使えるのかな？
その考えなら、効率のいい不等号式を考える問題になりそうです
アイテムを１つずつ比較して、重さの順番を把握して重さ上位をグループに分けて、残り細かいものを一番軽い所に詰めていくのはどうか？
→Qの最小値が2Nなので、一つずつソートしていると間に合わないパターンがありそう
マージソートをベースに、軽い方だけはある程度ソートが効くようなソートを考えてみた（重い方はあまり正しくないソート状態になる）
重い側を先に埋めていくので、重い側がちゃんとわかるようなソートにしました
↑初めに、重いものをグループ分けし軽いグループに割り振っていく
seed=2は、見た目結構いい感じになりましたが、最後にクエリ数を残しすぎて軽いもののソートが甘いためスコアが伸びていないように感じます
この時点(18:40)で、70位/200人なのであまり良い解法とは言えなさそうです
→Qが十分足りていて、ソートがやり切れる場合は強そう
上位を想像すると、最後のクエリまで試して手持ちの情報の精度を上げているような感じでしょうか？
複数の変数を同時に評価する方法としては、実験計画法も近い考えな気がしてきました（考え方は知っているが使ったことはない）
1週間あるので、この辺りも勉強しながら取り入れていきたいですね
※寝る前に追記
アイテムの重さが指数分布から生成されている記載が気になってグラフ化
1~(10^5*N/D)の範囲らしい
重いアイテムから振り分けていく考え自体は大事そう
4.2~3日目(~10/16月)
色々試して、44位(10/16 20時時点)に上がりました！
今のところの解法は、ケースによって2パターンあります
１.アイテムをソートして、降順に軽いグループへ合流させていく
２.適当にグループ分けした後、グループ内でソートして2分探索でバランスを取る
まず、ソートはマージソート O(nlogn) を採用しています
1と2の切り分けは、ソートの計算量を見積もってその後の操作が間に合うかどうかで分けました(下のコード
self.state = 0
mergeCnt = math.log(self.N, 2) * self.N
if (self.Q-mergeCnt) < (self.N-self.D)*(self.D/2):
self.state = 1
mergeCnt1 = math.log(self.D, 2) * self.D
mergeCnt2 = math.log(self.N/self.D, 2) * self.N/self.D
if (self.Q-mergeCnt1-mergeCnt2*self.D)/self.D*2 < self.D*2:
self.state = 2 # お急ぎモード
1の方は何となくイメージ付くかと思うので、2のグループ分け後にバランスを取る解法をgifにしました
バランスのとり方としては、
・一番重いグループから一番軽いグループへ、大小関係を逆転させない最大のアイテムを渡す（2分探索
・渡せなかったら、一番重いグループからランダムなグループへランダムなアイテムを渡す
としていました（焼きなましをイメージ
比較のクエリ数削減のため一度聞いた比較を保存しておいて、同じ比較をしたい時はオフラインで返答できるようにしています
さらに、「a>b」を知っている状態で「b>c」が判明した際に、「a>c」という回答をオフラインに保存するよう、再帰的な処理も作りました（さらっと書いたけど地味に大変でした
イメージ的には「b>c」判明の際に、bより重い各要素にcの方が軽いという情報を持たせて、cより軽い各要素にbの方が重いという情報を持たせるようにしています
# 不等号関係を伝播する
def sign_propagate(self, host, key, sign):
rev = {">": "<", "<": ">", "=": "="}
if sign in "><":
rsign = rev[sign]
for k in self.signGraph[host][rsign]:
if k not in self.signGraph[key][rsign]:
self.signGraph[k][sign].add(key)
self.signGraph[key][rsign].add(k)
output = "{} {} {} {}".format(len(k.split()), len(key.split()), k, key)
output2 = "{} {} {} {}".format(len(key.split()), len(k.split()), key, k)
self.signDict[output] = sign
self.signDict[output2] = rsign
self.sign_propagate(k, key, sign)
self.sign_propagate(key, k, rsign)
# 取得した不等号関係を更新
def sign_update(self, output, res):
rev = {">": "<", "<": ">", "=": "="}
x = list(map(int, output.split()))
nL, nR = x[0], x[1]
L, R = x[2: 2+nL], x[-nR:]
strL, strR = " ".join(map(str, L)), " ".join(map(str, R)),
output2 = "{} {} {} {}".format(nR, nL, strR, strL)
self.signDict[output] = res
self.signDict[output2] = rev[res]
# if nL<=2 or nR<=2:
if self.Q<1500 or nL<=2 or nR<=2:
# if True:
self.sign_propagate(strL, strR, res)
self.sign_propagate(strR, strL, rev[res])
self.signGraph[strL][res].add(strR)
self.signGraph[strR][rev[res]].add(strL)
次に試したいことの案
・パターン1の時、大量に余ったクエリの有効活用法
・パターン2の時、更新に向かいやすい近傍の見つけ方
・再帰比較メモを活用したマージソートの改良
・重量データから理想の解答を見て考察
5.4日目(10/17火)
・重量データから理想の解答を見て考察 について
seed=0のような、グループが2つの場合は重量データがわかっていれば厳密な解を求めることができます
以下の問題が類似していて、動的計画法で差の少ない数を求めた後、経路復元していけばグループ分けをすることができます
重さが分かれば、グループが多くともかなり正確な解が出せそうです
比較した情報から、各アイテムの重さを推定したい気持ちになり、ベイズ推定などを調べてみましたが、何も分かりませんでした；；
手動で良い解が出せたことに満足して次の検討に移ります
・パターン1の時、大量に余ったクエリの有効活用法
・パターン2の時、更新に向かいやすい近傍の見つけ方 について
パターン2では、重いグループから軽いグループへアイテムを渡せない時、ランダムに渡していましたが、ループ回数によって悪化したりするため別の方法を考えました
一方的に渡すのではなく、交換することにしました
重いグループのアイテム > 軽いグループのアイテム となるように選び、
尚且つ交換後もグループの大小関係が変わらないように交換しました
また、その遷移が出来なくなった後は、重いグループ側のアイテムを2つ選び同様の条件で交換判定をクエリ一杯まで行っています
この近傍は、クエリが大量に余るパターン1の場合特に有効に作用して、かなり得点が向上しました（瞬間29位！
6.5日目~(10/18~)
色々やった気がしますが、コーディングに夢中で記事に落とせていません
代わりに最終解法をちゃんとまとめます
7.最終解法
制約によって、３パターンの操作をしています
いずれの場合も、グループは降順ソートを維持しています
↓実際のコードの主要部分です（関数名が終わっていますが気にせず...）
while self.remCnt>0 and time()<self.eTime:
if self.state==2: # かなりクエリに余裕がない場合
if self.replace(0, 1, 1): continue
if self.replace(0, 2, 1): continue
if self.swap(0, 1): continue
if self.state==1:
if self.replace(0, 1, 1): continue
if self.replace(1, 1, 1): continue
if self.swap(0, 1): continue
if self.state==0: # クエリに余裕がある場合
if self.replace_0(0, 1): continue
if self.replace_0(1, 1): continue
for _ in range(self.D):
i, j = randrange(self.D), randrange(1, self.D)
ret=self.swap_bs(randrange(i+1), randrange(1, j+1))
if ret: continue
if self.swap_0(0, 1): continue
if self.swap_0(1, 1): continue replace関数
replace関数では、重いグループから軽いグループへランダムに選んだアイテムを渡そうとする処理をしています（AからBへ渡すと仮定します）
渡した後のBの重さが、Aより軽いorA以外で最も重いグループより軽い時、渡せると判断していました
swap関数
swap関数では、グループAからアイテムを2つ、グループBからアイテムを1or2つランダムに選び(a, bとします)交換しようとします
a>b かつ 交換後のBの重さが、Aより軽いorA以外で最も重いグループより軽い時、交換できると判断していました
replace_0関数
replace_0関数では、グループA内のアイテムをソートし、Bへ渡せる最大のアイテムを2分探索で探して渡そうとします
swap_0関数
swap_0関数では、グループB内のアイテムをソートし1or2つのアイテムを降順に探索してグループAのアイテム1つと交換しようとします
swap_bs関数
swap_bs関数は、グループBからランダムに1つグループAへ渡しておき、AからBへ渡せる最大のアイテムを2分探索で探して渡そうとします
8.提出コード
pypy3
9.終わりに
今回のコンテストは、よい方針が思いつかず「上位は推定とかすごいことをしてるんだろうなぁ」と半ば諦めながら取り組んでいました
蓋を開けてみると、すごい人はすごい（！）のは変わりませんが、同じような方針で更に上位に入っている方も多く見えました
自分の知識・方針でやり切ることが出来なかったと思うと非常に悔しいです
次のヒューリスティックでまた会いましょう！
