菜

ハル研プロコン2019 参加記

最終順位は未確定だけど多分4位になった

人生

問題

読んで

www.hallab.co.jp

  • 書いてないけどパッケージを見るとわかること

    • エサの数{40, 60, 80, 100}・カメの数{6～25}・高さの分布{低, 中, 高}の直積で全240ステージとなっている

    • エサ・カメの座標は一様ランダムで、重なって生成されることはない

    • エサの高さは、[1, カメの数]の離散一様乱数を{低: 3, 中: 2, 高: 1}回発生させた最小値で決定される

やったこと

応募履歴見ながら思い出して書いてるのでやったけど改善しなかったことは結構書き漏らしてると思う

序盤

巡回セールスマン問題は一度取り組んだことがあって（Kaggleサンタ）知見を得ていたので1位を取りたいと思った

過去に類似の問題が出題されてたりしないか探したけど見つからなかった

厳密解が得られないかと思って整数計画問題に落としてソルバに投げてみたけど全然だめだった

ランキングを見たらTopCoder MMの赤い人とかいつもランキングで見るような人たちが上位を占めていて怖気づいたので目標を5位（賞金圏）に下げた

7日

高さがカメの数の半分より大きいエサは同時に取れない（実質的にそれらのエサをすべて食べて回るカメが存在することになる）ので、高いエサをすべて食べる巡回セールスマン問題（TSP）が解けるか試した

これを参考に枝刈り探索を実装して投げると、高いエサのTSPの厳密解が全ステージ合計で46秒くらいで得られた

TSPで得られた経路の合間に低いエサを食べたい気持ちになったが、どう探索して良いのか実装がさっぱりわからずしんどくなった

8日

そういえばビームサーチとかいうのあったなとやっと思い出した
焼き鈍しは何回か書いたことがあったけどビームサーチは書いたことが無かったので完全に記憶の外だった

高いエサのTSPはとりあえず置いておいて、全てのエサから最大ターン数が最も小さく済むエサを選び続ける貪欲を書いて投げると72,000turns, 1.5000secになった

f:id:nagiss:20191017193019g:plain

幅1のビームサーチに書き換えて投げてみると74,388, 2.1484になった
貪欲と同じ結果になるはずなのにローカルでもなんか悪くなってたので不思議に思った

この時点でのビームサーチの状態の持ち方はこんな感じ

struct State {
        bitset<100> food_is_eaten;
        vector<Point> turtle_positions;
        vector<int> turtle_turns;
        vector<int> permutations;  // エサを食べた順
        double score;
}

ビーム幅を60にしても73,886だった
似た状態が多いからビームサーチの効果が薄いのかと思い、食べたエサの集合が同じ状態はunordered_mapで弾くことにして投げると71,384になった

一つ一つのステージを見ると幅1のときよりスコアが悪いステージがあるので流石におかしいと思って原因を探した

原因は、ビームサーチの後、エサの順番から行動を復元するときに、最も良いエサへのカメの割り当てが複数存在することだった

直すの大変だなーと思ったけどカメのインデックスをソートする前に毎回iotaでリセットしたら直ってくれた

修正したビーム幅60のものを投げると66,984, 39.2265になった

f:id:nagiss:20191017195459g:plain

https://twitter.com/lgeuwce/status/1181591630890975237?s=20

ビーム幅を90にしても66,742にしかならなかった

TSPで高いエサとその間にあるエサを回収する経路を決めて、それで回収しきれないものをビームサーチで探索するのを試したけどあまりいい結果にならなかったのでこの方針はすぐに打ち切った

f:id:nagiss:20191017203207g:plain

（画像はステージ229、バグが残っている）

9日

ビューアを見ると最後の方に孤立したエサが残ってしまっていたので、ビーム幅を40に減らしてエサが残り20個くらいになってからはビーム幅を300増やす感じにしたら64,787, 39.4375になった

評価関数の改善（これまでカメの最大ターン数のみだったが、新たにエサの(30, 15)からの上下左右それぞれへの最大距離の和を加える）（基準の座標は角も試したけど中央の方が良さそうだった）をしたりすると62,519, 48.6250になった
そういえば斜め方向を試してもいいかも？と思ってたけど結局最後まで試さなかった

f:id:nagiss:20191017201632g:plain (最終ステージ(エサ100・カメ25・分布高)はスコアが悪くなってる…)

10日

色々とコードが大変なことになったので全部書き直す

11日

評価関数に残ったエサを結ぶ最小全域木の大きさを入れたい気持ちになったので、マンハッタン距離での最小全域木をO(|V|log|V|)でやる方法を調べて実装したけど重すぎてだめだった

食べたエサの集合が同じものを弾くとビームの終端の方でビームが細くなるので最後の方だけunordered_mapを使わないようにする改善をしたりしたら61,687, 51.4296になった

12日

ビームサーチした後、山登り（エサ順列の2箇所をランダムに選んでrotateかswap）するようにして色々調整したら59,546, 59.6484になった
（次の日くらいにreverseも試したりして結局rotateだけが残った、ただ最終提出では確認してないのでもしかしたらreverseも入れたほうが良かったかもしれない）

f:id:nagiss:20191017204527g:plain

ちょっとずつしかスコアが上がらないのでしんどくなっている
このままちょっとずつ改善してても30位は安泰だと思ったけど目標は5位なので別の方法を並行して考えていた

高いエサのTSPを調整してみたら20秒くらいになった

高いエサのTSPを解いて閉路を得た後、閉路から順列を適当にひとつ取り出して、それらのエサに関してはその順に取る制約をつけてビームサーチをして山登りをしてみたが66,793, 54.9921だった

13日

山登りを焼き鈍しに変えるのを試したけどあまり良い結果にならなかった

ビームサーチの評価関数に残ったエサの高さの総和/2を加えると58,581, 59.6250に改善した
（この時点で評価関数が最終提出と同じになった）

高いエサのTSPをする解法を改善して、閉路から取り出す順列を任意に（具体的には、高いエサを1つ食べるまではエサを自由に選んで良く、高いエサを1つ食べた時点で他の高いエサを閉路の両隣以外すべてロックし、以降高いエサを食べるごとにその隣の高いエサのロックを解除する）したら58,572, 58.0703になった

f:id:nagiss:20191017211256g:plain

(最終ステージは改善が大きい)

3割はTSPを解く20秒の意味だった

このあたりでビームサーチの状態の持ち方は最終提出と大体同じになった

struct State {  // ビームサーチの状態
    bitset<100> food_is_eaten;
    bitset<100> food_is_available;  // 食べてないエサについて、食べていいかどうか
    Array<char, 25> turtle_positions;
    Array<int, 25> turtle_turns;
    Array<char, 100> permutations;  // エサを食べた順
    bool closed;  // 閉路の好きな頂点を使っていいかどうか
    int score;
}

14日

TSPを使わない方の解法のビームサーチをchokudaiサーチに変えると57,574, 58.0781になった

chokudaiサーチに変えると結果が良くなるのはある程度の確信を持っていて（この問題ではビームの終端で離れたエサが残っているか決まってくるので多様性が重要になり、chokudaiさんの記事の通りchokudaiサーチは多様性を確保できるため）（chokudaiサーチで多様性を確保できる理由は正直はっきり理解できていない）、数日前から考えていたが、せっかく一度最後まで探索するなら結果を次の探索にフィードバックできないか考えていたのでなかなか実装を始めていなかった（この可能性はshindanninさんが言及している）

一度最後まで探索し、最後に残ってしまったエサにペナルティをつけ、次の探索ではそのエサが残っていたら評価関数に加算するようにすれば、そのエサは早く食べられるようになるはず
ただ、ペナルティを具体的にどう決めるかとか、実装が大変そうとか考えて無限に足踏みしていた
結局、これをすると探索して見つけたすべての状態に対して評価関数を再計算しなければならないと思い断念し（各エサについてのペナルティが二値ならbitsetで所謂64倍高速化はできそうだとは思ったが）、普通のchokudaiサーチを実装した

ただ、コンテスト後のchokudaiさんのツイートを見るとこれをすれば実現できたかもしれないとなった

chokudaiサーチのイテレーション数を増やすとメモリが足りないっぽくRuntime Errorが出るようになったので、状態をchar型で持つようにしたらなんか実行時間が短くなった
回す回数が増やせたので57,186, 58.1953になった

