2024-02-06

LLM - Detect AI Generated Text 雑に振り返り

Kaggle Python

こんにちは。先日まで開催されてた"LLM - Detect AI Generated Text"に参加してました。

個人の取り組みとしては参加期間も短くディスカッションも追いきれず、公開ノートを弄って終わりでした。

久しぶりの機械学習（特にNLP）ということで今コンペはどんなモデルや手法が使われてるのか軽くメモを残しておきます。

※想像以上に雑なクオリティになってしまいました。ごめんなさい。英語の読解が正しくできてない部分もあるかもしれません。ご承知おきください。

solution毎のメモはコチラに公開してあります。

概要

LLMによって生成されたテキストを検出する
- 学生が書いたエッセイとさまざまな LLM によって生成されたエッセイを識別する
エッセイは中学生、高校生が書いたものと大規模言語モデルが書いたもの
- どのLLMで生成したかは非公開
評価指標
- ROC
LLMで生成された確立を提出

Data

約10,000件のエッセイ
trainデータは1378件与えられ、学生が書いたものが1375件、LLMが3件
残り約9,000件がpublicとprivateLB
- test data内の人とLLMの比率は非公開
エッセイは７種のプロンプトのうち一つに応じて書かれている
- 各プロンプトで、学生は 1 つ以上の原文を読み、応答を書くように指示されました
- これと同じ情報が、エッセイの生成時に LLM への入力として提供される場合と提供されない場合がある（ここが意味わからなかった）
train set は２つのプロンプトから構成されている

これが与えられた情報です。特徴としてはLLMのエッセイを識別したいのにLLMで生成したサンプルが3件しか与えられてないところだと思います。

参加者の調査によってもう少しデータについての情報が増えました。

7つのプロンプトが判明する(link)
testにはtrainとちがうpromptのデータしかない
- testの5種のうちpublicに含まれてないpromptがある(link)

図で表すとこのような感じになります。

public/privateでpromptが分かれていたため、publicにoverfitしていた人が大きくshakedownするということが起きました。

External data

上述の通りLLMが生成したデータが3件しかないため、参加者が作成した追加データセットを使用する人が多かったです。いろんな人が生成データを共有し、それをまとめる人がいたり、更新が止まったりとこの情報を追いかけることがすでに大変でした。

主要な公開データセットは @thedrcat 氏が公開していたデータセットv2,v3,v4あたりだと思います。上位の方々はこのデータを厳選したり、さらにエッセイを自作していたようです。

persuade_corpusということも特定されたので、人が書いたエッセイデータも参加者は追加で使用できました。

typo

本コンペで議論されていた大テーマの一つですが、今一つ実態を理解できてないので短く・・・（こんなんじゃコンペ参加してたと言えないですねごめんなさい

高速にtypoを直す（あくまで本データセットのtypo生成をハックした手法）
- 0.01boost
- https://www.kaggle.com/code/cpmpml/daigt-fix-typos
通常typoは隣接する文字などに間違うが、データをよく見ると完全にランダムに間違えられていた(link)
- 3割の確率でtypoを挿入/置換した(4th)
tfidfでmin_df = 2 とすると単一のエッセイ内に発生するngramが削除される。二つの異なるエッセイで同じtypoが発生する確率は低いと考える

銀上位あたりまで公開ノートを微修正で行けた

私がこのコンペを見てなかった期間に、testdata(こっちのほうが公式ののLLMデータが多く含まれてる)を使ってtokenizerをつくって、TF-IDFで特徴量を作ってオンラインで学習、推測をするノートが投稿され、大半の公開ノートがこれの派生になってる状態でした。

終了後、各参加者の投稿を見ると公開されてたハイスコアノートを弄って銀メダルという方もいました。 catboostのweightを大きくしただけであったり、ランダムフォレストを追加した人もいたのが印象的でした。

また、上位の人もアンサンブルの種にはしていました。公開ノートはpublicにoverfitしていましたが手法としては有効なものだったように思います。

上位はtransformerモデルを学習していた

印象としては上記TF-IDFを使ったモデルにtransformerモデルをアンサンブルさせていた人が上位にいたように思います。

