AHC025 ふりかえり! - まだタイトルない

こんにちは、AtCoder Heuristic Contest 025 が 2023-10-14(土) 12:00 ~ 2023-10-22(日) 19:00 で開催されていたので参加してきました

暫定ですが結果はこんな感じ。AHC024についで2回目の参加となり、初めての長期コンテストでしたがそれなりにやれたのではないでしょうか・・・？

考えたことや考察を時系列に書いていきます。考察があってない可能性もありますがご了承ください。

課題の確認

詳細はcontest pageで確認ください。

与えられたN個のアイテムをD個のグループに分ける
- Dこのグループの重さが均等になるように分割する
それぞれのアイテムの重さはわからないが、天秤があるので、どっちが重いかの情報を得られる
- 天秤を使える回数はQ回まで
アイテム数Nは30から100で一様ランダムに生成される
分割数Dはrand(2,floor(N/4))で一様ランダムに生成。30なら2~7、00なら2~25
クエリ数Qは2N~32Nで一様ランダムに生成
生成されるアイテムの重さはλ=10^-5の指数分布
- ほぼ一様ランダムと言える（多分）
- 上限は決まってる

考察

※あくまでcontest２回目の私がポイントだと思った要素

アイテム1が10gの時、アイテム2が11gでも100gでも天秤の出す答えは変わらない
N個のアイテムの中でどれが一番重いか、どれが一番軽いかはそれぞれ(N-1)回比較すればわかる
- クエリ数の条件（2N以上）から一番重いものと一番軽いものを探すことができる
  - ただし、それを求められていないしクエリ数の無駄
評価指標がMSE(機械学習コンペでよく見るやつだ！！！)なので大きく平均を外すと悪化する

結構ドヤ顔で「ああ、大きく外さないようにする方針でアプローチするのね」となってました。

とりあえずランダムにグループ分けする

「うげーインタラクティブ形式じゃん、えぇっとABCのインタラクティブ用のコードを持ってきてと・・・」

ぐぬぬ・・・・・洗礼を受けました。

なんだかんだして通します。

N, D, Q = map(int, input().split())
ans = [i%D for i in range(N)] # random split
for i in range(Q):
    # Interactive
    print(1, 1, 1, 2, flush=True)
    ret = input()
print(*ans)

クエリーは絶対Q回送らなければいけないので、無駄に消費します。

LB2427m,Local2602m

seed21でこんな感じになります。

ローカルでテストできるようにする

エラーでたりしても30分提出できなくなるので、ローカルでテストできるようにしました。

参考サイト

seed100個分回せるようにしました

ランダムにグループ間の移動をする

code

ランダムに2グループ選ぶ
- ここで一回秤を使う
大きい方のグループからランダムに一つ小さいグループに移動させる
- これを繰り返す
大きいグループが入れ替わったら操作をやめる

これでLB2142m Local2100mくらいまで微改善しました

このシードに関しては改善されてないような・・・・？

移動した時大小関係が変わったら戻す

移動したときに２つのグループの大小関係が変わらない場合は明らかにスコアは改善されます

ただし、移動後に大小関係が変わった時に関してはスコアが悪化している可能性があります。それを考慮漏れしていたので、大小関係が入れ替わったらその移動を無効にするようにしました。

    # G1からG2に移動させる
    if len(dict_idx[g1]) == 1: continue
    while remainQ:
        item = random.choice(dict_idx[g1])
        dict_idx[g1].remove(item)
        dict_idx[g2].append(item)
        ret = compare(g1, g2)
        if ret == ">":
            ans[item] = g2
            if len(dict_idx[g1]) == 1:
                break
        elif ret == "=":
            ans[item] = g2
            break
        else:
            dict_idx[g1].append(item)
            dict_idx[g2].remove(item)
            break

この変更でscore503m, local400mにかなりの改善が得られました

だいぶ見た目も良くなりましたが、左から２列目とかに課題を感じますね

何回か実験に失敗

残りのquery回数が300回以上の時50%の確率で大小が切り替わった移動を戻さない
- 焼きなまし的に、たまに悪化も許容したらどう？という狙い
- 300は適当
- 改善なし
指定回数を使ってお土産の重さを降順に取得して、残りの数で４回目までの入れ替え動作を行う
- 改善なし
- code

初期配列をスイスドローでやる