TSPを高速化した
プロファイラを使ったらソートがボトルネックになっていたので、比較関数の式の計算結果を予め配列に確保しておいたりしたら9秒になった
（他の初期化処理も含めて9秒なので本当はもう少し早いかも）

このときに限らずVisualStudioのプロファイラを使ってこまめに色々と処理時間を改善していた

reserveしたのにvectorのpush_backが遅いと思ったら、vectorをコピーしたときにcapacityはコピーされてないのに気づいてないだけだったということがあったりした

ハル研プロコンを通してVisualStudioに慣れていった
デバッガとプロファイラが便利だった

TSPの制約をつける方のビームサーチもchokudaiサーチに書き換え、57,109, 55.4062になった
高速化とか調整とかをすると56,539, 59.3593になった

f:id:nagiss:20191017211304g:plain

15日（最終日）

最終日のBGM

www.nicovideo.jp

山登りを焼き鈍しにしてスコアが良くならなかったのを思い出すと、山を登りきれていないんじゃないかという考えになる（前日とかに山登りで一定回数スコアが上がらなかったらbreakするみたいなことをしたけどうまく行かないとかもあった）ので、スコアが改善しそうなところに絞ってrotateをしたい気持ちになる

エサ順列から区間を選んでrotateするとき、区間の両端のエサは距離的に近い方がそりゃ改善しやすいはず
距離の近いエサの対を選ぶのにはマンハッタン距離最小全域木の前処理を流用できた
流用しやすくなるのでコードをきれいに書くのはやっぱり大事っぽいと思った

これがうまくいって54,630, 55.1484で目標の5位に到達した

エサの挿入先に少しランダム性を出したり（選んだ挿入先が順列のn番目だったとして、ランダムにnに±1する）、山登りを焼き鈍しに変えたりするとさらにスコアが伸びて4位になった

この後は焼き鈍しパラメータの調整とかをして終了した

f:id:nagiss:20191017212854g:plain

思ったこととか

  • 目標を達成できて良かった

    • 目標があったおかげで目先の小さい改善に気をとられないで済んだと思う
    • 去年はReleaseビルドを知らないで手元の環境おっそ！！！！とか言ってたし成長したなあ…

  • 評価環境へのoverfitがどこまで許されるのかわからなくてしんどい

問題規定には

特定のステージに依存したチューニングを行うことを禁止します。例えば、X番目のステージの時は、あらかじめ用意した配列に基づいて行動を決定するというような処理は禁止とします。

とあるけど、プロコン速報 vol.2 には

パッケージに含まれているチェックプログラムのコードを見るとわかりますが、全てのステージは同じではなく、
・低いところが多いステージ
・高いところが多いステージ
・二つの中間のステージ
の3段階のステージがあります。ステージの特徴を踏まえてカメを動かすことで、効率よくエサが取れるようになるのではないでしょうか。

とあって、ステージを3つに分けてチューニングすることは許されてそうな雰囲気はある気がする

ステージを分けてチューニングしたら結果が良くなるのはそれはそうだけど、あからさまにやるのはまずそうなので、間接的にやる方法を考えたりした（結局あまり上手い方法が見つからずできなかった）

（去年は30位に入るためにステージを特徴から2つに分けて戦略を変えるとかをしたけどかなりアレだなあと思っている）

  • 上位が強すぎる

    • 自分が最初の提出をした時点からほぼ不動だったしいい解に行き着くのが早すぎる
    • めちゃくちゃ時間つぎ込んでも上位陣の中盤のスコアに勝てないのはきびしい…

  • 最終提出のイテレーション数を10倍にするのを試したらローカル（初期シード）で52,317になった

    • 最終ステージのスコアは366だったけど他の戦略で363が出たことがあったので最適解からはまだ遠そう

  • 今回ビームサーチを実装したのでマラソンマッチで使われる主要なアルゴリズムをだいたいコンプリートできた気がする

  • 焼き鈍しを本来の意味(？)で使えたことがないのでこのままで良いのか不安がある

    • 十分に高い温度からゆっくり焼き鈍すと最適解に行き着くのが本来の焼き鈍しだってどこかで聞いた気がするけど、現状山登りの亜種みたいにしか使えたことがない
    • 本来の焼き鈍しと違うことをしているなら遷移確率の式(p=exp(dE/T))も最適なのか気になる気がする
      • まあでも多分温度管理とかの方が重要そうなので気にしてもしょうがない部分な気もする
        • 何もわからない

  • C++って意外とそこ最適化してくれないのかーってことがあったりするなあと思った

  • k-means++とかでクラスタリングする解法の人が何人かいて、そういうのもあるのかと思った

    • そういえばハル研プロコン2017で結構使われてたみたいだった（参加してないけど去年だったかに下調べで見た気がする）

      • 中盤めっちゃ実行時間短いのにスコアが強くてなんなんだ…とずっと思ってた

  • 赤コーダーに褒められて嬉しい

  • chokudai幅

まとめ

人生…

Python競プロライブラリの整理をする

（19/11/22 追記）

一応最新のはgithubに上げてる

github.com

そのうち整理されるかもしれないので個別のページへのリンクを貼ったりするのはやめといたほうがいいかも

この記事は何

  • PyCharmに常に貼ってたライブラリが長くなりすぎて整理する必要が出てきた

  • 使わなくなったライブラリを消すのが何となくもったいないので公開してから消す

  • ついでに競プロライブラリを共有する

前置き

この記事のコードは公開を前提に書いたわけじゃないので、Python競プロライブラリを探しているならまず↓のサイトを見るといいと思う

ライブラリ整理

拡張ユークリッド互除法・中国剰余定理

拡張ユークリッド互除法

# 拡張ユークリッド互除法
# gcd(a,b) と ax + by = gcd(a,b) の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

AtCoderを初めて間もない頃に誰だったかの解答からコピペしたもの

m1 = 10
m2 = 6
gcd, x, y = egcd(m1, m2)

# 10で割ると1余り6で割ると3余る数を求める
b1 = 1
b2 = 3
s = (b2 - b1) // gcd  # これは必ず割り切れる
ans = b1 + m1 * s * x
print(ans)

使い方のメモがあったけどこれはいらない、消す

中国剰余定理

def chineseRem(b1, m1, b2, m2):
    # 中国剰余定理
    # x ≡ b1 (mod m1) ∧ x ≡ b2 (mod m2) <=> x ≡ r (mod m)
    # となる(r. m)を返す
    # 解無しのとき(0, -1)
    d, p, q = egcd(m1, m2)
    if (b2 - b1) % d != 0:
        return 0, -1
    m = m1 * (m2 // d)  # m = lcm(m1, m2)
    tmp = (b2-b1) // d * p % (m2 // d)
    r = (b1 + m1 * tmp) % m
    return r, m

なんか効率悪いことしてる気がするけどまあこのままでいいか

乗法のmod逆元・組み合わせ

乗法のmod逆元（mod-2乗）

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

こっちを普段使ってる

乗法のmod逆元（拡張ユークリッド互除法）

# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

egcdと一緒にパクったものを残してるけどpowでいいこと知ってから使われていない

組み合わせ

# nCr mod m
# modinvが必要
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

愚直に求めるものだけどたまに使う

組み合わせ（2）

# nCrをすべてのr(0<=r<=n)について求める
# nC0, nC1, nC2, ... , nCn を求める
# modinvが必要
def combination_list(n, mod=10**9+7):
    lst = [1]
    for i in range(1, n+1):
        lst.append(lst[-1] * (n+1-i) % mod * modinv(i, mod) % mod)
    return lst

これは使ってない、消す

階乗のmod逆元のリスト

# 階乗のmod逆元のリストを返す O(n)
def facinv_list(n, mod=10**9+7):
    L = [1]
    for i in range(1, n+1):
        L.append(L[i-1] * modinv(i, mod) % mod)
    return L

これO(n)って書いてるけどO(nlog(mod))では？効率悪いし使ってないので消す

重複組み合わせ

# nHr mod m
def H(n, r, mod=10**9+7):
    return combination(n+r-1, r, mod)

combination()の部分は必要に応じて下記のCombinationオブジェクトに書き換えて使う

組み合わせ（何回も使う方）

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

（久々に中身見たけどこれどうやって動いてるんだっけ）

下2つのメソッドはクラス内から呼び出されることを前提にしてるので_をつけたほうがいいのかもしれない、知らんけど

素数判定、素因数分解

エラトステネスの篩

# nまでの自然数が素数かどうかを表すリストを返す
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if isPrime[i]:
            for j in range(i * i, n + 1, i):
                isPrime[j] = False
    return isPrime

若干効率悪く書いてたのに気付いたので修正した

素因数分解

# 素因数分解
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

素因数分解はなんか高速にやる方法もあったと思うけどそれは持ってない

確率的素数判定もあった方がいい気がしたのでyaketakeさんのものを参考に導入することにした

確率的素数判定 - yaketake08's 実装メモ

順列

def full(L):  # 並び替えをすべて挙げる，全探索用
    # これitertools.permutationsでええやん！！！！！！！
    if len(L) == 1:
        return [L]
    else:
        L2 = []
        for i in range(len(L)):
            L2.extend([[L[i]] + Lc for Lc in full(L[:i] + L[i+1:])])
        return L2

itertools.permutationsを知るまで使っていたもの
思い出的に残してた（消す）

転倒数

# 転倒数
def mergecount(A):
    cnt = 0
    n = len(A)
    if n>1:
        A1 = A[:n>>1]
        A2 = A[n>>1:]
        cnt += mergecount(A1)
        cnt += mergecount(A2)
        i1=0
        i2=0
        for i in range(n):
            if i2 == len(A2):
                A[i] = A1[i1]
                i1 += 1
            elif i1 == len(A1):
                A[i] = A2[i2]
                i2 += 1
            elif A1[i1] <= A2[i2]:
                A[i] = A1[i1]
                i1 += 1
            else:
                A[i] = A2[i2]
                i2 += 1
                cnt += n//2 - i1
    return cnt

Spaghetti Source - バブルソートの交換回数 をPythonで書き換えたもの
動作原理は理解してない

転倒数はBinary Indexed Treeで求められるし使ってないけど…一応残しておく

Binary Indexed Tree

一点加算・区間和取得

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, i) の要素の総和を返す
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        # 足し算と引き算にはaddを使うべき
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])