mistral7BをQLoRA
Deberta-v3-largeをLoRAでなく普通に学習
deberta-v3-smallやdistilbertをsubmit時にtraining などがありました。

Pseudo-Label

testデータに対する予測値で、自信をもって予測されてるものに疑似ラベルを付けて学習しなおす手法も多くのチームが採用していました。
- 気持ちとしては、自作したエッセイとhostが用意してるLLM産エッセイが同じクオリティとは言い切れないため、hostが用意したエッセイの情報を使った方が有効というところだと思います。

データセットをよくする方に注力した参加者が多かった

自分でたくさんエッセイを生成したり、有志で共有されてたデータセットのデータを吟味してるチームも多かった（こ、これがデータセントリック！？）
今後コンペで勝つには良質なデータを生成するスキルも身につけなきゃいけないのかなーということをひしひしと感じた。
- 英語わからんから良質かどうか判断つかないのがハンディキャップすぎる

その他

llama 7b と tiny llama 1.1B を使用してghostbusterを実装(1st)
人間とAIのペアを作ってMargin Ranking Lossで学習(1st)
promptを予測するサブタスクを用意し、そのタスクのlogitを特徴量として使用
trainデータを少しずつ増やしていく（予測させて間違えたものをtrainに追加して学習など
rankingでアンサンブル
roberta-large-openai-detector(GPT-2の出力を検知するモデル)
token sizeが512のモデルの場合、頭512tokenとお尻512tokenの2つを予測

2023-12-28

2023年振り返りと2024年の目標

雑談

2023年の振り返りをしていきます。この一年は私にとって色々な目標を達成したり、あえて辞める選択をするなど非常に濃密な1年間でした。人間社会としても2022年の暮にChatGPTが登場して、ここまでたった1年ですごい変化が起きており濃密な1年だったと思います。

AtCoder Algorithm　入水

2022年度内の達成を目指してましたが、実力不足であったりDDoSがあったりとでGW後の入水になりました。PAST本上級が途中で終わってたりするので、これの読了とPAST受験、入青をまったり目指すかもしれないです。

AtCoderHeuristic 入水

9/24の回からAHCにも取り組み始めました。

特に明確な理由目的はなく、どれくらい行けるんだろう？という興味ではじめてみました。

12月に入水できました。まだ焼きなましたり出来ないので本番で使えるようになりたいです。こっちもまったり入青目指すかもしれないです。

ひとりディズニー

king of ひとり〇〇だと思うのでやってみたかったんですよね。二日間かけてどっちも行った。普通に楽しかった。トイマニ楽しかったけど1人は寂しいかな・・・・

個人的にはひとりボルダリングのほうが無理です。

ひとり海外旅行

海外旅行は好きですがこれまでは複数人で行ってて、同行者の助けがありながら無事帰ってこれてたと思っていたので、一人でできるかという意味で挑戦しました。初めてということで難易度が優しいと言われている台湾に行きました。

こうして無事に帰ってこれてますが、海外旅行中の貴重な体験その場で一緒にいる人に共有したいと思ったので、今後海外旅行は人としたいなーって思いました。

転職活動

8月くらいからカジュアル面談しはじめて、11月くらいから選考に入り始めました。実際には1月から視野に入れていてkagglerの皆さんとたくさんご飯に行って色々話を聞いてました。活動中私に時間を撮ってくれた皆さん本当にありがとうございました！！！！！！！！！

貯金

N歳までに金融資産額hoge円を目標にしてましたがダメでした。N歳の間にと目標を切り替えて、こっちは無事達成できました。

100人とご飯食べる

あまり積極的に人とご飯に行くタイプじゃないので意図的に100という設定をして色んな人とご飯を食べに行くようにしました。色んな人の考え方とか話を聞くことは自分の幅を広げることになるんじゃないかなと思ったからです。結果としては64と未達出終わりましたが、いい感じだったと思います。（語彙力力尽きた

その他出来なかったこと

富士登山
フルマラソン

マジで早くしないと老いていしまいどんどん難易度が高くなってしまう。

来年の目標

健康
Kaggleで金メダル

