penguin46の精進記録

気まぐれで何かを書きます

Kaggle Grandmasterになるまでを振り返ってみる

0. はじめに

penguin46といいます。大阪の公立大学に所属しているM2の大学院生です。先日のUSPTOコンペでGrandmasterに昇格したので、これまでのKaggle生活を振り返ってみます！


1. Kaggleを始めるまで

Kaggleに参加し始めたのは学部2年の冬からで、それまでは2年弱の間競プロerをしていました。
penguin46.hatenablog.com


AtCoderで目標としていたレーティングを達成した後、次にやりたいことを探していました。当時から機械学習が流行っていて、競プロと近い雰囲気もあったので、「なんか楽しそう！」くらいのノリでKaggleを始めてみました。

Kaggleを始める前はまさかGMまで到達でいるなんて思っておらず、在学中にメダルを取れたらいいなぁくらいに思っていた気がします。

2. 参加コンペの振り返り

最初は競プロで学んだ知識が活かせそうなコンペに参加していき、段々と機械学習要素の強いコンペにも挑戦するようになりました。以下、参加したコンペを順番に振り返っていきます。

GMになるまでに獲得したメダル（銀メダル以上のみ）

Indoor Location & Navigation（indoorコンペ）

解法

ショッピングモールの中で、センサデータから位置推定をするコンペでした。人間が歩行したルートを推定するので、フロアマップを活用して推定結果が障害物の中に入らないようにしたり、通路の形状に合わせて推定結果を移動・回転・スケーリングしたりといった後処理が有効なコンペでした。

中盤くらいからコッコさん、ころんびあさん、tuboさんとチームマージしていただきました。機械学習についてはコンペ開始前にKaggle本を流し読みした程度で何もわからなかったので、自分は他のチームメイトが機械学習で位置推定をしてくれた座標に対して、上記のような後処理を作っていました。

緑の経路を赤に後処理

機械学習何もわからないながらも、チームメイトがどんな風にモデルを改善してるのかを眺めれたり、後処理でわいわいアイデアを出しあったりして凄く楽しかったです。振り返ってもこのコンペが1番楽しかったかもしれないです。

Google Smartphone Decimeter Challenge (outdoorコンペ)

解法

アメリカの道路を走る車の中に設置されたスマートフォンが受信する衛星信号から、位置推定をするコンペでした。indoorコンペの屋外版みたいだったので、outdoorコンペと呼ばれていました。

indoorコンペに引き続き、序盤からころんびあさんとtuboさんとチームを組みました。indoorコンペで後処理が効いたのもあり、序盤から3人でホストから提供されたベースラインの推定結果に対する後処理ばかりを作っていました。ハンマーを持つとなんとやらってやつですね。。

結果的には衛星測位をしっかり実装した方が圧倒的に伸び代が大きく、殆ど後処理しかしてなかった自分たちは終盤で伸び悩んでしまいました。その後、SaitoさんとChrisさんにチームマージしていただけて金メダルが取れたのですが、金メダルに見合った貢献は全くできておらず、すごく悔しかったです。

NFL Health & Safety - Helmet Assignment (NFL2コンペ)

アメリカンフットボールの試合動画で選手識別をするコンペでした。選手のフィールド座標や試合動画が与えられるので、「試合動画での選手の物体検出→フィールド座標とのマッチングで選手を割り当てる」というアプローチを取りました。

中盤くらいにtkとチームマージをし、終盤にAriyasuさんにチームマージしていただきました。特にチームマージ後は、マッチングのパートをメインに取り組んでいました。結果は金圏の1つ下という結果で悔しかったです。

Kaggle休止期間（B3冬~B4秋）

この時期は主にAtCoder Heuristic Contest (AHC)をやったりしていました。ここまで参加したコンペの3つ中2つでヒューリスティック最適化を上手く使えなかったり、他のKagglerが持ってない武器を作りたかったのがAHCを始めた理由でした。そんなに長い期間やるつもりはなかったのですが、思いの外楽しくて気がついたら結構な期間になってました。

AHCで黄色になり、ある程度ヒューリスティック最適化に詳しくなれたのはよかったです。あまり多くのKagglerが持っている知識ではありませんが、Kaggleでも比較的よく使えるイメージがあります。後のBenetechコンペやUSPTOコンペで活かせました。

1st and Future - Player Contact Detection (NFL3コンペ)

解法
アメリカンフットボールの試合動画で、選手同士や選手とグラウンド間の衝突を検出するコンペでした。試合動画とテーブルデータ(選手の座標、速度、体の向き等)が与えられました。動画データで衝突検出する1st stageと、1st stageの予測値とテーブルデータから生成した特徴量からGBDTで最終予測を作る2nd stageの２つに分けて取り組みました。

中盤にtkとチームマージし、主にtkが1st stage、私が2nd stageを担当していました。終盤にQishen Haのチームからお誘いいただき4人チームになり、最終的に6位でコンペを終えました。私以外の3人は画像コンペがめちゃくちゃ強く、本当にいろんなことを教わりました。

PC購入

ここまではGoogle Colabを使っていたのですが、出てくるGPUや使える時間が制限されるようになったのがきっかけで、RTX4090を購入しました。学生なので50万円前後の出費は結構痛いのですが、「いつか賞金取れば実質無料！」と思って先行投資しました。計算リソースを言い訳にできなくなったので、ソロ金を取らないとなぁという気持ちにもなりました。

Benetech - Making Graphs Accessible

解法
グラフ画像(散布図や棒グラフ等)に含まれるデータを、テーブル形式に抽出するコンペでした。基本的にはTransformerベースのVision2Languageモデルが強く、画像を入力として"x1 y1 x2 y2…"といった形式でテキストを生成する解法が使われていました。散布図に関してはデータ点が多すぎたり事前学習が弱かったりといった理由で、物体検出を使った解法を取るチームもありました。

publicで金圏に残れそうだったのもあり、最後までソロでやりきったのですが、結果は14位で銀メダルでした。上位の解法と比べると、物体検出周りの基本的な知識が足りていなかったりと勉強不足な部分が目立ち、もっと過去コンペをしっかり勉強しようという気持ちになりました。

Child Mind Institute - Detect Sleep States (睡眠コンペ)

解法

