AHC017参加記~PyPyによる解法~

はじめまして、nadareと申します。

普段は機械学習エンジニアとして、レコメンドエンジンの製作や、kaggleやatmacupのような機械学習コンペティションへの参加をしています。

今回はTHIRD プログラミングコンテスト 2022 （AtCoder Heuristic Contest 017）に参加し、全体で126位になりました。 Python3での提出に限定した場合、pretestで3位の絶対スコア、finalで2位の相対スコアだったので、遅いPythonの中では健闘した方だと思います。

本ブログでは自身の解法についての解説と、参加した感想を書いていきます。

overview

除く辺の条件をいくつか設定し、その制約を満たす範囲で除く辺をDFSで伸ばしながら初期解を生成しました。 その後、除く辺の条件を満たしつつ、除く辺同士を繋げた大きさを最大化するように遷移し山登り法を行いました。 遷移後は、除いた辺の周囲から何個かの点のペアを作り最短距離の和を計算して、悪くなった場合は遷移を取り消しました。

table of contents

• スコアとビジュアライズ結果
  • 入力別スコア
  • ビジュアライズ結果
• solution
  • 設定した制約について
  • 初期解生成
  • 辺の遷移
  • 評価方法
• technique
  • dijkstra -> A*による高速化
  • UnionFindの部分更新による高速化
• うまくいかなかったこと
• 感想

スコアとビジュアライズ結果

入力別スコア