結婚願望はあるのでそろそろそこに向けて動くべきだと思いますがネットに向かって宣言するのも違う気がするのでこんな感じにゆるく記載して〆ようと思います！

2023-12-14

AHC027参加記・AHC入水しました!

AHC Python

こんにちは

AHC026に参加してきました！

415th / 3136で水パフォ、無事入水することができました

AHC027

課題の確認

問題はcontest page参照

考察

※正しくない部分はあると思います

各マスの汚れやすさdは1～1000
j-k-1は N=20の時-9から17の値を取る、中心が正のあたりにある正規分布
毎ターンsum(dij)-d現在地分スコアが増加する
dが大きいマスに移動距離を増やしてまで寄り道することは基本的にスコアの悪化を招く
- N=40の時は全体で最低でも1600汚れるので、１マスで相殺できない

つまり方針としては、Lをなるべく小さくなるようにしつつ、どうしても訪問済みのマスを通る必要があるときはなるべくdが大きいルートを通る。

でいいとおもってましたが、、、、上位のgifを見る限り違ったようです；；

最終提出

code

BFSで一番近い未訪問マスへの経路を探す処理をベースに実装しました。

隣接するマスを調べる上下右左の順序を２４通り試したりもしましたが、そもそもLを小さくという方針がよくなかったのか微改善しかできませんでした。

丁寧に経路長とスコアの相関を取ったら相関係数0.915だったので確信してたんですけどね・・・・

AHC入水

AHC024,025,026,027で入水することができました。

各振り返り記事は下記にございます。

感想

AHCをはじめる前までは「焼きなまし法とやらを使わないと戦えないのでは？」と思っていたので、焼きなまし法や山登り法がどういうものなのか座学してからAHC024からヒューリスティクスデビューをしました。

しかし、Contest本番になるとその手法の適用方法がわからず、その場その場においてどうしたほうがスコアがよくなるかというルールを作っていく貪欲なアプローチしかできずすべてのコンテストで貪欲なアプローチで水色までなってしまいました。

余談ですが、アルゴリズムはすでに水色まで取り組んでおり、この貪欲に進める部分で早いソート方法は何だろう？とか、BFSを使おうとかそういったアルゴリズムで学んできた知識は活かすことができたのではないかと思っています。

各コンテストの上位解法のヴィジュアライザを見ると何が起きてるのか全くわからないぐらい上には上があります。

今後の課題としては焼きなまし法や山登り、ビームサーチなどを駆使した最適化コードを実装できるようになるというところだと思います。

引き続き頑張ります！

2023-11-05

AHC026参加記

AHC Python

こんにちは

AHC026に参加してきました！

212th/1644で青パフォでした（入水しそこねた・・・・・

今回はちょっと手短に振り返ります

課題の確認

問題はcontest page参照

ソリティアと言ってる参加者が多くたしかにそんな感じだと思います。

考察

取り除くアイテムは200個、操作は5000回できる
- 毎回上に乗ってるものをどかしてから取り除いても400回なので結構余裕
- 1つ取り除くのに25回移動させられるので制約違反は気にしなくて良さそう
目的の数字の上にN個荷物が乗っていたらそれを撤去するにはNの体力消費をすればできる
- 何回に分けてもN消費することは変わらないというのは多分ポイント

とりあえず愚直に上に乗っかってる荷物を隣に移す

code

from collections import defaultdict
N, M = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(M)]

def get_over_n(n):
    # nの上に置かれた数字と箱の番号
    for m in range(M):
        for i in range(len(B[m])):
            if B[m][i] != n:continue
            if i == (len(B[m])-1):
                return 0, m
            else:
                return B[m][i+1], m

def move(n, cur_b, nxt_b):
    #nを箱bから箱bに移す
    idx = -1
    for i in range(len(B[cur_b])):
        if B[cur_b][i] == n:
            idx = i
    B[nxt_b] = B[nxt_b]+B[cur_b][idx:]
    B[cur_b] = B[cur_b][:idx]


for n in range(1,N+1):
    over_n, cur = get_over_n(n)
    # 上に乗ってる荷物をどける
    if over_n != 0:
        nxt = (cur+1)%M
        move(over_n, cur, nxt)
        print(over_n, nxt+1)
    print(n,0)
    B[cur].remove(n)