被験者の腕に装着されたセンサデータから、睡眠の開始時刻と終了時刻を予測するコンペでした。系列をTransformer等のモデルに入力して、Seq2Seqで一定ステップ毎の出力を得た後、評価指標に合わせた後処理をするというアプローチを取りました。

IndoorコンペでNNパートを全くできていなかったので、そのリベンジも兼ねて参加したのですが、NNに対する特徴量生成の肌感を少し掴めたり、基本的な時系列モデルを使えるようになれたのがよかったです。残り3週間で順位の近かったNikhilとチームマージして、4位で終了しました。日本人参加者も多く、TLがワイワイしてて楽しかったです。

BirdCLEF 2024 (鳥コンペ)

解法

自然の中で録音された音声データから、鳥の鳴き声を検出するコンペでした。音声データは触ったことがありませんでしたが、この時期コンペが少なくて手持ち無沙汰だったので、折角ならと来る鳥コンペに備えて1か月くらいゆっくり過去コンペを勉強していました。

鳥コンペは毎年タスクがほぼ同じなので、新しい強力な手法が出てくることはそうそうないはずだし、もしあっても数チームしか思いつけないはずと考えました。そこで、まずは過去コンペでよく使われた手法を試し、最後にいくつかの今回のコンペ特有の工夫を加えました。

このコンペは過去コンペと同様にCVとLBが殆ど相関せず、public LBを信じるしかないコンペでした。データサイズの小さなpublic LBで細かいチューニングをするとLBに過学習してしまう可能性があったので、重要な実験を一通り終えたら、解法をシンプルに保ったまま余計なことをしないように次のコンペ（USPTO）に取り組み始めました。結果は6位でソロでの金メダルを獲得できました。

USPTO - Explainable AI for Patent Professionals

解法

アメリカの特許データ約1300万件から、指定された50件のみをヒットさせるようなブーリアンクエリ(トークンをANDやORで繋げたもの)を構築するコンペでした。Kaggleではなるべく最適化コンペに参加することを避けていたのですが、あまりにも面白そうなタスクだったので参加しました。

このコンペでは評価プログラムの欠陥を突いたmagicが有効でした。クエリには「トークン数が50以下かつクエリ全体で1万字以下」という制約あるのですが、ANDで繋ぐトークン間に適当な記号を挟むとトークンの句切れが正確に検出されず、1トークンでほぼ無制限の単語数を繋げられるというものでした。例えば、token1 token2 token3というクエリは3トークンを消費してtoken1 AND token2 AND token3という意味を表すのですが、"token1""token2""token3"とすると同じ意味のままトークン数を1にできます。

私がこのmagicに気がついたのはコンペ終了10日前でした。当時の私のスコアは0.91だったのですが、数日前に突然0.99を出す人が出たり、突然0.87くらいから0.92あたりまでジャンプしたチームがあったことがきっかけで、このmagicに気がつきました。「こんな解釈性のカケラもないmagicが本当に許されるのか？？explainable AIってなんだっけ？？」と思いながら、なんとかスコアを0.98まで上げ、4位でコンペを終えました。競ってるつもりだった殆どのチームに負けてしまったのですごく悔しいですが、最終盤にLB見て後追いしてる時点でダメだったなと反省しています。スコアを隠されていたらもっと酷い負け方をしてたはずですし、自分で気がつけないといけなかったです。

3. コンペで大事にしてること

以下、私がコンペに参加している時の取り組み方や、気をつけていることなどを列挙します。

コンペ選び

  • must
    • リークがなさそう
      • リークは最終盤に見つかることが多い気がするので避けれるかは不明
      • 最低限、合成データは避ける
      • metricが複雑なコンペも非本質なhackがありがちな気がする。（睡眠、Prompt Recovery, USPTOなど）
    • 運要素での揺れがなさそう
      • 上ブレで金メダル取っても嬉しくないし、負けた時に言い訳する余地が残るのもいや。
      • cvかpublicの少なくとも一方が信頼できる
    • タスク自体が面白い
  • want
    • 少し変わったコンペ
      • indoor, NFL, Benetech, USPTOみたいなコンペです。みんな違った解法をしていて楽しいから好きです。
    • やったことないドメインのコンペ
      • ドメインを絞ると参加できるコンペが少なくて楽しくないのと、単にやったことないことをやるのが好きです。
    • 観測フェイズなし
    • ドメイン知識が重すぎない
    • 外部データがいらない

立ち回り

  • 序盤（開始~1か月）
    • 序盤から参加する
    • いい感じの順位を維持することでモチベを保つ
    • ベースラインを作り、データと評価指標を理解する
    • 必要ならCVの計算方法を決め、何を見て精度を評価するかを確定させる
    • ドメイン知識や先行研究、外部データがないかを捜す
    • 色んな手法でベースラインを作ってみる
    • 過去コンペで使われてる手法を試していく
  • 中盤
    • 最終的にスコアが一番出そうな解法を深堀する
    • スコアが大きく伸びるアイデアだけ採用していく。
      • 微改善で実験サイクルが悪くなったりコードが汚くなるアイデアはメモしておいて終盤に試す
  • 終盤
    • コンペによるが、とにかく最終のLBが一番高くなりそうな立ち回りをする。
      • アンサンブル、チューニング、寄与の小さな特徴量の追加など
    • 過去の日記やdiscussion見たりして、思いついたアイデアは全部試す。

実験管理

この辺あまり行儀が良くない自信があります。そろそろ見直したいです。

  • コード管理
    • Gitを使って常にベストスコアのコードをメインブランチにする
    • 大きな変更をするならブランチを切る。改善したらマージ
  • notebook派
    • ログを簡単に残せるのと、エラーが起きた時とか実行後に変数が消えないのが助かる
    • notebookが肥大化しないように適宜pyに移せるコードは移す
  • ディレクトリ構造
    • Dockerを使って出来るだけ提出環境と揃える。提出時にデータセットのパスとか修正しなくていいので楽
  • notionで考察メモを書く
    • データベースとかは使わない。見た目はスッキリするけど、情報が複数ページに分散するのが苦手なのと行き来が面倒。
    • 「日記」、「最後忘れないこと」、の二つだけページを作る。
    • 思考の過程や結果などほぼ全てを記録。コンペ後に立ち回り等をふりかえる

その他大事だと思うこと