初期値をO(n)で入れられるようにするべきかもしれない
和以外の演算もできるようにすべきかもしれない

# BITで転倒数を求められる
A = [3, 10, 1, 8, 5, 5, 1]
bit = Bit(max(A)+1)
ans = 0
for i, a in enumerate(A):
    ans += i - bit.sum(a+1)
    bit.add(a, 1)
print(ans)

Binary Indexed Treeの使い方のメモ

区間加算・一点取得

class BitImos:
    """
    ・範囲すべての要素に加算
    ・ひとつの値を取得
    の2種類のクエリをO(logn)で処理
    """
    def __init__(self, n):
        self.bit = Bit(n+1)

    def add(self, s, t, x):
        # [s, t)にxを加算
        self.bit.add(s, x)
        self.bit.add(t, -x)

    def get(self, i):
        return self[i]

    def __getitem__(self, key):
        # 位置iの値を取得
        return self.bit.sum(key+1)

いもす法みたいな使い方をしやすいようなBIT

区間加算・区間取得

# 未検証
class Bit2:
    def __init__(self, n):
        self.bit0 = Bit(n)
        self.bit1 = Bit(n)

    def add(self, l, r, x):
        # [l, r) に x を足す
        self.bit0.add(l, -x * (l-1))
        self.bit1.add(l, x)
        self.bit0.add(r, x * (r-1))
        self.bit1.add(r, -x)

    def sum(self, l, r):
        res = 0
        res += self.bit0.sum(r) + self.bit1.sum(r) * (r-1)
        res -= self.bit0.sum(l) + self.bit1.sum(l) * (l-1)
        return res

原理わかってない

セグメント木

RMQ

# セグ木
class SegTree:
    # 根は 1
    # 親は node>>1
    # 子は node<<1, node<<1 | 1
    # 兄弟は node^1
    # 値が入ってるのは offset:

    def __init__(self, n):
        self.n = n  # 要素数
        self.INF = float("inf")
        self.seg = [self.INF] * (n * 4)
        self.depth = len(bin(n))-2
        self.offset = 1<<self.depth

    def initialize(self, lst):
        # あとで書く
        pass

    def update(self, i, x):
        node = self.offset + i
        self.seg[node] = x
        while node > 1:
            # 親を更新
            self.seg[node >> 1] = min(self.seg[node], self.seg[node ^ 1])
            node >>= 1
    def getmin(self, a, b, k=1, l=0, r=None):
        if r is None:
            r = self.offset
        # a, b は再帰で変化しない値
        # 要求区間[a,b)と今見ている区間[l,r)が交わらない
        if r <= a or b <= l: return self.INF
        # 今見ている区間は要求区間に完全に含まれている
        if a <= l and r <= b: return self.seg[k]
        # どちらでもなければ子ノードを見る
        vl = self.getmin(a, b, k << 1, l, (l + r) >> 1)
        vr = self.getmin(a, b, (k << 1) | 1, (l + r) >> 1, r)
        return min(vl, vr)

確か プログラミングコンテストでのデータ構造 をPythonで書き換えたもののはず
コピペしてきたもののほうがクオリティが高いので供養

一点更新・区間取得

# https://atcoder.jp/contests/abc014/submissions/3935971
class SegmentTree(object):
    __slots__ = ["elem_size", "tree", "default", "op"]

    def __init__(self, a: list, default: int, op):
        from math import ceil, log
        real_size = len(a)
        self.elem_size = elem_size = 1 << ceil(log(real_size, 2))
        self.tree = tree = [default] * (elem_size * 2)
        tree[elem_size:elem_size + real_size] = a
        self.default = default
        self.op = op

        for i in range(elem_size - 1, 0, -1):
            tree[i] = op(tree[i << 1], tree[(i << 1) + 1])

    def get_value(self, x: int, y: int) -> int:  # 半開区間
        l, r = x + self.elem_size, y + self.elem_size
        tree, result, op = self.tree, self.default, self.op
        while l < r:
            if l & 1:
                result = op(tree[l], result)
                l += 1
            if r & 1:
                r -= 1
                result = op(tree[r], result)
            l, r = l >> 1, r >> 1

        return result

    def set_value(self, i: int, value: int) -> None:
        k = self.elem_size + i
        self.tree[k] = value
        self.update(k)

    def update(self, i: int) -> None:
        op, tree = self.op, self.tree
        while i > 1:
            i >>= 1
            tree[i] = op(tree[i << 1], tree[(i << 1) + 1])

"""
C = [int(input()) for _ in range(N)]

idx = [0] * N
for i, c in enumerate(C):
    idx[c-1] = i

seg = SegmentTree([0]*(N+1), 0, min)
for i in range(N):
    idx_ = idx[i]
    seg.set_value(idx_, seg.get_value(0, idx_)-1)
print(seg.get_value(0, N+1)+N)
"""

htkbさんのセグメント木
神

平衡二分探索木

Treap

# Treap
import random
class Treap:
    def __init__(self):
        self.node = None  # root

    def __str__(self):
        L = []
        def recursiveSearch(node):
            if node.left is not None:
                recursiveSearch(node.left)
            L.append((node.val, node.priority))
            if node.right is not None:
                recursiveSearch(node.right)
        recursiveSearch(self.node)
        return str(L)

    def add(self, x):
        i = self.bisect(x)
        self.node = self.insert(self.node, i, x)

    def remove(self, x):
        i = self.bisect(x)
        self.node = self.erase(self.node, i)

    def bisect(self, x):  # bisect_left
        def recursiveSearch(node):
            if node is None:
                return 0
            res = 0
            if x <= node.val:
                if node.left is not None:
                    return recursiveSearch(node.left)
                else:
                    return 0
            else:
                res += self.count(node.left) + 1
                if node.right is not None:
                    return res + recursiveSearch(node.right)
                else:
                    return res
        return recursiveSearch(self.node)

    def __getitem__(self, k, t=None):
        if t is None: t = self.node
        if k < self.count(t.left):
            if t.left is None:
                return t.val
            return self.__getitem__(k, t.left)
        elif k == self.count(t.left):
            return t.val
        else:
            if t.right is None:
                return t.val
            return self.__getitem__(k - self.count(t.left) - 1, t.right)

    class Node:
        def __init__(self, x):
            self.val = x
            self.priority = random.randint(0, 1<<30)
            self.left = None
            self.right = None
            self.cnt = 1
        def __str__(self):
            return str(self.val)

    def count(self, t: Node):
        return 0 if t is None else t.cnt

    def update(self, t: Node):
        t.cnt = self.count(t.left) + self.count(t.right) + 1
        return t

    def merge(self, l: Node, r: Node):
        if l is None: return r
        if r is None: return l
        if l.priority > r.priority:
            l.right = self.merge(l.right, r)
            return self.update(l)
        else:
            r.left = self.merge(l, r.left)
            return self.update(r)

    def split(self, t: Node, k: int) -> (Node, Node):  # [0,k),[k,n)
        if t is None: return None, None
        if k <= self.count(t.left):
            s = self.split(t.left, k)
            t.left = s[1]
            return s[0], self.update(t)
        else:
            s = self.split(t.right, k - self.count(t.left) - 1)
            t.right = s[0]
            return self.update(t), s[1]

    def insert(self, t: Node, k: int, x):
        l, r = self.split(t, k)
        return self.merge(self.merge(l, self.Node(x)), r)

    def erase(self, t: Node, k):
        l, r = self.split(t, k)
        _, r = self.split(r, 1)
        return self.merge(l, r)