wleiteさんのstatics(https://tc-wleite.github.io/ahc017)より

綺麗に得意不得意分かれたな#AHC017 pic.twitter.com/NWYoskP1nQ

— nadare🌱 (@Py2K4) 2023年2月7日

ビジュアライズ

seed=0 6685286点でした pic.twitter.com/yePn4lI7Ta

— nadare🌱 (@Py2K4) 2023年2月5日

solution

設定した制約について

除去する辺を選ぶ際に、以下の制約を設定しました。

1. ある辺を除去する際、ある辺の二点を結ぶある辺を使わない最短経路が残っていること
2. 次数が4以上の頂点においては、除去する辺同士が隣り合わないこと

この二つの制約を設けることで高速化と、限られた時間内でいい遷移を選びやすくなりました。

二番目に短い経路の確保

概要

全ての辺についてその辺を使わなかった際の最短経路(準最短経路とします)をA*の経路復元で求めておきました。 辺を除く際は以下の判定を行いました。

• 除く辺に対して除去済みの辺が準最短経路に含まれていないか
• 除去済みの辺に対して除く辺が準最短経路に含まれていないか

メリット

この条件を設定することにより、以下のメリットが生まれます。

• ある辺を除いたときその二点間まで極端な遠回りをすることを避けられる
• 必ず他のパスが活きているので、グラフの連結性の判定をしないですむ

この条件を満たすことは簡単で、初期解の作成の後少し遷移させるだけで秒もかからず達成できました。

アルゴリズム

除去済みの辺が最短経路に含まれているかは、事前に計算した準最短経路が除去済みの辺に含まれていないかの判定で簡単にできます。 後者の他の除去済みの辺の準最短経路に除く辺が含まれているかは、各日において準最短経路として使われた回数を配列として保持しておき、辺の追加や除去の度に更新することでO(1)で判定できます。

隣接辺を除かない

概要

いい点をとれた時のビジュアライザを確認した際、除去した辺が連結していてかつ適度に広がっている状態だといい点数をとれることに気づきました。 そこで、各頂点における辺を角度順に並べ、各辺について左右の辺を一緒に遷移してはいけないリストを作成しました。

アルゴリズム

各頂点の隣接辺についてatan2(y, x)を計算することで角度を求め、その順番で並びなおしました。

初期解生成

初期解は上記の制約を守りながら除去する辺をDFSで長く伸びるようにしながら作成しました。 この際一日ごとに一気に伸ばすのではなく、何サイクルかに分け1サイクル目では最大X個まで、2サイクル目では最大2X個までとすることで横に広がりすぎないようにしました。

辺の遷移

概要

辺の遷移は一つ除去する動かすか、除去する辺につながった除去する辺を全てまとめて動かすかの試行を毎回すべての日を対象に行っていました。 動かす日の決定は除去した辺同士がつながっている数が同じか増える遷移に限定しました。

アルゴリズム

辺の除去先では設定した制約を満たすかを毎回確認しました。 移動させる日は、除去した辺同士の連結数をUnionFindにより求め、元と同じかそれより大きくなる日を選びました。

評価方法

辺の移動先を決めた後は、除いた辺を使いそうな二点間の移動距離を何個か計算し、それがよくなるかどうかで遷移を確定するか決めました。

辺を一つ移動させる場合

辺uvを移動させる場合は、頂点vに近い点xからベクトルuvとvxのコサイン類似度が高い候補集合Xと、頂点uに近い点yからベクトルvuとuyのコサイン類似度が高い候補集合Yを選びました。 集合Xと集合Yのなかから、(x, y)の中点と(u, v)の中点のユークリッド距離が近くなるペアをいくつか選び、(x, y)間の最短距離をA*で計算し除去前後で比較しました。

辺を複数移動させる場合

全ての頂点に対して、どの辺ものぞかない状態での各頂点から最も最短経路が遠い点までの最短経路を事前計算しました。 辺ごとにどの頂点のペアで使われていたかを転置インデックスでもっておき、除去する辺の集合がよくつかわれているペアの最短距離を除去前後で比較しました。

technique

dijkstra -> A*による高速化

辺を一つも除去しない状態での全対最短経路をdijkstraを複数回繰り返すことで計算しておき、その距離をヒューリスティックな距離としてA*を計算しました。 これにより、各頂点から最も遠い辺までの距離を計算するときは5倍くらい早くなりました。

UnionFindの部分更新による高速化

繋いである辺をもう一回繋げないように注意してコードを書くことで、各連結集合が保持する辺を持っているUnionFindを書くことができました。コードは以下になります。

class EdgeUnionFind():
    def __init__(self, N):
        self.parent = list(range(N))
        self.edge_size = [0] * N
        self.edges = [[] for _ in range(N)]
    
    def find(self, i):
        if self.parent[i] == i:
            return i
        else:
            self.parent[i] = self.find(self.parent[i])
            return self.parent[i]
    
    def unite(self, i, j, e):
        a = self.find(i)
        b = self.find(j)
        if a != b:
            if self.edge_size[a] < self.edge_size[b]:
                a, b = b, a
            self.edge_size[a] += self.edge_size[b]
            self.edges[a] += self.edges[b]
            self.edge_size[b] = 0
            self.edges[b] = []
            self.parent[b] = a
        self.edge_size[a] += 1
        self.edges[a].append(e)
 
    def match(self, i, j):
        return self.find(i) == self.find(j)

辺を繋げるときはそのままuniteします。 辺を除くときはその辺とつながる頂点の親を全て更新するのが大切で、self.subopt_uftがUnionFindとしたとき 頂点u, vをつなぐ辺iをUnionFindから消す場合は以下のようなコード

g = self.subopt_uft.find(u)
edges = [e for e in self.subopt_uft.edges[g] if e != i]
self.subopt_uft.parent[u] = u
self.subopt_uft.parent[v] = v
self.subopt_uft.edges[g] = []
self.subopt_uft.edge_size[g] = 0
for e in edges:
    eu, ev, _ = self.graph.edges[e]
    self.subopt_uft.parent[eu] = eu
    self.subopt_uft.parent[ev] = ev
for e in edges:
     eu, ev, _ = self.graph.edges[e]
     self.subopt_uft.unite(eu, ev, e)

辺をまとめて消す場合は以下のようなコードを書いていました。

g = self.subopt_uft.find(self.graph.edges[members[0]][0])
edge_members = self.subopt_uft.edges[g]
if check_difference:
    remain_members = list(set(edge_members) - set(members))
else:
    remain_members = []
self.subopt_uft.edges[g] = []
self.subopt_uft.edge_size[g] = 0
for m in members:
    u, v, w = self.graph.edges[m]
    self.subopt_uft.parent[u] = u
    self.subopt_uft.parent[v] = v
    self.remove_map[m] = False
    self.remove_edge_per_node[u] -= 1
    self.remove_edge_per_node[v] -= 1
    self.sub_path_cost -= (self.remove_edge_per_node[u] == 0)
    self.sub_path_cost -= (self.remove_edge_per_node[v] == 0)
    for sub_path in self.graph.subopt_roots[m]:
        self.subpath_used_count[sub_path] -= 1
self.removes.difference_update(members)

for m in remain_members:
    u, v, w = self.graph.edges[m]
    self.subopt_uft.parent[u] = u
    self.subopt_uft.parent[v] = v
for m in remain_members:
    u, v, w = self.graph.edges[m]
    self.subopt_uft.unite(u, v, m)

うまくいかなかったこと

• 除去する辺のswap: 遷移の良さに対して計算時間がかかりすぎた
• annealing: pythonの時間だと山登りでも時間が足りなかった
• いくつかの代替指標: 辺を多くつなぎつつ頂点の数は増やすなどの制約を入れてみたがあまり効かなかった

感想

上位陣の解法を見ると今回は高速化がキモとなるコンテストで、Pythonは言語選択自体が悪かったように感じます。 ただその中では制約に工夫を入れたことで、遅い言語なりに頑張れたのかなと思います。

今回の問題はやりこむほどに色々見えてきて、一週間丸々破滅楽しむことができました。 ビジュアライザもデバッグから考察にまでいろいろ活躍して本当に良かったです。

THIRDさん、AtCoderさん、そしてライバルの皆さん、楽しい対戦本当にありがとうございました。

HTTF 2023 qual 54th place solution

あいさつ

はじめまして、nadareと申します。 普段は機械学習エンジニアとして、レコメンドエンジンをつくったりkaggleやatmacupのような機械学習コンペティションに参加しています。

AtCoderも三年前くらいまではアルゴに参加していたのですが、就職後はkaggleのHaliteコンペやCodingGame等の長期コンテストが中心になっていました。

今回はHTTFではじめてratedのヒューリスティックコンテストに参加して、54位になったので解法やテクニックをまとめたいと思います。

overview

グラフの頂点を次数(接続している辺の数)が多い順に並び替え、大きい順に並べた次数の配列を二乗誤差で比較した際に最も似たグラフを予測として出力しました。 グラフのNは黄金分割探索によって決定し、一定のルールでグラフをたくさん生成したのち、焼きなましで用いるグラフの組み合わせを最適化しました。

ある程度整理したコードは以下のリンクになります。本記事中で出てくる関数は以下のコードに出てくるものです。 Submission #36724658 - HACK TO THE FUTURE 2023 qual（AtCoder Heuristic Contest 016）

• solution
  • グラフ生成
  • 最適N探索
  • スコアシミュレーション
  • グラフ組み合わせ探索
• technique
  • numpyによる並列化
  • matplotlibによる可視化
  • ipythonによるテスト
  • joblibによるパラメータ探索

また、私と類似した解法でyunixさんがツイートで解説を行っています。 こちらを先に読むとより理解が深まると思います。

solution

グラフ生成

グラフ生成方針

今回の方針では多様で区別の付きやすい次数の組み合わせを作ることが大切でした。 特に、次数の平均よりも何個かの点の次数が大きく離れていることが重要で、

• 次数が4の頂点が10個のグラフ vs 次数が5の頂点が10個のグラフ
• 次数が0の頂点が10個のグラフ vs 次数が5の頂点が5つ、次数が0の頂点が5つのグラフ

では、後者の方が見分けがつけやすかったです。 (これは何パターンかグラフの生成方法を試し、得点の高かったケースと低かったケースをそれぞれ可視化しながら見つけました)

グラフ生成方法

以下の方針でパラメータを渡せば自動的に作れるような関数を作成しました。

• N個の頂点をX個とN-X個に分割する。(0 ≦ X ≦ N/2)
• それぞれ片方ずつのみで頂点を結びグラフを生成する。(make_side_sparse_expression関数)
• 最後に両者の頂点を結ぶ。(make_inter_sparse_expression関数)

make_side_sparse_expression

二つに分割した頂点に対しては以下の二種類のグラフを作成しました。

• 次数が全て同じグラフ
• 次数が単調に変化するグラフ

次数が全て同じグラフ

次数が全て同じグラフは頂点数Xが奇数の時はX/2 + 1個、Xが偶数の時はX個作成できました。 作成方法は二種類あり、奇数の時は前者、偶数の時は後者で作成しました。

• 頂点を円形に並べたとき距離A以内の頂点と辺を結ぶ方法(次数0~2Aのグラフができる)
• 頂点を半分ずつにわけ、片方から片方へA個の辺を結ぶ方法(次数0~Aのグラフと、補グラフでA~2Aのグラフができる)

次数が単調に増加するグラフ

結ぶ辺が変化する傾きのαと切片のheightを与え、以下のようなコードで生成しました。

for i in range(X):
     for j in range(i + 1, min(X, i + 1 + int(round(alpha * i + height)))):
        sparse_expressions.append((left + i, left + j))

make_side_sparse_expression

片方のグラフのすべての頂点からそれぞれA本ずつ、もう片方のグラフの頂点へ辺を結びました。 これにより片方は次数がA、もう片方は次数がA x 頂点の比で増えました。

パラメータの与え方

片方のグラフの大きさやその高さ、単調増加させるときの傾きは全探索すると間に合いませんでした。 そのため、NやM、epsの大きさから増やす値の大きさを手探りで決定しました。(generate_graphs関数)

最適N探索

あるM, epsのときにNとスコアの関係は凸関数のようになると予想しました。 そこでNを決定するために黄金分割探索を実装しました。 黄金分割探索は凸関数に対し、上端と下端を狭めながら頂点を探す手法で、効率的な探索ができます。 詳しい解説は省きますが、golden_search関数で実装しました。

スコアシミュレーション

最適Nを決めるためにはスコアの高速なシミュレーションが重要でした。 シミュレーション方法は、今回の方法の場合

• 全ての辺にたいしてエラーをシミュレーションする方法: O(N²)で正確
• 次数に対して二項分布に従う乱数でシミュレーションする方法: O(N)でだいたい正確

の二種類のシミュレーション方法を実装しましたが、スコアとの乖離から後者を採用しました。

それぞれのグラフにノイズを加えた際の次数の期待値はGraph.calc_expectで実装し、それらに対してPredictor.simulate関数でスコアを計算しました。 二項分布に従う乱数はnumpyのnp.random.binomialを用いました。 正確なスコアを計算するには頂点の次数に対して乱数を加えた後、必ずソートした値で期待値を計算することが重要でした。

グラフ組み合わせ探索

貪欲パート

グラフの組み合わせは最初に全結合のグラフを選んだ後、貪欲にそれまで選んできたグラフとの距離が最も遠いグラフを選び続けました。 正確なスコアのシミュレーションには次数の期待値を乱数を加えてからソートをする方法で計算する必要があったのですが、この貪欲で選ぶ段階ではソートしてから期待値を計算しても大体同程度のスコアが得られました。

焼きなましパート

Nを決定した後は焼きなましでグラフの組み合わせを改善しました。 この際に毎回正確なシミュレーションをすると焼きなましの試行回数をとれないので、グラフを入れ替えた際に一番近いグラフとの距離が大きくなればOKというように近似し、時間で無理やり遷移させる確率を変えながらグラフの組み合わせをよくしました。(Predictor.climbing関数)

technique

numpyによる並列化

生のPythonでループを書くと遅いので、numpyによって高速化を行いました。 numpyを採用した理由は、np.random.binomialが使えたというのもあるのですが、普段はdeeplearningのためにTensorFlowの関数を用いたGPUによる高速化を行うことが多く、行列計算による高速化に慣れていたのが理由です。(大体似た感じで書けますが、たまにnp.linalg.svdとtf.linalg.svdみたいに違う関数があるので〇にますが...) numpyは配列のindexingが簡単ですが、tensorflowはtf.gatherやtf.tensor_scatter_nd_XX系を使う必要があります。この辺りは慣れるとパズルみたいで楽しいです。

matplotlibによる可視化

生成したグラフの次数の配列の組み合わせはmatplotlibで可視化しました。 以下のツイートのようなグラフを生成し、どのようなグラフがいい性質を持つかを考察していました。

#HTTF #AHC016 解法ざっくり
暫定51位　23,147,476,754点
各頂点につながる頂点の数を数え、小さい順に並べる。
その並べた値をM個用意しておいて、どの線に近いかをl2_lossで比較して一番近いものに判別していました.
たくさんグラフのパターンを用意して、貪欲初期値→焼きなましでばらけさせました pic.twitter.com/LGK0INz2KF

— nadare🌱 (@Py2K4) 2022年11月20日

Jupyter notebookによるテスト

テストはJupyter notebook上でマジックコマンドを用いて一つのバージョン一つのセルでテストを回しました。 公式のテスターを用い、以下のようなコードでテストを回しました。

for i in range(20):
    print(i)
    inp = f"in/{i:04}.txt"
    oup = f"out/{i:04}.txt"
    !tester.exe python script/exp027.py < $inp > $oup

joblibによるパラメータ探索

今回は各土日に集中して終了ぎりぎりまで取り組んだため、事前にMとepsから最適なNを決定し埋め込むことまでたどり着けませんでした。 ただ、途中で並列化によるN探索のコードは書いていて、その際はjoblibによる並列化を行っていました。 joblibはPythonで(比較的簡単に)プロセス並列を行うためのライブラリで、以下のようなコードで並列化ができます。

from joblib import Parallel, delayed
from math import sqrt
Parallel(n_jobs=1)(delayed(sqrt)(i**2) for i in range(10))

感想＆謝辞

HTTFは2018年の#ふみこん openから毎年参加しているのですが、今回もとても面白い問題でした。 本戦オープンや来年以降も楽しみにしています！ありがとうございました！

第四回atmaCupに参加してきました

オンサイトのデータ分析コンペティションのatmaCupの第四回に参加してきました。 これは1週間の間にお題について最も良い制度の予測をした人が勝ちというkaggleの期間が短い版です。 atmaCupは問題の質に定評があるコンペで、自分はこれで三回目の参加になります。

コンペについて

今回のお題はリテール予測で、買い物の履歴が与えられるので、ある買い物時に特定カテゴリの商品が一緒に買われたかどうかを予測するという課題でした。 特定カテゴリは全部で13種類あり、買い物ごとに13カテゴリ分それぞれ購入されたかどうかを01で予測し、macroAUCで評価します。 訓練データとテストデータは時系列で分割されていて、訓練データには二年分の特定カテゴリ以外の購入履歴と、一年三か月分の特定カテゴリの購入履歴が与えられました。

データは

• 購入日時
• 買い物ごとに付与されるID
• ユーザーごとに付与されるID
• 店舗ごとに付与されるID
• 購入された商品のIDと名前
• 商品について粒度ごとに四段階に分割されたカテゴリ名
• 商品ごとの数量と価格

等の情報が与えられました。

また、データセット自体にも特徴があり

• テストデータのうち半分のユーザーは訓練データに出現しない(コールドスタート問題)
• 購入データは一度に5品以上の商品が購入されたデータに限る

という特徴がありました(後者についてはユーザーの情報ではなく、商品の組み合わせの情報から特定カテゴリの商品が購入されるかを予測してほしいという目的があったようです)

今回の共同開催者であるリテールAI研究会さんの記事(https://diamond-rm.net/technology/28705/)を見ると、 目的のカテゴリがどのような場合にセットで買われやすいかの分析をすることで、 ある商品を買った人にセットで特定カテゴリの商品を勧める、 あるいはセットで買いやすいような商品配置にできるようになり消費者も店もハッピーになれそうな感じがしました。

分析やモデルについて

データの分析では特定カテゴリ以外と特定カテゴリでクロス集計を行い、買い物やユーザー、アイテムごとに集計や次元圧縮を行って統計的に特徴量を作ったり、平日の昼間に買い物をしているか、おつまみを一緒に買っているかといったデータの分析途中で得られた知見を元にした温かみ(?)のある特徴量を作ったりしてモデルに組み込まれていました。

予測モデルは勾配ブースティング木の一種であるLightGBMが圧倒的に人気で、上位陣はモデルをホットスタートとコールドスタート用にモデルを分けて取り組んでいる人が多かったです。

バリデーションもホットスタートではStratifiedKFold、コールドスタートではユーザーごとのGroupKFoldが人気だったように感じます。

自分のモデルについて

特徴量関連ではtarget encoding関連は強力な特徴だったのですが、データの正例と負例に大きな偏りがあり、件数の少ないカテゴリでうかつな操作をするとすぐにオーバーフィットしてバリデーションのスコアが下がってしまうのでスコアの推移を見ながら慎重にtarget encodingの方法を選ぶ必要がありました。

バリデーションについては時系列データだったので脳死で時系列による分割を考え、ホットスタートの方は時系列のhold-out、コールドスタートの方は時系列のhold-out × GroupKFold(5fold)で分割しました。CVは.841+.680で平均するとちょうどLBと対応していて妙な安心感はあったものの、上位陣は時系列で分割していなかったので使えるデータが少ない分損していて、late submissionで時系列の分割をやめたら順位で二つ分くらい上がりました……

また、モデルについては13個バラバラのモデルを予測するのではなく、目的のカテゴリを変数にして一つのモデルで学習させていました。初手でこれをやっていたので13個モデルを作る方は試していなかったのですが、両方試してアンサンブルしとけばよかったなと反省しています。

計算環境について

データ自体も刺激的で学びがあったのですが、今回はMicrosoftさんに計算環境を提供して頂いたので、計算をAzure上で無料で実行することができいい経験になりました。 これまでクラウド関連はなんとなく避けて通ってきたのですが、初日のチュートリアルやslack上でのサポートのおかげで初心者の自分でも使うことができました。 特に良かったのは、普段使っているエディタのVSCodeとの相性が良かった点で、ローカルと似た感じの雰囲気でコードを書けたのが使いやすかったです。

感想

順位は15位で自分の実力的には妥当かなというラインなのですが、late subの結果を見るともう少し上を狙えたかも……という気がします。 次のatma杯では10位以内を目指して精進を重ねていきたいです。

Kaggle Days Tokyoで初対面のテーブルデータコンペ初心者とチームを組んで戦った話

2019/12/11~12に開催されたKaggle Days Tokyoに参加してきました。

二日目はオフラインコンペで、日本経済新聞社さん*1に提供していただいたデータセットを使って日経新聞購読者の年齢を推測するというテーブルデータ+NLPの課題が与えられました。

ルールは8時間制限で、チームは上限が3人まで参加OK、当日は会場でチームマージを募集するコーナーがあったのでそれに参加して初対面の方々とチームを結成しました。 チームの組み方はその場で集まった人をkaggleの経歴順に並べ番号を1, 2, 3, 4, 1, 2...と振っていくやり方でしたが途中でなんやかんやあっていつの間にかチームができていました。

チームについて

メンバーは

• 私(nadare): kaggle Expert petfinderから半年休んでたし実質一年で経歴を詐称したにもかかわらずチームで一番経験のある枠に選ばれた
• Wenyan Ge氏: kaggle Novice テーブルデータの扱いに多少経験はあるが、kaggleには初参加
• Sunny氏: kaggle Novice 普段は画像認識系のNNを扱うTBD初心者で、kaggleには初参加

チーム名は最後まで決まらず、Sunny氏の名前のままLBにはいました。二人とも海外出身の日本で働くエンジニアだったので、二人は英語で話して自分は日本語で二人に話しかけるという形でコミュニケーションをとりました。私は二人へ日本語でゆっくりはっきり聞こえるよう話しかけていたので自分たちの作戦は周囲に筒抜けだったのではないかと思います。(騒がしくしてごめんなさい🙇)

開始~ランチまで

　自己紹介からはじめ、列名の読解に取り組み日経新聞電子版のドメイン知識とかを共有しつつ全員でデータを眺め意味を探ろう*2としました。その後ランチ開始の十二時まで四十分くらいで各々ベースラインモデルを作って感想を共有する流れを提案し取り組みました。結果は割と散々で、自分のモデルはtrain_df, test_dfのみ縛りでしたがLB13.85のstarter_kernel以下で割と落ち込みました。

ランチ

　ランチをゆっくり食べながら、特徴量についてのアイデアを交換しました。自分のモデルはuser_idが5番目にimportanceの高いハチャメチャモデル*3だったので、ひょっとしてuser_idに秘密があるのでは(例えば振られた番号が日経新聞の会員の登録順になっていて、そこから年齢について推測できるetc)等を推測し盛り上がりましたが、結局targetと相関係数をとったりして無関係そうだということが分かりました。悲しい

ランチ後~二人が完全に初心者だと気づくまで

　今回のkaggle daysはexpert以上が100人くらい参加していて、一日目の発表もかなり高レベルだったので私は全員がかなりの経験者だと考えていました。それなので私はランチ後に全員で別々にモデルを作って最後にアンサンブル形式を提案したのですが、二人の手があまり動いていないようだったので話してみたところ、二人ともテーブルデータの経験が本当の意味で少し*4だったようなので方針を切り替える必要がでてきました。Sunny氏が公開kernelを元に特徴を追加していくことを提案したので、自分はテクニックが必要そうなメタデータ由来の特徴に絞って作り、二人に特徴量をつくるヒントになりそうな内容をどんどん投げていく方針をとりました。

役割分担について

　最初は二人に『記事を読んだ分布の時間が特徴的な形をしているのでこれを基に特徴量がほしい』、『携帯の機種につながる情報は新しい機種を持つ人ほど若い人だと思うからそれにつながる特徴を探してほしいくらい』の粒度でヒントを投げていましたが、これだと少し荒かったので『機種のOSごとにversionがあるからそれをOSごとのリリース順に並び替える関数を作ってほしい』、『携帯の機種名ごとにメーカーっぽさがあるのでシリーズの番号を消して欲しい』くらいの細かさまで落としてリクエストしたところ良い感じに特徴量を作ってもらえました(前者の特徴は効いて後者の特徴は効かなかった)。

Wenyan氏にはこれに加えターゲットエンコーディング*5の実装でモデルの精度に貢献していただきました。結果このターゲットエンコーディングが特徴量の中で一番feature_importanceが高かったです。

また、Sunny氏には作った特徴量をモデルに追加してどうなったかの管理とモデルのハイパーパラメータのチューニングを行っていただきました。彼はpandasの経験自体も浅くLightGBMもその日にDLしていたはずだったのですが、自分たちの作った特徴量に合わせてパラメータをどんどんよくしていただきました(肩にOptuna乗ってんのかい！)。

こうして二人に役割を分担していただいた*6ので、自分はメタデータからの特徴量生成に集中することができました。モデルの詳しいfeature importanceは確認していなかったのですが

• 記事のジャンルごとに読んだ回数をカウントし、読んだ回数の多い順にTOP3を並べた特徴量*7
• 記事×キーワード・トピックで作ったスパース行列をSVDで100次元に落とした特徴量

を追加した時にスコアが良くなったので多分これらが効いたんだと思います。

結果

　PBは 33位/88チーム で、マスターの方々ややエキスパート同士で組んだチームに近づけました。おそらく自分一人でやるよりはいい成績が取れたと思うので勝ちだと思います。

チーム戦の楽しさ

　今回は自分の英語力のなさやマネジメント力・チーム経験の薄さから前半がグダグダでしたが、後半は30番台で追い抜き追い越しをやれたので(少なくとも自分は)だいぶ盛り上がれました。また、チームメイトに説明を行う中で自分の中での言語化されていなかったテクニックを再確認できたので学びもありました。一日で終わるにはもったいない、メダル付きで長期間開催してほしい良コンペだったので開催していただいたホストには感謝の気持ちでいっぱいです。

　チーム的には僕より強いMasterの方を入れて実力勾配を良い感じにしてほしいなぁと思うので、これが実現できるよう皆さんもオフラインコンペでは積極的に知らない人とチームを組みましょう。私は次のオフラインコンペでもチームを組む気でいます。

*1:日本経済新聞社さんは今回のコンペだけでなく競技プログラミングでもAtCoderで全国統一プログラミング王を主催するなどもしていただいている素晴らしい会社です。今週末(12/15)にもAtCoderでコンテストがあります。本当にありがたいです

*2:のちにホスト側から説明の入ったexcelファイルが共有されました

*3:user_idもうっかり混入していました

*4:チョットデキルではないほう

*5:1日目のJackさんの発表から会場で関心が高かったです

*6:やや面倒を押し付けてしまった感もあるので申し訳なさもあります

*7:1日目のonoderaさんの発表を参考にしました

院転して入学した大学院を中退しました

退学 Advent Calendar 2019 三日目に記事を書くnadareです。

私は東北大学薬学部を卒業した後大阪大学大学院薬学研究科に院転し、今年の秋に中退をしました。

中退した当時はもっと恨みつらみを退学アドカレに書いてやろうかと思っていたのですが、中退後の環境に恵まれ自身の中でいい感じに思いが風化してきたので軽い経過報告に留めたいと思います。

なぜ院転したのか

　大学入学時から情報系と薬学部で迷っていたのですが、入って半年くらいで薬学部を選んでしまったことに後悔し、学部二年の頃には大学院で他所の研究科に移ることを考えていました。二年の終わりごろからプログラミングを勉強し機械学習の研究がしたいと思うようになったものの、東北大学の薬学部には計算機を使って創薬を行うin silico系の研究室がなかったので、同じ旧帝の薬学研究科で情報系の研究を幅広く扱っている(らしい)大阪大学の研究室に院転しました。

なぜ中退したのか～中退まで

　マイルドに言えば空気が合いませんでした。研究に比較的熱心な人もいたものの研究よりも*1薬剤師の資格習得やサークル活動を優先したい学生の方が多く、やりたかった機械学習分野についてはあまり研究室で得られる指導もリソースもありませんでした。

　このままでは自分がダメになってしまうと思った私は大学院に入って半年くらいで研究室に見切りをつけ、kaggleやSIGNATE、AtCoderで腕を磨いていました。幸いそれなりに好成績を残せていたものの、段々「自分は研究をサボって時間を得ているだけ」と自己肯定感を得られなくなっていってしまい、今年の五月ごろにはkaggleのサイトを開くだけで辛く身体も動かなくなってダメになりました。研究科の相談室や大学のカウンセリングも利用したのですが、一時の気休め程度にしかなりませんでした。

　辛さを眠りでごまかし何か用事がある日以外は布団にこもってダラダラするだけの日々を過ごしていたのですが、*2心療内科を受診して気分安定剤を少量頂いたところスッキリして不安も抑えられるようになり、他にもいろいろな支えがあって中退までたどりつけました。現在は東京に引っ越し入社まで内定先でアルバイトをして暮らしています。

おわりに

　大学院はわりと散々でしたが、競技プログラミングを通じて色々な人に出会い中退まで助けて貰ってきました。やっぱり中退したことは辛いですが、大学院で得られなかったもの以上のものを社会人になった後に得られるといいなぁと思います。

*1:薬学部の一部の学生は六年生に進み研究室と並行して実習を受けます

*2:予約したら一週間以内に受診できました。頂いたお薬は薬価も安く費用対効果が抜群だったので本当にダメになる前に気軽に受診するといい気がします

ゆるふわ競技プログラミングオンサイト at FORCIA #2 ゴリラの挑戦状 に参加しました

A-H の8完1:35分で表示上は22位(時間的には25位)でした。

各問題の感想と全体の感想を書いていきます。

問題のリンクはこちらです→ https://www.hackerrank.com/contests/yfkpo2/challenges

C - mosaic tile art

これは

□■■　■□■　■■□

をどう並べるか、みたいのをイメージして解きました。

ちょっと視点を変えるパズルみたいでこの難易度帯の中では好きです。

D - n-dwich box

最初は"||"でsplitすることを考えましたが、1-ドイッチの"|"が消滅するので左から順に舐めました。

S = input()
ans = []
cnt = 1
for i in range(len(S)-1):
    if S[i] == "#":
        cnt += 1
    elif S[i] == S[i+1] == "|":
        ans.append(cnt)
        cnt = 1
ans.append(cnt)
print(*ans)

E - usagi vs kame

制約を見てクエリがソート済みだったので、クエリがくる毎にそれまで動いたうさぎの距離を計算しました。

# list末尾からのpopはO(1)なので逆に並べなおす
S = list(accumulate(A))[::-1]
B = B[::-1]
usagi = 0

for q in Q:
    while len(S) and q >= S[-1]:  # len(S) == 0の時、and以降は評価されない
        usagi += B.pop()
        S.pop()
    # 結果を出力(省略)

F- mneme game

にぶたんで解きました。Python使う人は https://docs.python.org/ja/3/library/bisect.html#searching-sorted-lists を見ながらbisect, bisect_leftの使い分けを考えるとよいです。

B = [i*(i+1)//2 for i in range(N+1)]

for q in Q:
    b = B[bisect_left(B, q)-1]
    print(S[q-b-1])

G - double range cards

被さっているところは二回反転させれば操作していないのと同じなので、AとBでそれぞれ反転させました。

二次元累積和の良い典型問題だったと思います。

from itertools import accumulate
from bisect import bisect_left
def inpl(): return list(map(int, input().split()))

R, C = inpl()
V = [inpl() for _ in range(R)]

Q = int(input())
G = [[0]*(C+1) for _ in range(R+1)]

for _ in range(Q):
    a, b, c, d, e, f, g, h = [i-1 for i in inpl()]
    G[a][c] += 1
    G[a][d+1] -= 1
    G[b+1][c] -= 1
    G[b+1][d+1] += 1
    
    G[e][g] += 1
    G[e][h+1] -= 1
    G[f+1][g] -= 1
    G[f+1][h+1] += 1

G = [list(accumulate(G[i])) for i in range(R+1)]

for j in range(C+1):
    for i in range(1, R+1):
        G[i][j] += G[i-1][j]

ans = 0
for i in range(R):
    for j in range(C):
        ans += V[i][j] * (G[i][j]%2)

print(ans)

H - double range cards

ゲームDPですが、N=10でとりうる状態数が十分に小さいので状態をまとめなくても解けます。

ゲームDPに関してはこの解説が好きです。

実装のコツとしては、座標(a, b)からマンハッタン距離mで行ける座標をD[a][b][m] = [(c1, d1), (c2, d2)]のような形で先に列挙しておくと楽です。

# -*- coding: utf-8 -*-
from collections import defaultdict

def inpl(): return list(map(int, input().split()))

N = int(input())
D = defaultdict(list)  # Pythonだと多重リストよりタプルをキーにした辞書の方がアクセスが早い

for a in range(5):
    for b in range(5):
        for c in range(5):
            for d in range(5):
                D[(a, b, abs(a-c)+abs(b-d))].append((c, d))

G = [[0]*5 for _ in range(5)]
for i in range(5):
    row = input()
    if "G" in row:
        gx = row.index("G")
        gy = i
    for j in range(5):
        G[i][j] = int(row[j] == "B")

C = inpl()

def game(i, px, py, G):
    global C
    res = []
    G[py][px] = 0
    if i < N:
        for qx, qy in D[(px, py, C[i])]:
            if G[qy][qx]:
                res.append(game(i+1, qx, qy, G))
    G[py][px] = 1  # Gが参照渡し?なのでここで修正しておく
    if i%2 in res:
        return i%2
    else:
        return (i%2)^1

if game(0, gx, gy, G):
    print("uho")
else:
    print("gori")

I - pino assort

本番中に実装が間に合わなかった問題です。 制約をよく見ると

すべてのiについて、v_i, a_i, c_i のうち少なくとも2つが1である

と書いてあるのが重要で、それぞれの味を好む三種類の社員に分類して貪欲で行けます。

解説では箱の数でにぶたんをしていましたが、箱の数は最大でも15*10⁵を越えないので累積和を使って計算しました。

詰まったところとして、1 1 1の社員をバニラ味に振ると1 1 1だらけのケースで少なく見積もってしまったのでアーモンドかチョコ味に振りました。

from itertools import accumulate
from bisect import bisect_left
def inpl(): return list(map(int, input().split()))

N, K = inpl()
V = []
A = []
C = []

for _ in range(N):
    v, a, c = inpl()
    if v > 1:
        V.append(v-1)
    elif c > 1:
        C.append(c-1)
    else:
        A.append(a-1)

V = sorted(V)
A = sorted(A)
C = sorted(C)

v = K*1
a = K*1
c = K*1

VV = [0]*(15*10**5)
AA = [0]*(15*10**5)
CC = [0]*(15*10**5)

for i in range(len(V)):
    v += V[i]
    VV[-(-v//10)] += 1
VV = list(accumulate(VV))

for i in range(len(A)):
    a += A[i]
    AA[-(-a//7)] += 1
AA = list(accumulate(AA))

for i in range(len(C)):
    c += C[i]
    CC[-(-c//7)] += 1
CC = list(accumulate(CC))

for i in range(len(VV)):
    if VV[i] + AA[i] + CC[i] >= K:
        print(i)
        break

全体的な感想

良質な典型問題で、前半部分もスピードランとして楽しめました。

12問出題してなにもトラブルなかったのすごくないですか？
しかもオンサイトオンラインともに全完が1人ずつで、幅広い人が2時間フルに参加できたのは満足度が高かったのかなーと思ってます#ゆるふわオンサイト

— prd🦍 (@prd_xxx) September 14, 2019

本当にこれで凄いと思いました。

ただ、J以降もノーヒントで解いてみたかったので、もう一時間あれば……いやオンサイト1位が残り10分くらいで全完したらしいので要精進ですね。

懇親会

ピザをたくさん食べれて嬉しかったです

ICPC国内予選参加記(コーチ編)

ICPC2019国内予選にコーチのお手伝いとして参加しました。 正確に言うと阪大の7チームのコーチは全てふるやんくんで登録していましたが、自分もいろいろ手伝ったりしていました。 選手側とは違う視点で、コーチ側の反省をまとめたいと思います。

当日参加していたコーチについて

• 学生で参加していたのは、私とふるやん氏とHidari氏の三人。三人とも普段からAtCoderに参加していて、私とふるやん氏は去年のICPCで同じチームを組んでいた
• 阪大7チームのコーチは全てふるやん氏で登録していたが、出場資格のなくなった学生もslack上で実況したりサポートに回ったりわいわいしていた

当日の役割分担について

• ミーティングルームに参加者7チームと試験監督・コーチがいて、私とHidari氏の二人は隣接する渡辺研のコピー機の前で待機していた。
• 各チームが印刷したことをコーチのふるやん氏に伝え、ふるやん氏がslackのコーチ用のチャンネルでどこのチームが印刷したかを伝えていた。

印刷のルールについて

• 試験開始時に各チーム一斉に問題ページを印刷した
• 問題文の印刷は全チーム片面印刷で統一し、最初の一部が届くまで二部以降の印刷を禁止した
• 問題文印刷時のみ、運搬係は7チーム分が揃ってから運んだ
• プリンターは基本的に全チームで一台を使用した

反省点について

模擬国内

• 紙の入れ過ぎによる紙詰まりで印刷が一時的にストップした
• 問題文が片面印刷と両面印刷が混じっていてた
• 最後の一枚を抜かしたままコードの印刷物を渡してしまった(枚数チェック)
• コーチの人員のバランスは問題なかった

国内予選

• 問題文が白黒とカラーで混ざっていた
• コーチ側のwifiが数分切れるアクシデントがあった(参加者側への影響はなし？)
• 活動記録として試験の様子を写真に撮っておきたかった

おわりに

またなにか思い出したら追記します。