nxt = (cur+1)%Mで隣の箱の番号を計算してそのまま移します

これで1,221,582で710位くらいで茶パフォです

自分以外のボックスで一番使われるのが遅いボックスに移動させる

code

def get_next_box(n):
    # 次移動させるボックスを計算する
    s = set(range(M))
    s.remove(box_dict[n])
    while len(s)>1 and n < 200:
        n += 1
        idx = box_dict[n]
        if idx in s:
            s.remove(idx)
    l = list(s)
    return l[0]

こんな感じの関数で直近で使わなそうなボックスをとってきます。whileの条件を考えるのとsetの中に要素が複数残る可能性があることに注意が必要です

これをすると 1,356,657で426位、水パフォまで上がります

同じスコアの人めちゃくちゃいたけど同じ方針？？？？

移動させるときに直近で使いそうなものが上に来るように入れ替えてみる

code

# N個のダンボール
# M個の山
# 最大5000回作業できる
# - 1個の箱を取り出すために25回位操作してもいいと言える
from collections import defaultdict
import numpy as np
N, M = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(M)]
D = 2 # 何個移動を考える？

# nはboxmにある
box_dict = defaultdict(int)
for i in range(M):
    for v in B[i]:
        box_dict[v] = i

def get_over_n(n):
    # nの上に置かれた数字と箱の番号(0-index)
    for m in range(M):
        for i in range(len(B[m])):
            if B[m][i] != n:continue
            if i == (len(B[m])-1):
                return 0, m
            else:
                return B[m][i+1], m

def get_best_sep_idx(l):
    # 2回に分けて移動させる時、どこで区切るといいか求める
    sorted_l = sorted(l)
    best = 10**18
    best_idx = -1
    for i in range(len(l)):
        tmp = l[i:]+l[:i]
        cnt = 0
        for n in range(D):
            _ = np.argmin(tmp)
            cnt += len(tmp) - _ - 1
            tmp.remove(tmp[_])
        if best > cnt:
            best = cnt
            best_idx = i
    return best_idx

def move2(n, cur_b, nxt_b):
    #nを箱cur_bから箱nxt_bに移す
    idx = -1
    for i in range(len(B[cur_b])):
        if B[cur_b][i] == n:
            idx = i
    move_l = B[cur_b][idx:]
    # dictionary更新
    for v in move_l:
        box_dict[v] = nxt_b

    if len(move_l) >= D:
        best_idx = get_best_sep_idx(move_l)
        if best_idx == 0:
            B[nxt_b] = B[nxt_b]+move_l
            B[cur_b] = B[cur_b][:idx]
            print(move_l[0],nxt_b+1)
        else:
            print(move_l[best_idx],nxt_b+1)
            print(move_l[0],nxt_b+1)
            move_l = move_l[best_idx:] + move_l[:best_idx]
            B[nxt_b] = B[nxt_b]+move_l
            B[cur_b] = B[cur_b][:idx]
    else:
        B[nxt_b] = B[nxt_b]+move_l
        B[cur_b] = B[cur_b][:idx]
        print(move_l[0],nxt_b+1)

def get_next_box(n):
    # 次移動させるボックスを計算する
    s = set(range(M))
    s.remove(box_dict[n])
    while len(s)>1 and n < 200:
        n += 1
        idx = box_dict[n]
        if idx in s:
            s.remove(idx)
    l = list(s)
    return l[0]

for n in range(1,N+1):
    over_n, cur = get_over_n(n)
    # 上に乗ってる荷物をどける
    if over_n != 0:
        nxt = get_next_box(n)
        move2(over_n, cur, nxt)
    print(n,0)
    B[cur].remove(n)

3を取り出したいときに、83を動かすよりも、56を動かしてから83を動かしたほうがいいんじゃない？みたいなアイデアです。

一応関数を作って、移動させる集合の中で軽い方から何個か移動させるときの最適なんてものも考えましたがあまり劇的な改善は見られませんでした

これをすると1,381,277になって212位、青パフォです