"""
treap = Treap()
for i in range(100000):
    treap.add(i)
    s.add(i)
print(treap[50])
"""

重すぎて使い物にならない、供養

AVL木

これ
PythonでAVL木を競プロ用に実装した（誰か高速化してくれ） - 菜

↑はPythonにC++のsetに相当するものが無いから実装したものだけど、クエリ先読みできるならBITでなんとかなるらしい（わかってない）
オフラインクエリのset実装 - Tallfallの日記

ダイクストラ法

from collections import defaultdict
import heapq
class Dijkstra:
    # 計算量 O((E+V)logV)

    # adjはdefaultdictのリスト
    def dijkstra(self, adj, start, goal=None):

        num = len(adj)  # グラフのノード数
        self.dist = [float('inf') for i in range(num)]  # 始点から各頂点までの最短距離を格納する
        self.prev = [float('inf') for i in range(num)]  # 最短経路における，その頂点の前の頂点のIDを格納する

        self.dist[start] = 0
        q = [(0, start)]  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q)  # pop

            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if self.dist[src] < prov_cost:
                continue

            # 探索で辺を見つける場合ここに書く


            # 他の頂点の探索
            for dest, cost in adj[src].items():
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost  # distの更新
                    heapq.heappush(q, (self.dist[dest], dest))  # キューに新たな仮の距離の情報をpush
                    self.prev[dest] = src  # 前の頂点を記録

        if goal is not None:
            return self.get_path(goal, self.prev)
        else:
            return self.dist

    def get_path(self, goal, prev):
        path = [goal]  # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))

Pythonでダイクストラアルゴリズムを実装した - フツーって言うなぁ！ を改造したもの

クラスになってるけどそのまま使うことはほとんどしていなくて、
実装の参考にするために置いている

経路が必要がないならself.prevは必要ない

Union Find木

# unionfind
class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]

これどこかからコピペしたんだっけ…？

マス目の幅優先探索

# マス目の幅優先探索
for y, s in enumerate(S):
    for x, c in enumerate(s):
        if c=="S":
            start = (x, y)
        elif c=="G":
            goal = (x, y)
ans = 0
Open = [start]
Close = {start}
a = 0
flg = True
while flg:
    a += 1
    OpenNext = []
    for x, y in Open:
        for dx, dy in [(1,0), (0,1), (-1,0), (0,-1)]:
            if (x+dx, y+dy) not in Close and S[y+dy][x+dx] != "#":
                if (x+dx, y+dy) == goal:
                    flg = False
                OpenNext.append((x+dx, y+dy))
                Close.add((x+dx, y+dy))
    Open = OpenNext
    if len(Open) == 0:
        a = float("inf")
        break
ans += a

だいぶ前にメモとして置いておいた気がするけど使ってないし微妙に効率悪い、消す

高速ゼータ変換・高速メビウス変換

# 高速ゼータ変換

# 自身を含む集合を全て挙げる方
N = 3
f = [{i} for i in range(1<<N)]
for i in range(N):
    for j in range(1<<N):
        if not (j & 1<<i):
            f[j] |= f[j | (1<<i)]  # 総和は +=  # -=にすると逆変換になる
print(f)

# 部分集合をすべて挙げる方
f = [{i} for i in range(1<<N)]
for i in range(N):
    for j in range(1<<N):
        if j & 1<<i:
            f[j] |= f[j ^ (1<<i)]
print(f)

メモだけどわかりにくいと思うしどうやればわかりやすく書けるのかわからない

[{0, 1, 2, 3, 4, 5, 6, 7}, {1, 3, 5, 7}, {2, 3, 6, 7}, {3, 7}, {4, 5, 6, 7}, {5, 7}, {6, 7}, {7}]
[{0}, {0, 1}, {0, 2}, {0, 1, 2, 3}, {0, 4}, {0, 1, 4, 5}, {0, 2, 4, 6}, {0, 1, 2, 3, 4, 5, 6, 7}]

実行結果

最長回文

# Manacherのアルゴリズム
def man(S):
    i = 0
    j = 0
    n = len(S)
    R = [0]*n
    while i < n:
        while i-j >= 0 and i+j < n and S[i-j] == S[i+j]:
            j+=1
        R[i] = j
        k = 1
        while i-k >= 0 and i+k < n and k+R[i-k] < j:
            R[i+k] = R[i-k]
            k += 1
        i += k
        j -= k
    return R

フロー

Dinic法

# 最大流問題
from collections import deque
INF = float("inf")
TO = 0;  CAP = 1;  REV = 2
class Dinic:
    def __init__(self, N):
        self.N = N
        self.V = [[] for _ in range(N)]  # to, cap, rev
        # 辺 e = V[n][m] の逆辺は V[e[TO]][e[REV]]
        self.level = [0] * N

    def add_edge(self, u, v, cap):
        self.V[u].append([v, cap, len(self.V[v])])
        self.V[v].append([u, 0, len(self.V[u])-1])

    def add_edge_undirected(self, u, v, cap):  # 未検証
        self.V[u].append([v, cap, len(self.V[v])])
        self.V[v].append([u, cap, len(self.V[u])-1])

    def bfs(self, s: int) -> bool:
        self.level = [-1] * self.N
        self.level[s] = 0
        q = deque()
        q.append(s)
        while len(q) != 0:
            v = q.popleft()
            for e in self.V[v]:
                if e[CAP] > 0 and self.level[e[TO]] == -1:  # capが1以上で未探索の辺
                    self.level[e[TO]] = self.level[v] + 1
                    q.append(e[TO])
        return True if self.level[self.g] != -1 else False  # 到達可能

    def dfs(self, v: int, f) -> int:
        if v == self.g:
            return f
        for i in range(self.ite[v], len(self.V[v])):
            self.ite[v] = i
            e = self.V[v][i]
            if e[CAP] > 0 and self.level[v] < self.level[e[TO]]:
                d = self.dfs(e[TO], min(f, e[CAP]))
                if d > 0:  # 増加路
                    e[CAP] -= d  # cap を減らす
                    self.V[e[TO]][e[REV]][CAP] += d  # 反対方向の cap を増やす
                    return d
        return 0

    def solve(self, s, g):
        self.g = g
        flow = 0
        while self.bfs(s):  # 到達可能な間
            self.ite = [0] * self.N
            f = self.dfs(s, INF)
            while f > 0:
                flow += f
                f = self.dfs(s, INF)
        return flow

これ何を参考に実装したのか全く思い出せないけど気付いたらあった

最長増加部分列（LIS）

いかたこさんのものを使っています

最長増加部分列・最長共通部分列 [いかたこのたこつぼ]

最近共通祖先（LCA）