特に以下は人によって意見が違う点もあるはずです。あくまで私が参加するときに意識している(いた)ことです。

  • チームでいいからとにかく一回金メダルを取る
    • 強いチームがどんな風にスコアを伸ばしているのかをそばで観察できるのは貴重です。
    • 特に、2つ以上の要素が重要なコンペで、自分のパートで貢献しながらチームメイトから別パートを学べると凄く良いです。
  • コンペ仲間を作る
    • わからないことがあったときに気楽に質問できたり、議論できます
    • Kaggleの学生コミュニティとかもあるらしい？
  • 過去に類似コンペがあった場合、過去コンペを勉強する
    • 金圏に入るには「上位が全員やってること」＋「コンペ独自の工夫」が必要なことが殆どな印象です。
    • 前者の殆どは過去コンペで使われているので、過去コンペを勉強するのが効率いい
  • データの生成方法やテストデータの作り方をよく調べる
    • ホストが過去に出している論文や、githubリポジトリがないか等も調べます。
    • データの理解にも繋がりますし、生成過程で重要な特徴が出現する場合もあります。
    • コンペ期間のホストの対応に違和感を感じたら、テストデータも可能な範囲でprobingします。
  • 雑に実験しない
    • スコアが上がらなかったとき、雑な考察をして終わらせない
    • 可能なら追加の実験をして修正後の考察が正しいかまで確認する
  • うまくいく自信があるアイデアを諦めない
    • 序盤からずっと「これができたらめっちゃスコア伸びるだろうけど難しすぎるなぁ」と悩んでたアイデアの解決方法を、終盤になって突然閃くということがほぼ毎回ありました。
    • 一度諦めた実験も、うまくいかない理由がはっきりするまでは何度か考察や実験をやり直すようにしています。
  • とにかくコンペに参加する
    • コンペで必要なことはコンペ中に勉強する。
    • 実力不足で途中撤退して出直すくらいならそのコンペで実験して少しでもスコアを伸ばす。（辛いからやめたいのか、本当に撤退したほうが良いのかを考える。）
  • 楽しむ
    • 結局これが一番大事だと思ってます。
    • Kaggleの称号はメダルが複数枚必要で長期戦になるので、モチベが続くことを最優先にしています。
    • 例えば、コンペ外で過去コンペのsolutionを読み漁ったり、late subをするのは学習効果が高いと思いますが、自分はモチベ的に辛いので殆どできてないです。（solutionはやったことないゲームの攻略本を読んでるみたいで個人的に楽しくないのと、過去コンペにsubするなら現行コンペをやりたいです。参加記とかは読んでて楽しいです。）

4. 最後に

Grandmasterまで到達できたのは、本当に界隈のみなさんのおかげです。ありがとうございました！

振り返ると、初めて参加したコンペが偶然競プロ的な後処理が効いたり、ワイワイできるコンペ仲間に出会えてKaggleにハマるきっかけを得たり、つよつよなチームメイトや界隈から多くを学べたり、近いモチベーションを持った大学同期と沢山議論できたりと、すごく恵まれていたなと思います。

あと、この記事を書くにあたって自分の過去ツイを遡ったのですが、indoorからoutdoorあたりのツイートを見るとめちゃくちゃ楽しそうにコンペしてて、「なんか中の人変わってるなぁ」とか、「また日本人とチームを組んでワイワイしたいなぁ」とか思いました。自分にとってKaggleはあくまでも趣味ですし、これからも楽しさも忘れないようにしたいです。

長くなりましたが、ここまで読んでくださりありがとうございました！少なくとも学生の間は今までと同じようなペースで参加するつもりなので、またどこかのLBで会いましょう！！

AtCoder Heauristic Cotest 014 解説(9位)

日記はこちらです↓
penguin46.hatenablog.com

結果

pretest 、システムテストともに9位

問題概要

atcoder.jp

格子点上に頂点を1つ追加して軸に平行or45度傾いた長方形を作ることを沢山繰り返してください。既存の頂点を通ったり、辺を共有するような長方形は追加できません。

seed1, 1.48M点

解法

一部の長方形を削除して貪欲で再構築する焼きなましをしました。長方形を削除すると宙ぶらりんになる長方形が生まれるので、それらも削除します。*1

長方形の全列挙

各頂点から8方向に線形探索し、直角な2方向で別の頂点に到達したら、その3点を使う長方形が作成可能かを判定することで全列挙します*2。長方形を追加すると、新たに作成可能になる長方形が生まれるので、追加した頂点を使う長方形を同様の方法で探します。ちなみに作成不可能になる長方形も生まれますが、この判定は必ずしも必要ではないので、評価値が高く使用したくなった時に遅延評価するようにしています。

貪欲パート

作成可能な長方形をから、評価値が高いものから使用していきます。使用する評価関数は1回の貪欲につき下記の2つの内1つをランダムに選択します。テストケースによって長方形の大きさや頂点の密度が大きく異なるので、評価値はタプルで持ちました。前の要素の値が大きいほど評価が高いです。

  1. （4頂点の次数の和, 追加する頂点の重み)
  2. （-長方形の外周の長さ, 4頂点の次数の和）

次数の和：1つの頂点が複数の長方形に含まれてほしいお気持ちです
外周の長さ：外周が長いと長方形を追加する際の邪魔になるので短くしたいお気持ちです
頂点の重み：場合によっては次数とか外周を捨ててスコアを稼いでほしいお気持ちです

焼きなましパート

以下の4つの近傍を作成しました。いずれも連鎖的に削除された結果、状態が大きく変化してしまう場合があります。大きな近傍はacceptされにくいので、削除された長方形の割合と同じ確率でその削除を拒否し、貪欲を走らせずに状態を復元するようにしました。

  1. ランダムに長方形を削除。追加する頂点の重みと残り時間に比例した確率で長方形を削除
  2. ランダムな直線を1本引いて、外側にある長方形をすべて削除
  3. ランダムな点を選び、距離が一定値以下の範囲に含まれる長方形を削除
  4. 最終的に出力する答えから、インデックスがランダムな範囲にある長方形を削除します。

その他・感想