感想

典型的ビームサーチ？って思いましたが使ったこと無いので貪欲なシミュレーション？しながらやりました
上に乗ってるものを複数箇所に散らばらせて移動させることを何らかのルールのもとで来たら伸びるんだろうなーと思いましたが何もわかりませんでした。
次水色に慣れるように頑張ります。開催ありがとうございました！！！

2023-10-22

AHC025 ふりかえり!

AHC Python

こんにちは、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

code全体

これをするとLB143m local 120ｍくらいまでいけました（思っていた以上に効いた

ビジュアルでも良くなってますね

最終

Qの使い道をどの処理にどれくらいという微調整して最終的にこれくらいになりました

提出Code

n:mの交換の実装とかまだできることはありそうですが今回はここまで！

お疲れ様でした！

2023-09-24

【AHC始めました】AHC024参加レポート

AHC Python

こんにちは、そろそろAHCの色も欲しいなーって思ったので参加してきました。

基本的に答えがある方が好きなのでAtCoderではこれまでアルゴリズムの方をやってました。

今回は参加レポートということで時系列で思ってたこと考えてたことをつらつらと

問題の理解

隣接関係を崩さないようになるべく少ないマス数で表現する

明らかに削っていいマスはわかるけどどうやってプログラムでやればいいかわわからない
ダウンロードしたツールもよくわからない
- 昨日Introduction to Heuristics Contestで少し予習したときはtester.pyがあったけどそれがない
  - →「あーこれ自分で評価関数的なやつを作らなきゃいけないのか、隣接情報とかよくわからないし作るの無理やな！」

行を間引いてみる

上から一行ずつ見て、下の行と全く同じ行は削除する。[code]

え？？？

ビジュアライザを見てみたらエラーが出てました。よく見たら出力行が1行足りなかったみたいです。

直して提出してみる

まだだめ

行単位で消すなら下の行が同じなら消していいは間違いで、上下の行が同じなら消していいが正しいです。

直して提出[code]

150点になりました！

ただこれはぬか喜びで、ルールに"作成した地図に含まれる色 0 のマスの総数を E としたとき、E+1 の得点が得られる。"とあるので、つまり0点です。

ならば、初見で感じた明らかに消して良いマスを消す実装をするしか無いです。

凸を消してみる

といっても、腰が重いので、凸部分を消せば、行単位の削除できるんじゃね？

この真中部分を青に揃えるコードを実装してみる→150点から変わらず

消していい場所を消す実装をする

code

外周に0の番兵を置く
自信含む周囲9マスの色の数が2色以下かつ0があれば消していい

(´・ω・`)

手元のサンプルでダメなやつを探してみる

左下が途切れてます。

さてどうしよう？

BFSを使う

code

組み込むのに40分くらいかかりました
事前にdefaultdictで色番号ごとの連結数を記録
消した後、周囲の消した色のマスの座標を取得し、連結数をBFSで数える
- bfsは計算量高々50**4（ほんと？）なので動くと判断
非連結になってたら戻す

良さそう

スコアが出た！

これに凸を消すロジックを入れたら微改善しました。

地図の形状ごと変えに行く

後なにできるかを考えると、もう中の方の色を圧縮するしか無いんですよね・・・・
でも何らかのプログラムでできる気がしない
とりあえず色をできるでけ右に伸ばせば、これまでの手法で削れるマスが増えるかも知れない

# 右に進撃するコード
for _ in range(2):
    for i in range(1,N+1):
        for j in (range(1, N)):
            color1, color2 = C[i][j], C[i][j+1]
            if color1 == color2:
                continue
            _, s1 = bfs(C,(i,j))
            _, s2 = bfs(C,(i,j+1))
            C[i][j+1] = color1
            d[color1] += 1
            d[color2] -= 1
            _, s1_2 = bfs(C,(i,j))
            i2, j2 = get_around_color(C,i,j+1,color2)
            n, s2_2= bfs(C,(i2,j2))
            if (s1 != s1_2) or (s2 != s2_2) or (n != d[color2]):
                C[i][j+1] = color2
                d[color1] -= 1
                d[color2] += 1