class Lca:  # 最近共通祖先
    def __init__(self, E, root):
        import sys
        sys.setrecursionlimit(500000)
        self.root = root
        self.E = E  # V<V>
        self.n = len(E)  # 頂点数
        self.logn = 1  # n < 1<<logn  ぴったりはだめ
        while self.n >= (1<<self.logn):
            self.logn += 1

        # parent[n][v] = ノード v から 1<<n 個親をたどったノード
        self.parent = [[-1]*self.n for _ in range(self.logn)]

        self.depth = [0] * self.n
        self.dfs(root, -1, 0)
        for k in range(self.logn-1):
            for v in range(self.n):
                p_ = self.parent[k][v]
                if p_ >= 0:
                    self.parent[k+1][v] = self.parent[k][p_]

    def dfs(self, v, p, dep):
        # ノード番号、親のノード番号、深さ
        self.parent[0][v] = p
        self.depth[v] = dep
        for e in self.E[v]:
            if e != p:
                self.dfs(e, v, dep+1)

    def get(self, u, v):
        if self.depth[u] > self.depth[v]:
            u, v = v, u  # self.depth[u] <= self.depth[v]
        dep_diff = self.depth[v]-self.depth[u]
        for k in range(self.logn):
            if dep_diff >> k & 1:
                v = self.parent[k][v]
        if u==v:
            return u
        for k in range(self.logn-1, -1, -1):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]

これパクったんじゃないっけ…？AOJ見たら自分がverifyしてる痕跡があったけど…
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3526639#1

幾何

いくつかあるけどAOJからコピペしたものが多いので割愛

その他細かいメモ

import sys
def input():
    return sys.stdin.readline()[:-1]
input = sys.stdin.readline

from functools import lru_cache
@lru_cache(maxsize=None)  # メモ化再帰したい関数の前につける

import sys
sys.setrecursionlimit(500000)
from operator import itemgetter
from collections import defaultdict
from itertools import product  # 直積

ord("a") - 97  # chr

N = int(input())
N, K = map(int, input().split())
L = [int(input()) for _ in range(N)]
A = list(map(int, input().split()))
S = [list(map(int, input().split())) for _ in range(H)]

itemgetterとかがどこにあったのか昔は覚えてなかったけど今は大丈夫なのでそのへんは消す

input = sys.stdin.readline は読み込むものが文字列じゃないときに使ってる

まとめ

コピペ多いね…

AtCoder黄色になった

注: この記事のPythonはPyPyを含む

黄色になった

年が変わる前に黄色になりたい → 無理だわ。AtCoder始めて1年経つ前に黄色になりたい → 無理だったわ。何が何でも黄色になりたい → なったわ。

f:id:nagiss:20190629162236p:plain

黄色になるまでにやったこと

精進

f:id:nagiss:20190629144615p:plain

C++はunratedだった平成ABCでしか使ってない

f:id:nagiss:20190629144745p:plain

f:id:nagiss:20190629144808p:plain

初見で解けなかった問題はACしないようにしてる（これは多分良くないが）ので少なめに出てると思う

知識

やった

青のときとの差分で（青のときの記事は今見ると微妙なので貼らないけど）

  • 動的計画法（DP）
  • Binary Indexed Tree（BIT）
  • 転倒数
  • セグメント木
  • トポロジカルソート
  • クラスカル法
  • 二分探索
  • 木の直径

やったけど使えてない

  • 最大流
  • スライド最小値
  • AVL木
  • 高速ゼータ変換・高速メビウス変換
  • 三分探索
  • 最長回文
  • 中国剰余定理
  • Grundy数
  • 最長増加部分列（LIS）

やってない

  • 最小費用流
  • 遅延評価セグメント木
  • プリム法
  • Rolling Hash
  • Trie木
  • Suffix Array
  • 行列（ABCで出たけど）
  • 高速フーリエ変換（FFT）
  • kD木
  • 幾何
  • 永続データ構造

ポエム（Python競プロについて）

賛否両論ありそう

Pythonの実行速度

AtCoderにはPyPyがあるので、その辺のスクリプト言語とは話が違う
このおかげで、保証されていないとはいえ、実際のところratedなコンテストではPythonで通せない問題は0に近い（黄coderが解かないような高難易度の問題は知らないが）

まあ定数倍で厳しい気持ちになることもあるけど、他の人の提出を見ると「頭悪い実装してた…」ってなるので…

Pythonもだいたいこれ

Pythonの利点

配列Aをもとのindexを保持したままソートしたい
C++の場合は

V<pair<ll, ll>> B;
rep(i, A.size()) B.emplace_back(A[i], i);
sort(B.begin(), B.end());

普通だな！

pythonなら

B = sorted(zip(A, range(len(A))))

楽～～～～～～～神～～～～～～～～～（実行速度を気にするならB = sorted(enumerate(A), key=itemgetter(1))としたほうがいいかもしれない）

コードが短く書けると間違いにくく・速く実装できるし、デバッグもしやすくなって、
これはかなり大きな利点だと思う

あとitertoolsのおかげで再帰を書く機会が大きく減るのが嬉しい
再帰は天才過ぎて頭がバグるのでitertoolsがあると天才を無駄遣いしなくて良くなる

itertools知る前は自力で書いてたので許して

結局Python競プロってどうなの

2019年6月現在Pythonで橙以上が存在しないので、Pythonが過小評価されている印象がある
これのせいで黄色が限界とかいう説まであるが、Pythonで黄色の人がC++使い始めたら途端に赤になるなんてことは有り得ない

少なくともAtCoderにおいては、自分はPythonの実行速度で悩むより頭の回転速度で悩むことがずっと多い
Pythonは実装が簡単に済むので余計なことに頭のリソースを割かずに済み、このレート帯ではC++に比べて不利ということはないと思う（似たことは他の人にも言及されている: titiaのノート: AtCoderで青になるまで）

頭の回転が速い人ならPythonでももっと上の色に十分到達できるはず

（どちらかというとPython競プロを長い期間続けている人が少ないことが原因な気がする）

Python競プロはまだ発展途上だと思っている
去年の段階ではPythonサブウエポン無しで黄色の人は3人程度（iehnさん、yaketake08さん、ukikagiさん）しかいなかったが、半年で4人増えた（hoxoshさん、ikatakosさん、maspyさん、自分）

f:id:nagiss:20190629153942p:plain

http://atcoder-circles.com/circles/pythonista

Python橙coderが出るのも時間の問題だと思う

まとめ

Pythonで黄色になると色違いボルケニオンをゲットできます

PythonでAVL木を競プロ用に実装した（誰か高速化してくれ）

（19/11/22 追記）

このAVL木どうも遅いっぽい

順序付き集合はPythonだと平方分割が速いことが熨斗袋さんによって判明したのでそれを使うといいと思う

熨斗袋さんによる実装
Submission #7482671 - AtCoder Beginner Contest 140

自分の実装（SkipListベース）
Submission #7488620 - AtCoder Regular Contest 033

Pythonで競プロをやるとAtCoderのレートが1970上がることが知られている（※個人の感想であり、効果・効能には個人差がある）が、Pythonには平衡二分探索木がなくて悲しい。なのでAVL木を実装した。

writerの助言もあり、なんとかPyPyでCPSCO2019 Session1 E - Exclusive OR Queriesを通せたが、かなり制限時間ぎりぎり。自分は諦めたので誰かこれをもっと高速にしてほしい（他力本願寺建立）

atcoder.jp

コピペだらけのコードだけど実行速度優先だから多少はね？