ビームサーチやバックトラッキングするDFSも試しましたが、スコアは伸びなかったです*3。焼きなましで長方形を削除しすぎていてほぼ貪欲になっていることに中盤まで気が付かなかったりしたりするなど*4、スコアが上がってもプログラムが想像通りの挙動になっているかを確認してギャップを埋めていくのは大事だと思いました。あと、AHCではテストケースを無限に生成すればハイパーパラメータに過剰適合することを簡単に避けられるので、Optunaなどを使ってきちんとチューニングすることも大事でした。他の70M台の方たちが何をしてるのか全く想像がついていないので、感想戦を楽しみにしています。

*1:実装では、削除前の長方形を前から順番に追加しながら、削除する長方形と作成不可能な長方形をスキップしました。この時、辺の重なりとかは気にしなくてよく、頂点が存在するかだけ調べればよいです。

*2:他にも「各方向に探索した時に最初に見つかる頂点」をメモ化したり、直線ごとに頂点の座標をheapqueuで管理したりしましたが、却って遅くなりました。恐らく、殆どの長方形はサイズが1x1などと小さいので線形探索が想像より高速なのかと思います。

*3:原因は同じ状態に到達するまでの経路が多すぎるためだと考察しています。試しにタブーリストを持ちながらバックトラッキングすると、若干（pretest換算で1.5M程度）はよくなりました。

*4:これに気づいて諸々の失敗した実験をやり直すと54M→65Mくらいまで上がりました

AtCoder Heuristic Contest 014 参加記

参加中に書いていた日記です。殆どコピペなので長いです。解説記事は追って書こうと思います。
内容を整理した解説記事はこちらです↓
penguin46.hatenablog.com