↑で初期配列を多少の大小関係考慮したものにして失敗したんですけど、「もう少し少ない回数で大体の大小関係理解るとうまく言ったりするんじゃない？」ってことでスイスドローしてみることにしました。

シャドバやってた経験が生きましたね。

スイスドローをすると

N個に対して、高々ceil(math.log2(N))ラウンドで1番重いものが分かる≒大体の重さ順が分かる
100人だと7回戦、350試合、3.5Nなので、クエリ数の条件によって足りないこともあるが50％以上の確率で7回戦出来る

余談ですが

スイスドローの文脈で色々調べてたらサイクリック計画とスイスドローのいいとこどりをした手法の論文とか見つけたけどやり方を読み取れなかったです(link)
サイクリック計画自体もはN人の順序付けをN回で実現させるらしいんですけど、計算方法がわからんかったです

【閑話休題】

スイスドロー組み込んだcode

def init_swiss_groups(round:int):
    rank = [[0,i] for i in range(N)]# [-勝利数, 選手の番号]のリスト
    for _ in range(round):
        for i in range(N//2):
            p1 = rank[2*i][1]
            p2 = rank[2*i+1][1]
            ret = compare_single(p1, p2)
            if ret == "<":
                rank[2*i+1][0] -= 1            
            else:
                rank[2*i][0] -= 1
        # 奇数対策
        if N%2 == 1:
            rank[-1][0] -= 0.5
        rank.sort()

    omiyage = [i for _, i in rank]
    swiss_score = dict()
    for item in rank:
        swiss_score[item[1]] = item[0]
    ans = [-1]*N
    tmp = (list(range(D)) + list(range(D-1,-1,-1)))*50#最低でも100にする
    tmp = tmp[:N]

    for i, idx in enumerate(omiyage):
        # ans[idx] = i%D
        ans[idx] = tmp[i]
    return ans

LB 423m local388m で実際はあまり変化なかったけどなんとかく気持ちいいので採用

移動させる条件の改善

大きい方からランダムで一個取り除いく
- 大小が変わらなければ小さい方に移動させる（明らかに部分最適）

つまり、この場合これまで使ってた条件だと一番上にある茶色の移動は成功しないのですが、移動させたほうが得点は高くなるのでそれが実現できるような条件に変えました。必要な秤の使用回数に変化はありません

code

LB 200m local 176m まで改善できました

飛び出た２列分は明らかに過大なんですけど解決方法はわかりません・・・

スイスドローしたときの結果を使ってswapさせる

これまでは１個を何処かに移動させる方法で均等なグループを作ることを目指してましたが、ちゃんと交換できるなら強いはずです。
n:mで交換できればいいですがコストがかかりそうなので1:1での交換を指せる方法を考えていきます。
- 移動と同じようにランダムに2グループ選んで条件をしっかり決めて交換をしましたがあまり良くなかったです
  - （後から実装見たらバグがあったので多分これでも少し良くなる）
ランダムにグループを選ぶのでなく、すでに比較した結果を使って交換間できないか考えます。
これはスイスドローの結果をメモを活用できます

図において、（はっきり視認できませんが）a>bであり、a,bを除いたそれぞれのグループG1,G2の関係がG1>G2なら、交換するとスコアは改善されます。
直感ですが、移動させるほうが優先してするべきな気がしたので、移動をする→swapを探して最終調整みたいな順序にしました。

def swap(ans:list, comp_result:list, dont_move_idx:set)->list:
    idx = 0
    mod = len(comp_result)
    dict_idx = defaultdict(list)
    for i, v in enumerate(ans):
        dict_idx[v].append(i)

    while remainQ:
        a, b=comp_result[idx]#ここで a>b を満たす
        idx = (idx+1)%mod
        if (a in dont_move_idx) or (b in dont_move_idx):
            continue
        g1, g2 = ans[a], ans[b]
        if g1 == g2:continue
        if len(dict_idx[g1]) == 1 or len(dict_idx[g2]) == 1:
            continue
        dict_idx[g1].remove(a)
        dict_idx[g2].remove(b)
        if compare_group(g1, g2, dict_idx) == ">":
            # 交換確定
            dict_idx[g1].append(b)
            dict_idx[g2].append(a)
            ans[a] = g2
            ans[b] = g1
        else:
            # 戻す
            dict_idx[g1].append(a)
            dict_idx[g2].append(b)
    return ans