class AvlTree:  # std::set
    def __init__(self, values=None, sorted_=False, n=0):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # n: add メソッドを使う回数の最大値

        # sorted_==True であれば、初期値の数の線形時間で木を構築する
        # 値を追加するときは必ず n を設定する
        if values is None:
            self.left = [-1] * (n + 1)
            self.right = [-1] * (n + 1)
            self.values = [-float("inf")]
            self.diff = [0] * (n + 1)  # left - right
            self.size_l = [0] * (n + 1)
            self.idx_new_val = 0
        else:
            if not sorted_:
                values.sort()
            len_ = self.idx_new_val = len(values)
            n += len_
            self_left = self.left = [-1] * (n + 1)
            self_right = self.right = [-1] * (n + 1)
            self_values = self.values = [-float("inf")] + values
            self_diff = self.diff = [0] * (n + 1)  # left - right
            self_size_l = self.size_l = [0] * (n + 1)

            st = [[1, len_ + 1, 0]]
            while len(st) > 0:  # dfs っぽく木を構築
                l, r, idx_par = st.pop()  # 半開区間
                c = (l + r) >> 1  # python -> //2  pypy -> >>1
                if self_values[c] < self_values[idx_par]:
                    self_left[idx_par] = c
                else:
                    self_right[idx_par] = c
                siz = r - l
                if siz & -siz == siz != 1:  # 2 冪だったら
                    self_diff[c] = 1
                self_size_l[c] = siz_l = c - l
                if siz_l > 0:
                    st.append([l, c, c])
                    c1 = c + 1
                    if c1 < r:  # 左にノードがなければ右には必ず無いので
                        st.append([c1, r, c])

    def rotate_right(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == 2
        idx_l = self_left[idx]
        diff_l = self_diff[idx_l]

        if diff_l == -1:  # 複回転
            idx_lr = self_right[idx_l]
            diff_lr = self_diff[idx_lr]
            if diff_lr == 0:
                self_diff[idx] = 0
                self_diff[idx_l] = 0
            elif diff_lr == 1:
                self_diff[idx] = -1
                self_diff[idx_l] = 0
                self_diff[idx_lr] = 0
            else:  # diff_lr == -1
                self_diff[idx] = 0
                self_diff[idx_l] = 1
                self_diff[idx_lr] = 0

            # 部分木の大きさの計算
            self_size_l[idx_lr] += self_size_l[idx_l] + 1
            self_size_l[idx] -= self_size_l[idx_lr] + 1

            # 回転
            self_right[idx_l] = self_left[idx_lr]
            self_left[idx] = self_right[idx_lr]
            self_left[idx_lr] = idx_l
            self_right[idx_lr] = idx
            lr_container[idx_par] = idx_lr

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = 1
                nb = self_diff[idx_l] = -1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_l] = 0

            # 部分木の大きさの計算
            self_size_l[idx] -= self_size_l[idx_l] + 1

            # 回転
            self_left[idx] = self_right[idx_l]
            self_right[idx_l] = idx
            lr_container[idx_par] = idx_l

            return nb  # 新しい根の diff を返す

    def rotate_left(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == -2
        idx_r = self_right[idx]
        diff_l = self_diff[idx_r]

        if diff_l == 1:  # 複回転
            idx_rl = self_left[idx_r]
            diff_rl = self_diff[idx_rl]
            if diff_rl == 0:
                self_diff[idx] = 0
                self_diff[idx_r] = 0
            elif diff_rl == -1:
                self_diff[idx] = 1
                self_diff[idx_r] = 0
                self_diff[idx_rl] = 0
            else:  # diff_lr == 1
                self_diff[idx] = 0
                self_diff[idx_r] = -1
                self_diff[idx_rl] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] -= self_size_l[idx_rl] + 1
            self_size_l[idx_rl] += self_size_l[idx] + 1

            # 回転
            self_left[idx_r] = self_right[idx_rl]
            self_right[idx] = self_left[idx_rl]
            self_right[idx_rl] = idx_r
            self_left[idx_rl] = idx
            lr_container[idx_par] = idx_rl

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = -1
                nb = self_diff[idx_r] = 1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_r] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] += self_size_l[idx] + 1

            # 回転
            self_right[idx] = self_left[idx_r]
            self_left[idx_r] = idx
            lr_container[idx_par] = idx_r

            return nb  # 新しい根の diff を返す

    def add(self, x):  # insert
        # x を加える
        # x が既に入ってる場合は False を、
        # そうでなければ True を返す

        idx = 0
        path = []
        path_left = []

        self_values = self.values
        self_left = self.left
        self_right = self.right

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if x < value:
                path_left.append(idx)  # 重複を許さないので処理を後にする必要がある
                idx = self_left[idx]
            elif value < x:
                idx = self_right[idx]
            else:  # x == value
                return False  # 重複を許さない

        self.idx_new_val += 1
        self_diff = self.diff
        self_size_l = self.size_l

        idx = path[-1]
        if x < value:
            self_left[idx] = self.idx_new_val
        else:
            self_right[idx] = self.idx_new_val

        self_values.append(x)

        for idx_ in path_left:
            self_size_l[idx_] += 1

        self_diff[idx] += 1 if x < value else -1
        for idx_par in path[-2::-1]:
            diff = self_diff[idx]
            if diff == 0:
                return True
            elif diff == 2:  # 右回転
                self.rotate_right(idx_par, self_right[idx_par] == idx)
                return True
            elif diff == -2:  # 左回転
                self.rotate_left(idx_par, self_right[idx_par] == idx)
                return True
            else:
                self_diff[idx_par] += 1 if self_left[idx_par] == idx else -1
            idx = idx_par
        return True

    def remove(self, x):  # erase
        # x を削除する
        # x の存在が保証されている必要がある

        idx = 0
        path = []
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if value < x:
                idx = self_right[idx]
            elif x < value:
                self_size_l[idx] -= 1  # 値の存在を保証しているので
                idx = self_left[idx]
            else:  # x == value
                idx_x = idx
                self_size_l[idx] -= 1
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return True
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return True
            else:
                return True
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return True

    def pop(self, idx_):
        # 小さい方から idx_ 番目の要素を削除してその要素を返す（0-indexed）
        # idx_ 番目の値の存在が保証されている必要がある

        path = [0]
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            path.append(idx)
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                self_size_l[idx] -= 1  # 値の存在が保証されているので
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:
                idx_x = idx
                x = self_values[idx]
                self_size_l[idx] -= 1  # なんで？
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return x
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return x
            else:
                return x
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return x

    def __getitem__(self, idx_):
        # 小さい方から idx_ 番目の要素を返す

        self_left = self.left
        self_right = self.right
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:  # c == idx_
                return self.values[idx]
        raise IndexError

    def __contains__(self, x):  # count
        # 値 x があるか

        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:
                return True  # res + self_size_l[idx]
        return False

    def bisect_left(self, x):  # lower_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x
                return res + self_size_l[idx]
        return res

    def bisect_right(self, x):  # upper_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x:
                return res + self_size_l[idx] + 1
        return res

    def print_tree(self, idx=0, depth=0, from_="・"):
        if idx == 0:
            idx = self.right[idx]
        if idx == -1:
            return
        self.print_tree(self.left[idx], depth + 1, "┏")
        print("\t\t" * depth + from_ + " val=[" + str(self.values[idx]) +
              "] diff=[" + str(self.diff[idx]) +
              "] size_l=[" + str(self.size_l[idx]) + "]")
        self.print_tree(self.right[idx], depth + 1, "┗")

まとめ

# なんで？ をつけたコードをブログで公開するやつがいるらしい

これはブログ更新のハードルを下げるためのクソ記事です

両側キューって機能だけ見たら両側スタックだと思うんですよね
スライド最小値のアルゴリズムとヒストグラム中の最大長方形のアルゴリズムも多分そういう関係だと思うんだけど
うまく説明できない

Kaggle Master になるまでにやったこと

きやうぷろあゝもすなる〇〇になるまでにやったことといふものを、かぐらもしてみむとてするなり

Kaggle以前

授業

自分の通う大学には各学部が開講する科目とは別にグローバルエデュケーションセンター（GEC）という謎の部門（文科省が好きそうな名前だなあ）が開講する科目がある
その中に『学習者言語の分析』という自然言語処理をする授業があって、一昨年（2017年）何故かそれを取っていた
（この時点では機械学習って言葉を知っていたか怪しい）

この授業は理系向けというわけでもなかったので理論はそこそこに実際にPythonとsklearnでいろいろ書いていく感じだった
この授業で初めてPythonをさわった
この授業で

  • 線形回帰、kNN、決定木、ナイーブベイズ、ランダムフォレスト、SVM、
  • n-gram、TF-IDF
  • 入力の正規化
  • PCA
  • 交叉検証
  • データの可視化

あたりを勉強した

大学の授業は玉石混交だけどこの授業はかなり良かったし確実にKaggleにも役立った
近藤先生ありがとうございました

AtCoder

去年（2018年）の5月くらいにAtCoderをPythonで始めたら面白かったのでいっぱい問題を解いた

Kaggle以降

夏休み前くらいに学科の友人に言われてKaggleを始めた

Titanic: Machine Learning from Disaster

Titanic: Machine Learning from Disaster | Kaggle

Kaggleチュートリアルの定番であるところのTitanicをやった（8/17）
Kernelsを見ながら色々弄ってみてKaggleが何をする場所なのか把握した
去年取った授業でやったのは機械学習だったんだなあって初めて気付いた

多分初めてGBDTをさわった

解法が知れ渡っているものを実装したり（GBDTほど）精度が出ない学習器を実装したりするのは絶望的に面白くなかった記憶がある

Digit Recognizer