(https://iilj.github.io/AtCoderMarathonReplay)
(https://iilj.github.io/AtCoderMarathonReplay)

9/17（土）

  • ルールを確認した。
  • 頂点を増やしてスコアが下がることはない。
  • 同じ頂点を追加しても長方形は一つに決めらないから他の3点も出力するのか。
  • 操作の順序が影響する。
    • 最終的にはビームサーチか、AHC013みたいな焼きなましになる？
    • まあとりあえず貪欲だよな。
  • AHC013みたいな焼きなましが出来る？
  • 大きな長方形を作ってしまうと、その辺上が重なれなくなって状態が悪くなってしまいそう。
  • 何も出力しなければ、50ケース 13.8Mくらい。
  • いろんな場所から作り始めちゃうとかみ合わせが悪くなりそうなので、BFSっぽくやってみるか。
    • 追加した長方形の近くの頂点をqueueに入れて、取り出した時に周辺の長方形を探した。[localの50ケース 28M]
    • BFSだから見つかった順の貪欲になってるけど、他にもいろんなやり方がありそう。
      • 最大クラスタを拡張していく
      • 長方形が小さいものから置いていく
      • 隣接する頂点が多いものから置いていく
  • クラスタを大きくしていってもどこかで別の長方形を追加しないといけない。
    • その時のかみ合わせはどうやって調整するんだ？？
  • 完全になんもわからんだな。

9/18（日）

  • とりあえず小さな長方形から順番に作っていくか。
    • 大きさ1x1の長方形を追加→1x2の長方形を追加→...。[100case: 37M]
    • 長方形の列挙が雑で70回くらいしか最後まで到達してないな。
  • BFSの挙動がそれっぽかったので、同じサイズなら早く見つけた方を優先するか [100case: 38M]
  • 小さな長方形から作るのは正しいと思うんだよな。
    • 辺が共有できなくて使える辺の長さの総和が決まってるので、沢山頂点を増やしたければ小さな長方形じゃないといけない。
  • 可視化してみたけど、最初から用意されてる頂点はほぼ使い切れてる。
    • 連鎖的に頂点を追加していけるようにしたいが。
  • スコアが中心からのユークリッド距離の二乗なので、個数を増やすより外側に置く方法を考えた方が良い？
  • 長方形の列挙はO(K)でできるな。
    • 各頂点について8方向を線形探索して、角度が90度な2つを使った3点で長方形を確定させて、違反してないか確認すればいい。
    • 線形探索は重そうなので、直線ごとに二分探索すると良さそう。

9/19 (月・祝)

  • 上の全列挙をやった。[LB 40M]
    • まだ二分探索にしてないけど、プロファイラを見る感じ問題なさげなので後回し。
  • 簡単にビームサーチにしてみるか。
    • スコアを評価値にしたらスコアが下がった。
    • 先を見越した評価値を作るのが難しいな
      • 他のクラスタとかみ合うかどうかを評価するの、かなり難しそう。
      • 絶対かみ合うようなパターンを用意してもいい？
        • 見つからない。
  • アルゴ緑～水でも45M出してる人がいるな。
    • 天才パズルだったりするのかな
  • これ、もしかして操作回数に上限がないか？
    • 各頂点は次数8で最大4つの長方形で使えるけど、1つ長方形を作ると8消費するので±0。
    • ということは次数を使い切れずに埋もれてしまった頂点が増えるほど苦しくなっていくのか。
    • 埋もれたかの判定をできれば評価値に使えそう。
      • この判定も難しいな。作成可能な長方形の中でその頂点を使っているものがあるかを見てもいいと思ったが、なんかいまいちな気がする。
    • 逆に上手く使い切った個数を数えるなら簡単か。
      • 「その長方形に含まれる頂点の次数の和」を評価値にした。[100case: 42.6M]
      • ビームサーチでも試したけど、相変わらずスコアが低いな。
  • AHC002のwalking on tilesみたいな感じで、追加できなくなったらバックトラッキングするのはどうかな。
    • 変わらないな。
    • これ、長方形を追加しても作成可能な長方形のリストへの影響が小さいから、実は順序性があんまり強くないんじゃないか？
      • 評価値の良い順にA, B, C, ...とあったとして、あえて先にBを使ってもその後にAを使われたら同じ状態になってしまう
      • いろんな方向でこれが起きたら同じ状態を違う経路で辿ってるだけだな。ビームサーチが上手くいかなかったのもこれが原因か。
    • なら、バックトラックするときに復元した次の長方形をブラックリストに入れてやると少しは軽減される？[100case: 43.5M]
    • ちょっと良くなった。このブラックリストを焼きなましたりするのはどうだ？
  • 外側に置いていく方針試せてないな。
    • なんかうまいこと先読みして外に置けないかな。
      • 「ここに置きたい」⇒「ここに置かないといけない」⇒「ここに置かないといけない」⇒「置けた！」みたいな。
    • 再帰で殴ればいけなくもないのか？
  • 根拠はないけど、天才焼きなましな気がするな。
  • とりあえず長方形列挙を高速化した。[LB: 46.1M]

9/20（火）～21（水）

  • 長方形列挙、直線ごとのリストでもって二分探索するやつやるか。
    • ほとんど変わらないな。8方向あるから定数倍が重いのかな。
  • twitterの900Kのseed0を見たけど、やっぱり頂点数が圧倒的に少ないな。まだ頂点を増やすのが大事らしい。
  • 長方形列挙、差分計算できるじゃん。
    • 良さげ。ここらへんで1回提出するか。[LB: 47M]
  • 辺上に頂点を置くのはOKで、頂点上に辺を置くのはNGなので、先に大きな長方形を置いた方が良い？
    • 特に1x1の長方形があとから置けなくなることはない。
    • 依存関係がDAGになってるから、トポソすれば答えの順番はある程度弄れるのか。
      • 弄って何になるかはわかんないけど。
    • あれ、これ焼きなませるんじゃないか。
      • テキトーな長方形と、それらに依存している長方形を削除してから貪欲で作り直す。[LB: 50.7M, 100case: 51.3M]
        • ランダムな確率で長方形を削除した。
  • 焼きなましの近傍をもっと追加してみる？
    • ランダムな領域の長方形を削除する
    • 答えをシャッフルする
    • 連続したいくつかを削除する
    • 直線の外側を削除する
    • 全部上手くいかないな。なんでだろう。
  • GA使えないかな。
    • 別の解と良さげな部分をいいとこどりしたいお気持ち。
  • 貪欲の評価関数を次数重視とスコア重視でランダムにした。[LB: 51.1M, 100case: 53.0M, 1000case: 51.6M]

9/22（木）

  • 次数じゃなくて、隣接してる頂点の個数を使うとかは？
    • 上がらないなー。密じゃないケースもあるしそりゃそうか。
  • 諸々を高速化した。[LB: 53.8M, 1000case: 53.8M]
  • 焼きなましの経過を可視化したら、殆ど全部の長方形が消えてた。
    • 20%くらい捨てるだけで、殆ど全部の長方形が消えてる。
    • 確率を小さくして、さらに時間経過も小さくした [LB: 57.3M, 1000case: 56.9M]

9/23 （金・祝）

  • 少し前にやったこと、削除する確率が大きすぎて機能してなかっただけな説ある。やり直すか。
    • 焼きなましの近傍
      • 長方形を切り抜く [1Mくらい向上]
      • 直線の外側を消す [4Mくらい向上]
      • 外側を優先して消す [1.5Mくらい向上]
      • 連続したいくつかを削除 [ほぼ変化なし]
    • 焼きなましで一定回数改善されなければベストからやり直すやつ。[1Mくらい向上]
    • 貪欲の評価値
      • スコア重視の評価値 [悪化]
      • 評価値を見ないでランダムに詰める [悪化]
  • とりあえず一通りやり直せた。 [1000case: 64.7M]
  • スコアが改善されそうなところを集中的に破壊したいな。
    • 大きな長方形を優先的に削除するとか [悪化]
    • 次数が小さい長方形を優先的に削除するとか [悪化]
  • N, Mで結構スコアが変わるので、焼きなましの温度も調整した方が良い？
    • あんまりうまくいかないな。
  • 5倍の時間実行したら、100caseで70.3M出た。
    • 10倍実行したら72.3M。
    • 高速化頑張るか。。。。。

9/24（土）

  • 一部不要な判定を削除した 。[LB: 66.0M, 1000case: 64.7M]
  • なんもわからんな。あと一週間あるのやばすぎる。
  • 結構時間かかるしoptunaで焼きなましの温度チューニングして今日は別のことするか。

9/25（日）

  • 真心チューニングと全然違う温度だ。[LB 67.9M, 1000case: 67.0M]
  • なんもわからん。スプラ楽しい。
    • 結局研究とスプラしかしてないじゃん。土日。。。かえして。。。

9/26（月）

  • スプラ楽しい。

9/27（火）

  • 気合い入れるためにchokudaiさんの根性論の記事読み直すか。
  • 焼きなましのスコア遷移。赤は貪欲回しただけのやつ。
    • 密度が低いケースで結構な悪化がacceptされてるな。
      • 温度を下げたけどスコアは悪化したので、温度の問題ではなさそう。
      • 頂点が少ないから1つの頂点の重要度が高くて簡単にスコアが下がりやすいだけなのかも。
      • とりあえずここは問題なさそう。

  • 削除された長方形の個数と、スコアの悪化量の関係
    • 長方形が沢山消されると殆ど改善されてないな。
    • 多く消されると貪欲も時間がかかるし、捨ててしまってもいいかも。
      • 悪化した。大きな変化をする近傍は必要か。
    • でも割合は減らした方が良いよな。残り時間の割合より多ければ捨てた。[LB: 68.5M, 1000case: 68.1M]
      • 久しぶりの向上だ。。。！

9/28（水）

  • 長方形列挙、同じ線分を2回見てるから、配列にメモすれば2倍以上速くなる？
    • というか線形探索の結果も、「その方向に最初に見つかる頂点」を差分計算すればいいのか。
    • 悪化した。1x1とかの長方形が多いから効果ないのかも。
  • 1位が76Mとかだから、高速化以外の改善もあると思うんだけどな。

9/29（木）

  • なんもわからん。

9/30（金）

  • アイデアがないのでとにかくやってなかったこと全部やる。
  • 高速化
    • vectorを配列に変える。vectorをwith_capacityで初期化&使いまわす、不要な判定を消す [LB: 69.2M, 1000case: 68.7M]
  • ハイパラ全部まとめてチューニングする [LB: 70.3M, 1000case: 69.4M]

10/1（土）

  • 昨日の提出、温度を間違えてた。[LB: 70.6M, 1000case: 70.0M]
  • 今までやったこと見直すために、解説記事書いた。
  • 悪あがきしたけど特に成果なし。

2021年の振り返りと2022年の目標

はじめに

　年末なので、今年1年間の振り返りをして、来年の目標を立てようと思います。振り返りは具体的なsolutionとかは書かず、当時のお気持ちを思い出として残す感じにしようと思います。（なので特に有用なことはないと思います。）
f:id:penguin46:20211231105221p:plain

AtCoderで青色になる（~1/23）

　今年の初めに、AtCoderで目標にしてた青色になれました。この時の振り返りは以前別の記事にまとめました。色変したコンテストではA~E問題をまとめて提出したのですが、5問とも一発でAcceptedされ、脳汁ドパーだったのが一番記憶に残ってます。
f:id:penguin46:20211231073158p:plain
penguin46.hatenablog.com

Indoorコンペ参加（~5/17）

　競プロ以外にもいろんなことをしたいと思い、競プロを中断してKaggleを始めました。このコンペでの目標はとりあえずメダルを取ることだったのですが、序盤～中盤は本当になにもわからず、公開notebookを弄って銅と銀のボーダーくらいにいました。1か月くらいひたすらEDAをするも、独自のアイデアで精度を伸ばせておらず、辛すぎて撤退してしまいそうにもなりました。

　その数日後、ふと思いついたアイデアを試してみると50cmくらい精度が上がりました。やったことはパラメータを調整しながら後処理を繰り返しただけなのですが、順位が48→13位まで一気に上がって、競プロでACしたような嬉しさがありました。

　その後、コッコさん、tuboさん、ころんびあさんの3人とチームマージをしていただけることになり、4人で残り期間を走りました。3人が機械学習パートをやってくださり、僕はずっと後処理芸人をしていました。知識量に差がありすぎて、後処理でも貢献できなかったらどうしようと震えていたのですが、その後もいくつかのアイデアが当たってくれたのでなんとか耐えました。

　最終的にprivate 15位（銀メダル）でfinishしました。金メダルには届かなかったのですが、そばで皆さんがどんな風にモデルを作っているのかを勉強させていただき、とても貴重な機会をいただけたと思っています。Kaggleの楽しさを感じることができたコンペでした。

Outdoorコンペ参加（~8/4）

　Indoorが終わるとほぼ同時に位置推定コンペが来たので参加しました。序盤からIndoorでのチームメイトのtuboさんところんびあさんとマージしました。コンペ終盤にChrisさん、Saitoさんとチームマージをしていただき、private5位（金メダル）でfinishしました。

　序盤から衛星測位に取り組んではいたのですが上手くいかず、簡単に精度が伸びる後処理に多くの時間を使ってしまいました。蓋を開けてみればドメイン知識が非常に重要なコンペで、戦略を見誤ったことを反省しています。このようなよく研究されたタスクでは、一般的な手法をきちんと調査するべきでした。

　ころんびあさんが追実験をしてくださったのですが、ホストのベースラインに対して3人(penguin, ころんびあ, tubo)の後処理をしただけでは13位相当のスコアだったようです。私たちの後処理ではドメイン知識を一切用いず、kNNやLightGBMを使い機械学習ベースの外れ値判定などを実装したのですが、金圏のスコアを出すにはドメイン知識が必須でした。ChrisさんとSaitoさんのおこぼれで取れた金メダルでした。

NFLコンペ参加（~11/2）

　ラスト1か月で同級生のTK、ラスト2週間でAriyasuさんとチームマージをしていただき、private12位（銀メダル）でfinishしました。

　競プロで学んだAffine変換やハンガリアン法の知識があったので、序盤からラスト1か月まではソロで金圏上位に居座れたのですが、終盤アイデアが尽きて失速してしまいました。金メダルに届かなかった敗因は、機械学習の知識が乏しかったことと、スコアの評価が甘かったことだと思っています。特にスコアの評価に関しては、序盤から終盤までを通して、大量の実験をしたことで偶然CVが微増したアイデアをいくつか使ってしまったのがまずかったのだと考えています。（多重比較問題というらしい？）



休憩＆精進（~12/31）

　特に参加したいコンペがなかったので、一旦ペースを落としてゆっくり機械学習の勉強をしていました。次の本を読んだ後、過去コンペの勉強をしました。

  • Kaggleで勝つデータ分析の技術（読み直し）
  • Kaggle Grandmasterに学ぶ機械学習実線アプローチ
  • PyTorch実践入門（第1部のみ）
  • PyTorchによる発展ディープラーニング

　

振り返りまとめと来年の目標

　IndoorとNFLであと少し金メダルに届かなかったり、Outdoorでは(少なくとも金メダルを貰うに値するほどには)貢献できなかったなど、たくさん悔しい思いをし、反省しないといけないことばかりの1年間でした。
　それでも、AtCoderで青色になれたり、チームを組んでくださった皆さんのおかげでKaggle Masterになれたり、ころんびあさんやtuboさんとはコンペ後も数理最適化の輪読会をしたりと、沢山嬉しいことや楽しいことがありました。ありがとうございました！

　来年の予定ですが、諸事情で2月ごろまではまとまった時間が取れそうにないので、3月からKaggleに集中できるよう、それまではTOEIC、卒論、過去コンペの復習（直近2~3年分）に取り組もうと思います。来年の目標はKaggleで金メダルを2枚取ることです。来年もよろしくお願いします！

AtCoderで青色になったので2年間を振り返ってみた

はじめに

1/23のABC189で、青色になることができたので、例に倣って色変記事を書いてみました。少しでも誰かの参考になれば嬉しいです。


目次

  • AtCoderとは
  • 競技プログラミングを始めるまで
  • 茶色になるまで
  • 緑色になるまで
  • 水色になるまで
  • 青色になるまで
  • その他精進について
  • 終わりに

AtCoderとは

AtCoderはプログラミングコンテストを開催しているサイトです。ほぼ毎週コンテストが開催され、約1万人程度の参加者が参加します。問題が6問ほど出題されるので、データ構造やアルゴリズム、数学などを使って解法を考え、その解法を実現するプログラムを作成することで競います。

レートに応じて色が割り振られ、下から順に灰・茶・緑・水・青・黄・橙・赤となっています。各色の詳しい評価は下の記事に書かれています。
chokudai.hatenablog.com

競技プログラミングを始めるまで

某地方国公立大の電気情報系の学科に通っています。大学入学前はプログラムを書いたことも見たこともありませんでした。他の方の色変記事を見るに、恐らく青色になった人たちの中では平均～少し多いくらいの精進量だと思います。

大学が始まるまでの春休みにプログラミングを始めてみたいと思い、DXライブラリでSnakeや2048、テトリス等の簡単なゲームを作ってみました。プログラムのロジックを考えることや、計算した結果が画面に出力されることはとても楽しかったのですが、正直Unityなどで本格的にゲームを作ることには興味を感じられませんでした。

その後、同じ学科の友人に競技プログラミングに誘われて始めて見たところ、好みにドンピシャで、楽しすぎてやめられなくなってしまいました。

茶色になるまで(～1回生7月)

自分の書いたプログラムが動いて結果が出てくるのが楽しくて、ABCのA～B問題をたくさん解いていました。文字列の扱いにかなり苦戦していたのを覚えています。

ちなみに、初めて知ったアルゴリズムは累積和でした。友人に教えてもらい、すごく感動したのを覚えています。その他、灰色の間に勉強した内容は以下のものがありました。

配列 ソート 累積和 bit全探索 ナップサック問題 幅優先探索 深さ優先探索


茶色になるまでに解いた問題数です。(その他はdifficultyのついていない問題、CFはCodeforcesの略です。2021年1月25日時点の問題数を母数としているので、割合は当時のものではありません。)

diff 灰 茶 緑 水 青 黄↑ その他 CF 合計
AC数 217 11 5 2 0 0 9 0 244
割合 40% 6% 3% 1% 0% 0% - - -

緑色になるまで(～1回生10月)

コンピュータについて全く無知でしたので、情報の分野全体の広い知識が欲しくて、夏休みはIPAの応用情報技術者試験の勉強をしていました。AtCoderのおかげで、午後のプログラミングの問題がとても楽になりましたし、逆にこの資格の勉強のおかげでデータ構造の理解が進んだこともありました。

10月ごろ、他大学の競プロ仲間ができて、お互いに作問した問題を解き合ったりしていました。作問は理解が深まるので、とてもお勧めです。そこのメンバーが異常精進をして信じられない速さででレートを上げているのを見て、「強い人はこんなに精進しているのか！」と、とても良い刺激を貰いました。

この頃は基本的には灰～茶diffをひたすら埋めながら、時々蟻本初級編の類題を解いていました。
qiita.com

緑になるまでに勉強した内容とAC数は下の表のとおりです。

逆元 二項係数 GCD, LCM 約数列挙 素数判定
素因数分解 素数列挙 二分探索 尺取り法 imos法
繰り返し二乗法 拡張Euclid 凸包
diff 灰 茶 緑 水 青 黄↑ その他 CF 合計
AC数 294 78 30 3 0 0 9 0 414
割合 54% 42% 16% 2% 0% 0% - - -

水色になるまで(～2回生6月)

緑diffを埋めたり、引き続き蟻本初級編の類題を埋めていました。レートが1000を超えたあたりからは、水diffで解けそうな問題を解いたり、蟻本中級編や下のサイトの問題を解いていました。コンテストでは緑diff以下を速解きして、たまに来る水diffの数学問題をACすることでレートを稼いでいました。
qiita.com

水色になるまでに勉強した内容です。

集合 多重集合 連想配列 順列列挙
優先度付きキュー 二次元累積和 Union-Find木 ダイクストラ法
ベルマンフォード法 ワーシャルフロイド法 順列列挙 3分探索
トポロジカルソート 半分全列挙 LCS LIS
diff 灰 茶 緑 水 青 黄↑ その他 CF 合計
AC数 473 157 147 88 27 3 43 0 938
割合 87% 84% 81% 45% 13% 1% - - -

青色になるまで(～2回生1月)

青は化け物だと思っていたので、この時点で競プロをやめようかと思っていたのですが、レートが伸び悩むまでは続けてみることにしました。

この時点での強みは、

  • 緑diff以下の問題の解法を思いつくまでが速い
  • 算数・数学的な問題が少し得意

という点でした。逆に弱みは、

  • 精進時間が青を目指す割に少ない
  • 実装をバグらせて時間を溶かすことが多い
  • コーナーケースを見落とすことが多い
  • 高難易度を解く考察力が身についていない

という点でした。コンテストで事故ってレートを大きく下げてしまうと、取り返すのに数週間～数か月かかってしまう上に、何よりモチベーションが失せてしまうことが怖かったので、特に弱点を克服していく感じで精進していきました。

まず、精進時間に関しては、Twitterの精進用アカウントを作って、生活に競プロを侵食させていきました。また、某ウイルスの影響で大学の講義がオンライン授業になり、1週間のどこでかで課題を提出すればいいという感じになったので、月・火(・水)曜日くらいに課題を一掃して、水～日曜日は出来るだけ競プロに集中するようになりました。

2・3番目の実装力に関しては、JOIの過去問を解いていくようにしました。JOIの問題は実装が重たいものが多いため、実装力を付けるのに向いています。僕の場合、実装をバグらせる主な原因は、頭の中で考察をして紙に整理しなかったり、「いける！」と思ったらコードを書きながら考察をしてしまうことでした。実装をバグらせることが多いと思ったら、コードにする前に考察を紙に整理すべきだと思います。「コードを書いている途中に考察が間違っていることに気が付いた」ということが減りますし、細かい条件分岐やコーナーケースにも注意しやすくなります。

4番目の高難易度の問題に関しては後述していますが、週に何問かだけでも青diffを埋めていくようにしました。最初は全然解けませんでしたが、次第に自力でACできる割合が増えていくのが実感できました。また、今まで勉強しなかったデータ構造・アルゴリズムもとにかく貪欲に勉強していくようにしました。

その他には、AtCoder Problemsの「くじかつ」という毎日夜9時に開かれているバーチャルコンテストに出るようにして、速解き力を鍛えたり、AtCoderの解説放送や、YouTubeでの実況、他の方の解説ブログなどを見たりもしました。特に解説放送や実況では、強い人がどんなことを考えて問題を解いているのかを説明してくれるので、とても学びが多かったです。

これらを続けると順調にレートが上がっていきましたが、11月ごろにレートが1500を超えたあたりで伸び悩みました。

典型はある程度揃っていると思っていたので、とにかく場数と演習量を増やそうと思い、Codeforcesというロシアのコンテストサイトに出たり、Educational Codeforces(通称エデゥフォ）という教育的な問題を集めたセットを埋めていくことで、無事に青色になることができました。Codeforcesは深夜にコンテストが開催されるのでおすすめはしにくいのですが、大学がオンライン授業になって、「俺が起きている時間が昼なんだ」などと考え始めている人は是非参加してみるといいと思います。

青になるまでに勉強した内容です。

Grundy数 座標圧縮 平方分割 セグメント木 遅延評価付きセグメント木
転倒数 分割数 行列累乗 ダブリング ポテンシャル付きUnion-Find木
括弧列 包除原理 フロー 最小全域木 最大安定集合
2部グラフ Euler Tour TSP Z-algorithm Kadane's Algorithm
区間DP 桁DP 木DP 全方位木DP Binary Indexed Tree
Splay木
diff 灰 茶 緑 水 青 黄↑ その他 CF 合計
AC数 546 186 182 181 116 11 196 157 1575
割合 100% 100% 100% 93% 57% 2% - - -





その他精進について

目標の立て方について

ある程度競プロをしていると、この界隈には化け物が一定数いることがわかると思います。これはchokudaiさんも言っていたことですが、自分より圧倒的に強い人と自分を見比べて、自分を卑下するべきではないと思います。

まずは自分の1色上、厳しければ1級位上などを目標にしたり、あるいは今まで解けなかった問題を解けるようになったことや、コンテストで粘って難しい問題を解けたことなどをモチベーションにするのがいいと思います。

難易度の高い問題の勉強について

上で述べたような化け物以外は、色変直後は自分の色より上の問題はあまり自力でACできないと思います。これは誰でもそうだと信じたいのですが、解けないのに精進を続けることは精神的に辛いです。僕も緑になったころは水diffはほとんど解けませんでしたし、水になったころは青diffはほとんど解けなくて辛かったです。しかし、そういった難易度の問題をなんとか自力で解いたり、解説を読んだり解説放送を見て理解していくと(僕の場合は30~50問程度)、特に類題という訳でもないのに解法が見えてくるようになります。そうすると今まで解けなかった問題がだんだん解けるようになってきて、かなり楽しくなると思います。最初はしんどいですが、1週間に何問かだけでも、やる気になった時に解いていくようにするといいと思います。

下埋め(低難易度埋め)について

これは精進の方針なので、人によって向き不向きがありますし、賛否両論もあると思いますが、僕は下埋めを積極的ににやりました。下埋めは退屈ですが、やっておくとコンテストで絶対に解けないといけない問題を取りこぼすことが減りますし、速解きにも繋がると思います。実際、なりたい色の一つ下のdiffをコンテスト中にしっかり通せれば、その色のパフォーマンスが出るということはよくあります。僕は「速解きで最低限のパフォーマンスを確保してから難しい問題を落ち着いて解く」という立ち回りが合っていたので、精進では目標の色より下のdifficultyをある程度埋め終わってから、目標の色に挑戦するようにしていました。

終わりに

このまま競技プログラミングを続けるかはかなり悩んでいます。ここまで熱中できる趣味はそう見つかるものではないと思いますが、時間も大量に溶かしてしまいます。完全に私事ですが、現状一番問題なのが将来やりたい仕事が決まっていないことなので、競プロ以外の色んなことにも手を出してみたいと思っています。

そういうわけで、競プロをやめてしまうかもしれないので、残しておきたいことや記録も含めて書き連ねました。長くなってしまいましたが、最後まで読んでいただきありがとうございました。少しでも役に立ったり、共感していただける点があればいいなと思っています。

Educational Codeforces Round 99(Div.2) D. Sequence and Swaps 解説

初投稿なので丁寧目に書きました。たぶん今後は徐々にテキトーになります（苦笑）

問題リンク

codeforces.com

 

問題概要

n個の非負整数からなる数列 a=\{a_1, a_2, ..., a_n\}と、非負整数 xが与えられます。次の操作を好きな回数行えます。

   操作: xより大きい aの要素 a_iを選択し、 a_iと xを入れ替える。

 数列 aを広義単調増加にするために必要な操作回数の最小値を求めてください。ただし、不可能な場合は -1と出力してください。

 

制約

1 \leq t \leq 500, 1 \leq n \leq 500, 0 \leq x \leq 500

ただし、 nの和は500を超えない。 tはクエリの個数。

 

解法

xと交換する aの要素は必ず xより大きいので、スワップを繰り返すにつれて xは(狭義)単調増加することと、ソート後の数列は左に行くほど小さくなることを考えると、直観的に xとスワップできる要素の内、最も左の要素をスワップをしていきたくなります。証明します。

 証明

　 x(=x')と a_i, a_j (i \lt j)がスワップできるとします。この時 a_i, a_j \gt xが成り立ちます。ここで a_jとスワップした場合、数列の並びは a_i, x'となり、 x=a_jです。 a_i \gt x'でしたから、この2要素の並びはこのままではいけません。しかし、さらに x(=a_j)を a_iとスワップしても a_j \gt x'なので大小関係が逆のままとなります。1回目あるいは2回目のスワップの直後に他から要素を貰ってくることもできますが、 xは単調増加であり、 x'よりも小さな xを貰うことはできないため、 i番目の位置には x'以下の要素を置くことができません。よって、2つ以上スワップできる要素があった時、そのうち最も左の要素とスワップするべきであり、逆にその他の要素とスワップするとソートが完遂しません。従ってこれが唯一の手順となり、他の手順が存在しないため、当然最小の手順にもなります。

 

　ただし、途中でスワップできたとしても、ソートが完了していればスワップする意味はありませんので、その時点で終了すべきです。（←自戒）

 実装

  1. 数列がソート済みであるかを確認する。ソート済みなら終了。
  2. 数列を前から見ていき、スワップできるならばスワップする。
  3. 最後に数列を確認し、ソートされていれば回数を、ソートされていなければ-1を出力する。

 

codeforces.com 

感想

　コンテスト中はソート済みかの確認を忘れて1ペナを出してしまいました。今回のコンテストは(少なくともDまでは)、解法がわかってしまえば実装は楽な問題が多かった気がします。あと、解説記事を書くとコンテスト中は適当になりがちな証明を詰めれていいですね。続けていきたいです。