Digit Recognizer | Kaggle

画像もやってみたいなと思ったのでやはり定番のMNISTをやった（8/18）
Kernels のこれ Introduction to CNN Keras - 0.997 (top 6%) | Kaggle を見ながらほぼそのまま手元で動かしてみた

Augmentationの章に入るところで飽きたので提出データを作るところまで行かなかった

NNを触ったのはこれが初めてだったと思う

Home Credit Default Risk

1423位/7198

Home Credit Default Risk | Kaggle

1週間チャレンジだった（8月下旬くらい）
AUCという評価指標に初めて出会う人になった
特徴量エンジニアリングについてめっちゃいろいろググりながらやったけど何もわからなくて公開Kernelを超えるものを作れなかった
LightGBMの他にxgboostとCatBoostも試してみたりしてLightGBMの強さを実感した
hyperoptも触ってみたりした

shakedownしたので"trust your CV"を実感した

Google Analytics Customer Revenue Prediction

29位/1089 銀

Google Analytics Customer Revenue Prediction | Kaggle

通称: Rコンペ、GAコンペ、GACRP
通称を知っておくとTwitterでググるときに役立つ

学科の友人と後輩と4人で週3で集まって取り組んだ（10月・11月）

ひどいリーク（Google Analyticsのデモアカウントに答えがある）が発覚して途中でリスタートして未来を予測するコンペになった
これのせいでKernelsが死んだ（リスタート前のいっぱいupvoteされてるKernelがずっと跋扈していた）ので色々と自力でやることになった（これのおかげで良い順位が取りやすくなってたのかもしれない）

このコンペで一番悩んだのが交叉検証だった
時系列データに対して交叉検証をどう行えば良いのかググってもよくわからなかった
結局次のようにした：

  1. 2017/05/01～2017/11/15のデータで2017/12/01～2018/01/31のトランザクションを予測
  2. 1.を全部62日ずつずらしたものを計9個作る

特徴はよく覚えてないけど確認したらこんな感じだった
（集約の方法が<lambda>になってるのはlambda x: sum(map(bool, x))） f:id:nagiss:20190418154014p:plain

あと全部Kaggle Kernelで作業してたのでデータをメモリに乗せるのに苦労した
メモリ管理が大変でhitsの情報を使い切れなかったのは少し勿体なかった

未来を予測するコンペだったので結果が出たのは2月下旬、メダル付与されたのは3月になってからだった
結果公開されてから確認したらちゃんと特徴加えてCV良くなるごとにLBも良くなってたので普通に意味のあるコンペだったと思う

PLAsTiCC Astronomical Classification

161位/1094

PLAsTiCC Astronomical Classification | Kaggle

通称: plasticc

2週間チャレンジだった気がする（12月前半）
Discussionでガウス過程が話題になってたけどなんだそれと思って流していたら何も出来なかった

Kaggleは定跡とか考えてるだけじゃだめで、よく言われるように"do everything"が大事なんだなって思った
競プロ（のマラソンマッチじゃないやつ）とかだと正しいものをじっくり考えて実装するのが大事だけど
Kaggleはとにかく思いついたものを全部やってみるのがいいっぽくて、その違いをここで理解した

Traveling Santa 2018 - Prime Paths

78位/1874 銀

Traveling Santa 2018 - Prime Paths | Kaggle

通称: サンタコンペ、kaggleサンタ

機械学習コンペじゃなくていわゆる競プロのマラソンマッチ
メダルを1個も獲れてないのがつらかったのでとにかくこのコンペで初メダルを獲ろうと思っていた（12月後半～1月上旬）

このコンペでは参加してから終わりまで大体銀圏に居ることができた
コンペ中にしても結果にしてもメダル圏に入れたのは初めてだったので、
このコンペで初めて各メダルのレベル感を理解できた

それと公開Kernelのレベルは（コンペの規模とかにもよるんだろうけど）そんなに高くないのかもしれないなって認識を得た
（巡回セールスマン問題の計算量は動的計画法を使えば都市数nに対してO(n2 2n)で済むのはググればすぐわかるけど終盤までO(n*n!)のKernelしかなかった）（でも終盤に公開されたKernel群はつよつよだったね…）

Quora Insincere Questions Classification

Quora Insincere Questions Classification | Kaggle

Rコンペのときの人たちとチームを組んだけど自分は全然協力できなかった…（1月）

NTT corevoチャレンジ: 話者の性別・年代識別 （SIGNATE）

6位/190

Competition Detail／Nippon Telegraph and Telephone Corporation | SIGNATE - Data Science Competition

通称: 音声コンペ

音声には多少ドメイン知識があったので春休みの前半を使ってこっそり参加していた（2月）
NN系のコンペにちゃんと取り組むのは初だった

最終的に特徴抽出はWORLD（f0とスペクトル包絡）、モデルはDenseNet121（転移学習）を使った
前後の無音が長いデータも多かったので似非RMS値が一番大きくなる3秒くらいを抜き出してモデルの入力に使った
入力の正規化のやり方が悪くて10回目くらいに出したスコアを50回目くらいまでずっと超えられなくて地獄だった

敗因はAugmentationをほとんどしなかったことだったと思う
自分がやったのはtrain dataに対してローパスフィルタをかけたりかけなかったりすることだけだった
なんで普通に伸縮とかピッチシフトとかしなかったのか、今思うと本当にわからない

このコンペではずっとGoogle Colaboratoryを使って実験して最後seed averageするときにKaggle Kernelも使ったりした
無課金でも割といけるなと思った

このコンペが終わったころにRコンペのメダルが付与されてKaggle Expertになった

Santander Customer Transaction Prediction

9位/8800 金

Santander Customer Transaction Prediction | Kaggle

通称: Santander

春休みの後半もデータ分析に溶けた（3月）

解法とか大体のことはもう書いた気がする

9th place solution (nagiss part) | Kaggle
Santanderコンペ中に日記をつけようとしたけど途中で飽きたもの - 菜

日記のあとの部分のハイライトを今適当に書くと、

  1. 爆速で順位表を駆け上がるguchioさんとチームマージ、単純なrank meanでスコアが0.922から0.923になる
  2. mamasさんが奔走して順位の近いソロ勢2人（Graseck、Vicens）とチームマージ
  3. Vicensが色々stackingを試してくれる
  4. 色々やってスコアが上がらないと思ったらGraseckのアンサンブル用のsubmitデータがバグっていた
  5. みんなお互いの特徴使い合って伸ばしてるなとか、なんかチームメイト信用しすぎると良くないなとか思って勝手にNNを試したらバグって重みが共有されていい感じのスコアが出た
  6. 最終日にmamasさんの提案でNNの正規化を変えたものを試すことになった（もとはRankGaussだった）　MinMaxScaler使ったら学習が上手く行き過ぎたせいで締切25分前まで学習が終わらなくててんてこまいになった　10fold分の学習結果を自分がまとめるときにミスってsubmitデータの予測値を倍にしてしまったけどVicensがrerankしてくれていたのでとても救われた　残り5分の攻防だった
  7. 最終日の日本勢skypeで彼女いない歴＝年齢の自分が地蔵になる出来事が起こった

はい
（念のためですがGraseckもしっかり活躍しています）

チームを組むと天邪鬼な性格が良い結果を生むこともあるっぽい（多様性的な意味で）
あとチームメイトは適度に信用しつつ適度に信用しないのがいいっぽい（多様性的な意味とチームメイトのバグを見つける的な意味で）　自分が一番信用出来ないけど

(4/19 0:09追記) このコンペでGBDTに5倍くらい詳しくなった（mamasさんのおかげ）

(4/19 12:24追記) mamasさんの記事が上がりました。必読です
シナモンが金メダルを3つ取ってKaggle Masterになるまでにやったこと - mamastan’s blog

まとめ

Kaggle Masterになるためにはコンペに出る必要があるようです

Santanderコンペ中に日記をつけようとしたけど途中で飽きたもの

ここはチラシの裏――

3/7 (木) くらい

R コンペがのメダルが確定して Expert になったのでしばらく Kaggle はいいかなとか思ったけど
コンペがいっぱいあってつよい人が分散してる今しか Master になるチャンスはないのでは？とも思っていた 、
Signate の音声コンペで3位を取っていた方が Santander で4位にいることに気づいたので
リベンジするために（？）Santander を始める

この時点での kernel top は 0.898 か 0.899 くらいだったはず
R コンペのときの友人も誘ったが忙しそうだったので1人でやることになった

discussion や公開 kernel で触れられていることは

  • データが綺麗すぎる（欠損値がない、全部数値データ）
  • 変数どうしの相関係数を取るとどれもほぼ 0 （列が直交している）
  • そのため主成分分析済みのデータかと疑う意見もあった（否定的な意見の方がそれっぽかった）
  • var_68 が奇妙 （分散が小さいのに小数第4位で丸められているせい）
  • なにか工夫をするよりそのまま LGBM にかける方が良いスコアが出る

他に得られた情報として、

  • LB の 4位以下のスコアは 0.901 以下なのに上位 3 位は 0.904 以上
  • このツイート

があったので、何かあるんだろうなと思った

3/8 (金) くらい

なんかデータランダムじゃなくない？と思った（このときはヒストグラムの書き方が悪くて勘違いしただけ）ので変数を Count Encoding してみたら何故かスコアが上がった
この時点では LGBM のパラメータを公開 kernel にあるベストなやつにしてなかったりしたので上位に上がったのは次の日の朝

3/9 (土)

Count Encoding したやつを提出したら 0.900 の最上位近くに来た (CV は 0.90374)

ヒストグラムの書き方の間違いに気付いたので無限に悩み始めた

The Zoo チームがぶっちぎりのスコアを出して LB 1位 に躍り出ていた

変数ごとにガウス混合モデルつかってどの山に属するかの特徴を作って
Count Encoding したやつと一緒に計 1000 特徴で学習したらなんかちょっと上がって 0.901 の最下位になった (CV は 0.90212 で低下)
たぶん誤差

この時点で 11 位

3/10 (日)

カーネル密度推定 (KDE) を試したけど効果がなかった

bandwidth=0.004 は見た目と直感で決めた

たしかこの日くらいに一瞬 12 位に落ちたあと 11 位に戻った気がする
その後に GIBA 氏が The Zoo に join したんだけどあれは GIBA 氏だったのか・・・？

3/11 (月)

kde/count_enc の特徴量を (元の変数、count_enc と合わせて計 600 特徴量で) 使ってみると CV で 0.90578 が出た（LB は 0.900）

3/12 (火)

train の count_enc の平均と test の count_enc の平均に必ず 1.5 程度の差があることに気付いた (test のが大きい)

それに基づいて test だけ count_enc の値から 1.0 を引いて 400 特徴量で学習すると
LB が 0.901 中位くらいで 11 位から 8 位に上がった

private と public の境目らしきものに気付いた

夜 2 時間くらいしか寝られなかった

3/13 (水)

mamas さんとチームマージさせていただいた

count_enc の平均はだいたい train+2 ≒ public+1 ≒ private になってることに気付いた

それに基づいて test だけ count_enc の値から 1.0 を引いて 400 特徴量で学習すると
LB が 0.902 になって 7 位になった（直後に 8 位に戻された）

夜中
private が 50000 個ずつに分けられることを発見した
public も 50000 個ずつに分けられた group1, group2 とした

3/14 (木)

朝 Disscussion に動きがあった https://www.kaggle.com/c/santander-customer-transaction-prediction/discussion/83882

train を target で分けて各列をシャッフルしても結果が変わらないという
このスレで CPMP がカテゴリカル変数なんじゃね的なことを言ってる
勘弁してほしい

シャッフルしても結果が変わらないってことは多分交互作用がないってことなので
ロジスティック回帰が結構良い精度出すって情報見たときに気づくべきだったなと思った

group2 を全部 0 にして submit したらスコアが変わらなくて意味不明だった
group1 を全部 0 にすると 0.500 になった
group2 || private を 0 にすると 0.901 (変化なし) だった
50% ってうそじゃん！ってなった
こうなると今まで public と private と呼んでいたものが本当に public と private なのか怪しくなってくる

mamas さんがダミーデータが入ってるのでは？と考えてくれたのでなるほどとなった

mamas さんに AUC について教わったりした

色々と提案していただいた
・全体でcount encodingした特徴を加える
・count encodingをグループ毎に行う（public group1, public, group2, private group1, private group2)
・catboostでカテゴリカルを使う
・XGBoostでexact

3/15 (金)

そういえば num_leaves=2 のモデルが効果的だって話があったけどこれ交互作用を考慮してないモデルだな？って気付いた

LB が 0.902 のやつ（元の 200 特徴と count_enc から test だけ 1 を引いた 200 特徴の計 400 特徴）に、
Train だけに fit させた Count Encoding 特徴を加えて 600 特徴で学習させると LB が 0.903 になった

その後、複製されたデータを全部除いて Count Encoding すれば良いんじゃね？と気付いて
やってみたら count_enc の平均が違う問題とか CV と LB が一致しない問題とか色々と解決した
CV 0.90438, LB 0.904 で 8 位になってようやくスタートラインに立った気がした

⎳geu(るぎう) on Twitter: "なるほどね… "

cnt_trn と cnt_all の比をとってみると CV 0.90478 になった

mamas さんに GCP の使い方を教わった
32CPU、128GB RAM、つよそう
プリエンプティブならお金出すのでどんどん使ってください的なことを言われた
僕は貧乏性だったので価値観の違いを感じてちょっとつらい気持ちになった

cnt_trn と cnt_all の比を取った 200 特徴と差をとった（これは実質的に cnt_test） 200 特徴を加えて、
計 1000 特徴で学習させると CV 0.90517 LB 0.905 が出た（差を取るのは mamas さんの提案）

3/16 (土)

AtCoder で AGC があったので始まる前に発見の要点だけ mamas さんに伝えておいた

・talkingdataをググった
・kdeを試したらcntとの比でスコアが上がった
　・比を取らないでそのまま使うとCVが下がった
・ダミーのデータは正例でも負例でもなさそうだった
　・public(だと思っていたもの)から目的変数にかかわらず適当に値をコピーしてる

AGC で爆死したのでしばらく引きずった

mamas さんからカテゴリカル特徴と numerical 特徴が混ざってると仮定した場合の処理を
色々と教わった

3/17 (日)

カテゴリカル特徴があると仮定して 2 つの列を使った aggrigation 特徴を作ったがスコアは下がった

この日に自分の見つけたのはこんな感じだった
・cnt/kdeの特徴量が割と強くて、cnt_trnとcnt_trn/cnt_allを消しても（=元の変数とcnt_allとcnt/kdeの600特徴で学習させても）ほとんどCVが変わらない
・target=1とtarget=0でcnt/kdeの分布が変わらないように見える

3/18 (月)

朝(昼)目を覚ますと mamas さんが 10 時くらいにこんなツイートをしていた

スマホを見ると mamas さんからの 9 時頃の通知があったが探しても見つからなくて幻覚だったのか？となった

mamas さんが何を発見したのか知らされてなくてずっと悶々としていた

KDE の bandwidth を倍にしたり半分にしたりしたやつの学習を試したりした（効果は微妙）

結構昼寝した

colsample_bytree を 0.05 から 0.5 まで上げたら LB 0.909 が出て順位が上がった
0.05 は交互作用あんまり考えないってことだったからそれはそうだった
0.9 も試したけどやりすぎっぽかった

夜になって教えてもらったことによれば、どうやらデータは既にシャッフル済みのものらしい
話を聞いているときは割と疑ってかかってたがその後いろいろ考えてみると段々と納得してきた
それなら確かに count encoding が効いたり kde が効いたりする
そっから使える特徴が何か話し合ったりした

各 n について var_n と n_count_enc と n_cnt_per_kde だけで予測して、
その 200 個の予測結果をつかって num_leaves=2 で学習 (stacking) させたらスコアが爆上がりした

それぞれちびモデルとメタモデルと名付けられた

3/19 (月) ～ 3/25 (月)

あらゆることを試したがスコアがびくともしない
順位が 3 位から 11 位に落ちた
public/private 分割とダミーデータの存在が Kernel で一気にバレた
もうおしまいだよ

3/26 (火)

mamas さんと久々におはなしして kde 抜いたのを試してないなとなったので抜いてみたらいとも簡単にスコアが上がってしまった

それとは全く関係なく、ちびモデルの num_leaves を 13 から 7 に減らしたらもっとスコアが上がってしまった

3/27 (水)

パラメタ探索を始めた

日記はここで終わっている・・・