オットセイのコーディングブログ

ベンチャーCTOが綴るコーディング問題解説(LeetCode)、たまに本業のデータサイエンス談義

Kaggleコンペ初心者が命削りながらなんとかメダル圏内に滑り込んだ話 (IEEE-CIS Fraud Detection)

前回のブログ記事投稿から約1ヶ月。この1ヶ月はKaggleのIEEE-CIS Fraud Detectionに人生を捧げると決めてブログを休んでいましたが、10/4にコンペが終了しました。

結果は、6381の参加チーム中、532位でした。上位10%に入ることができ、初Kaggle本気参戦で銅メダルを獲得することができました。

しかし、2週間ほど前からあらゆる試行錯誤を繰り返してもPublic LBが上がらず、所謂「このKaggleコンペ何もわからない」状態に陥り、非常に苦しい思いをした記憶が強いです。

ということで、本記事はKaggleで初メダル圏内を目指そう、という方を読者に想定して、自分のやったことを書きます。

メダルを既に獲得されている方、ましてKaggle Expert以上の方で万が一本記事にたどり着かれた場合は、さくっと離脱いただくか、笑って眺めていただければと思います。

1. 目的を明らかにし、自分の能力や環境を客観的に評価して、目的に到達するための戦略を立てる

いきなり自己啓発本みたいな言葉を並べましたが、Kaggleも一つの競技である以上、何を目的としてやっていて、それに到達するための自分の能力や環境はどうで、だからこんな戦略をとるべきだ、ということを考えないで戦いに臨むのは愚かだと考えました。

自分の場合、目的は以下2点でした。

  • データサイエンスコンペティションを開こうとしている者として、Kagglerのお気持ちを理解するために全力で戦う
  • 自分の全力を引き出せるように、無謀ではないが高い目標を設定する。具体的には銀メダルの獲得

データを眺めて法則を見出すのが好きな自分としては、本来はEDAをフラフラやって楽しみたいなという気持ちもあったのですが、上記がより重要度の高い目的としてあったので、本音は封印して、結果を出すことを重視しました。

一方で、自分の能力や環境は以下の通り捉えました。

  • Positiveな面
    • 大学で学ぶレベルの統計・機械学習の知識はそこそこある
    • 大学院や仕事で英語に触れていたのでそこそこ読める
    • コンサル業界にいたことがあるので調査力(ググり力)はそこそこある
  • Negativeな面
    • Kaggle初本気参戦なので、全体として何をやれば良いか、その中で何に力を入れるのがスコアupのために重要か、何も分かっていない
    • プログラムを書き始めて歴が浅いので、何でもない処理を書くのにも他の参加者に比べてもたつく可能性
    • スタートアップを経営しながらの参戦なので、(多分)他の参加者に比べて潤沢な時間を投入できるわけではない

半ば必然的に導かれた戦略は、
変に自分の能力に期待せず、徹底的に先人の知恵を調べ尽くし取り入れる。さらに時間が限られているので、スコアを上げるために重要な作業に集中的に時間を投入する
という身も蓋もないものとなりました。

結果から言えばこの戦略は間違っていて、先人の知恵ばかりに期待して自ら有効な特徴量のアイデアを探索する姿勢が弱いようでは、銀メダル圏内に到達できるほどKaggleは甘いものではなかったです。

しかし、自分の目的と能力・環境を照らして戦略を立てたこと自体は間違っていなかったと思います。

2. 全体として何をやれば良いか、その中で何に力を入れるのが重要か、特定する

大方針が決まったので、次に具体的にやるべき作業を理解する段に移ります。

まず、全体として何をやれば良いか把握するところからですが、偉大な先人が素晴らしいまとめをしてくださっています!

qiita.com

Kaggle界隈ではとても有名なupuraさんの記事ですね。この情報がなければ当て所なくKaggleに臨んでいたと思うので、ゾッとします。

さらに、主にTwitterやslack(kaggle-ja)で調べを進めた結果、自分なりの解釈ですが、Kaggleでは全体として以下をやれば良いのだと理解しました。

f:id:mhiro216:20191006125412p:plain

そして、もし投入できる時間が限られているのであれば、力を入れるべき工程は「特徴量エンジニアリング」「Discussion & Notebook 読み込み」だと理解しました。

情報を集める中で、スコアを上げるために特に重要なのは有効な特徴量を発見する特徴量エンジニアリングである、ということが多く言われていました。

一方でハイパラチューニングなどは、議論はそこかしこでなされていますが、実際のところ大きくスコアupに寄与することは少ない、と言われていた気がします。

さらに、Kaggleの良いところは、Discussion & Notebookがあることで、他の参加者と発見した知見を共有しながら戦えることです。

他の参加者の知見だけでなく、今回のようにデータの秘匿性が深く、カラム名がマスキングされているコンペでは、コンペ主催者から開示できる範囲のデータの補足説明がなされたりします。

実際今回のコンペでは、コンペ主催者からの説明はスコアupのための大きなヒントが含まれていました。

前述の通り先人の知恵に学ぶと決めたので、Discussion & Notebookは毎日チェックすることにしました。

あまりにDiscussionの内容を参考にしすぎたので、危うく落とし穴にハマりかけたこともありましたが。。。

以降、各プロセスでやったことを記しますが、明らかに特徴量エンジニアリングに重きを置いた内容となっており、他の工程がスッカスカなのはご了承ください。

3. 実験環境構築

早速データ分析に移りたいところですが、特徴量を追加・削除してモデルを作りスコアの変動を見るというプロセスを何百・何千回と繰り返すことになるので、その作業を行う環境を固定し、できるだけ効率的に実験を回せるように準備しておくことが長い目で見ると重要です。

実験のプロセスですが、大きく分けると以下の2つから成ります。

  1. 新たな仮説に基づく特徴量を追加してみて、スコアupに寄与するかどうか、全データを使わずにクイックに検証
  2. 検証結果が積み上がってきたら、全データを使ってCross Validation (CV)しながらモデルを作り、出力をsubmitしてLeader Board (LB)の変化を確認

一方で実験に使える環境は、一般的には以下の選択肢があると思います。

  • 個人のローカル環境
  • Kaggle NotebookやGoogle Colaboratoryなど無償のコンピュータリソース
  • GCPAWSなど有償のコンピュータリソース

結論から言えば、私は
1のクイックな検証には個人のローカル環境+Kaggle Notebookを、
2のモデル構築にはGCPのGCEを、
使いました。

理由は単純で、個人のローカル環境やKaggle Notebookは高々十数GBのメモリしかないので、特徴量を何千と作り探索しようとしていた私のやり方では、簡単にMemory Errorとなってしまうためです。

GCPを使う最大のデメリットは有償であることで、今回私は3万円ほど使いました(他の方のお話を聞いていると、決して高くないと思います)が、学生さんなどはなかなか難しいかと思います。

有償のリソースを使えない場合、メモリに配慮しながらKaggle Notebookなどを使い回していくことになりますが、それでも金メダルを獲得されている方はいらっしゃるので、テーブルデータであれば十分可能と思います(画像データではなかなか難しいと聞きます)。

で、GCPを使った実験環境の作り方ですが、これも偉大な先人であるtkmさんが手順を残してくださっています。

www.youtube.com

動画の手順と若干異なるのは、私はvimに慣れていないので、ローカルのPyCharm上でスクリプトを修正してgithubにcommitし、GCEにSSHで接続した後githubから修正したスクリプトをpullして実行する、という手順をとっていました。

いずれにせよ、tkmさんは他の動画でBigQueryでKaggleのデータを分析する手順も残してくださっていたり、非常に有益なコンテンツが多いので、食事中にテレビ番組を見るくらいならこちらの動画を流した方がinf倍有益かと思います。

4. EDA

ここからデータ分析に入るわけですが、コンペ参戦を決めたのがコンペ中盤だったこともあり、既に先人が多くのEDAを投稿してくださっていました。

そこで、ざっとEDA系のNotebookを確認した後は、先に特徴量エンジニアリングに着手してしまうこととし、特徴量のアイデアに行き詰まったら自分でEDAをしてみよう、という手順をとることにしました。

5. モデル構築手法選択

テーブルデータにおけるモデル構築手法は、大きく2つの選択肢があります。

テーブルデータでは、多くの場合勾配ブースティング系の手法の方がスコアが高くでるようです。

また、後に出てくるハイパーパラメータチューニングの方法はもちろんのこと、一部の特徴量の作り方についてもGBDTとNNで異なるので、投入できる時間が限られる今回は複数の手法に手を出すのは得策ではないと判断しました。

そこで今回は、LightGBM一本に絞って取り組むことにしました。

この戦略が良かったかどうかですが、最後に行うアンサンブルで、モデルの予測値を複数組み合わせて最終的な予測とするということをしますが、類似のモデルではなく全く独立に作られたモデルを混ぜた方がスコアが良くなることが一般的に知られています。

従って、使う手法を一本に絞ったことはアンサンブルで不利になりますが、一方でLightGBM一本でも上位Solutionでは銀メダル圏内に到達する相当のスコアが出ていたので、やはり次の特徴量エンジニアリングが勝負の分かれ目だったと思います。

6. 特徴量エンジニアリング(Feature Engineering)

戦いのスタートにあたり、良さげなNotebookを見つけ、Forkします(こういうことができるのがスターターに優しくて良いですね)。

私はKonstantin YakovlevさんのNotebookを元にしました。

選んだ理由は、スコアが良いこともそうですが、コードがシンプルでわかりやすく、今後コードを改変して特徴量を追加・削除していくときに混乱しづらいと思ったためでした。

ちなみにこのKonstantin Yakovlevさん、大量のDiscussion & Notebookで参加者に知見を振りまきながら、2位以下を突き放して圧勝されています。

スコアでも教育目的でも多大な貢献をされていて、プラットフォーマーのKaggle的にはこれ以上の貢献はないでしょうね。いつかこの域に達したいものです。

次に、Discussionを眺めながら良さげな特徴量をピックアップし、追加・削除しながらスコアupに寄与するか検証していきました。

以下、私が試行錯誤した特徴量を書き連ねます。本コンペのDiscussionを元に試したものが多いですが、過去コンペで有効だった特徴量も調べて投入しています。

具体的な実装については、長くなるので別記事にまとめることとして、ここでは頭出しだけします。

主に参考にしたDiscussion:

行った特徴量エンジニアリング:

  • 既存のfeatureに対する処理
    • NANをfeatureの最小値より小さい値(-999など)で置換
      • LightGBMはNANがあるとnon-NANだけを分割し最後に残りのNANをいずれかのnodeに振り分ける。過学習につながるリスクがあるためNANは置換しておくのが一般的
    • binning
      • 量的変数を任意の境界値で区切りカテゴリ分け
      • 境界値は1000, 2000, 3000,,,などと一定間隔の値で決める方法もあれば出現頻度で区切る方法もある(histogramの作り方と同じ)
    • label encoding
      • string, category, object型の変数をint型に変換
    • outlier removal
      • 出現頻度が非常に低い値は-9999など(NANの置換に使った値とは違う値)で置換
      • 今回は異常値を見つける問題なので注意して使用すべき
    • TransactionAmtのlog1pをとる
  • 既存のfeatureをgroup単位でaggregation(例えば、card1のcategoryごとに平均をとって新たなfeature "card1_mean"とするなど)
    • sum, mean, std, min, max
    • frequency encoding
    • normalization
      • mean, stdを使ったnormalization、min, maxを使ったnormalization
    • target encoding
      • train dataのターゲット変数の値をgroup単位でmeanなどのaggregationを行うこと
      • やりすぎると過学習になる(未知のデータに対する精度が低くなる)ので初心者にはリスキー。私見ではこれを使わないで精度が上がる方法をまず探すべき
  • group自体を新たに生成
    • cardやaddrを結合してuser groupを生成し、aggregation
    • 今回は時系列データなので、TransactionDTを月/週/日/時間などに変換し、各々の単位でaggregation
    • 今回は時系列データなので、TransactionDTの前後X個のレコードについてaggregation (rolling window)
    • NANの数が同じ変数でグルーピング -> PCAに利用(実装の参考)
  • aggregationではない方法でfeatureを新たに生成
    • 量的変数の和・積・差・商
    • TransactionAmtの小数点以下(cent)のみを取り出す
    • lag/lead
      • 例えば、card1を使ったtransactionが1つ前に発生した時点までのTransactionDTの差(lag)、1つ後に発生した時点までの差(lead)
      • 実装の参考
    • pseudo-labeling
      • 一度予測を行い、予測値が0ないしは1に非常に近いtest dataのtargetに0ないしは1をlabelしてしまい、train dataに新たに追加
  • featureを縮約して新たなfeatureで代替(元のfeatureを残しておいても良いが、縮約したいというニーズがある以上普通は元のfeatureは削除する)
    • PCA
      • 量的変数をn次元に縮約して新たなfeatureとする
      • これが有効な理由は、決定木系アルゴリズムが軸に斜めの表現を不得手なため(参考
      • 実装の参考
    • LDA
      • LDAは文章をベクトル化するとき、出現する単語の出現回数で表現すると次元が極度に大きくなってしまうので、次元削減するときに使う手法
      • この発想をテーブルデータにも適用して、カテゴリ変数間の共起行列を作り、それに対してLDAを行い新たなfeatureとする
      • 参考

様々試した中、最も有効だった特徴量は、

cardやaddrを結合してuser groupを生成し、count, mean, stdなどでaggregation

でした。

アンサンブルする前のモデル単体で、Public LBは0.951+でした。

1st solutionでも同様にuser groupを生成してaggregationした特徴量を有効に使っていて、私との違いは、私はuser groupを特定する程度で止まっていたところを、1st solutionではuser個人を特定する程度までcardやaddrを結合した上で様々なaggregationを行なっていました。

user個人を特定することが重要だというのは以下のDiscussionを見てなんとなく気づいていたのですが、実験するところまで動けなかったのが敗因で、悔やまれます。

"The logic of our labeling is define reported chargeback on the card as fraud transaction (isFraud=1) and transactions posterior to it with either user account, email address or billing address directly linked to these attributes as fraud too. If none of above is reported and found beyond 120 days, then we define as legit transaction (isFraud=0).

ちなみに、大きくスコアをboostするfeatureをmagic featureと呼ぶそうです。コンペ中盤にKonstantin Yakovlevさんが「magic featureが3つあるよ」とおっしゃっているのを見て以降、ひたすらmagic featureを探していたのですが。。。

他にも「TransactionAmtの小数点以下(cent)のみを取り出し、aggregation」などもスコアupに寄与しましたが、user個人を特定した特徴量に比べると効果は小さく、本当にここで勝負が決まってしまったなという感じです。

7. 特徴量選択(Feature Selection)

特徴量を作成した後は、それが有効かどうか検証し、取り込むか否かを決める必要があります。

私は1変数追加するごとに一部データを使ってLightGBMでモデルを構築し、CVの結果をみて有効か判定していました。

LightGBMで検証するとそこそこ時間がかかるので、高速に検証を回したい場合はRidge回帰で代替する手法も一般的なようです。

また今回は採用しませんでしたが、LightGBMではfeature importanceを返してくれる関数が用意されているので、とりあえず大量に思いつく限りの特徴量を作って投入し、feature importanceが0より大きいものは全て採用する、という手法もあると思います(逆にfeature importanceが0より大きいものは、モデル単体の精度向上には寄与しているので、いくら小さくても除くべきではない。敢えてそれらを除いたモデルを作り、後でアンサンブルしたい場合は別)。

今回は大量にfeatureを作ればスコアが上がるというより、特定のmagic featureを見つけることが重要な気がして1変数ごとに検証する手法を採りましたが、これが良かったかどうかは分かりません。

ちなみに世の中にはboruta, NullImportancesなどのfeature selectionの手法もあるそうですが、なかなか扱いは難しいようです。

8. クロスバリデーション(Cross Validation)

Cross Validation (CV)が何かはここでは詳説しませんが、簡単に言えばTrain dataをさらにTrain, Validate dataに分割し、Test dataによる予測を行う前に精度を予測する手法です。

これがなぜ重要かというと、Public LBが計算される対象はTest dataの一部を切り出したもので、Test dataの中で分布に偏りがある部分を切り取っている可能性があったり、そもそも少ないデータ量が切り出されていたりで、最終的に順位決定に使われるPrivate LBとは必ずしも結果が相関しないことがあるからです。

尚、Public LBとPrivate LBが激しく変動することをShake up/downというようです。あまりにこれが大きいコンペでは参加者に混乱を巻き起こしますが、しかし毎回安定して勝っている方もいるので、CVをしっかり設計すれば安定して勝てるはずとも言えます。

それくらいCVは重要で、たとえPublic LBが多少下がっても"Trust your CV"してCVが良くなるモデルを採用していくのが望ましいとされています。

逆に言えば、"Trust your CV"できるCV Strategyを立てなければいけません。

CV StrategyってKFold以外に何があるの?と私も以前は思っていましたが、今回は以下の3つを検討しました。

  • KFold
    • Train dataをK個に分割。デフォルトでは連続するレコードのまとまりで分割するし、shuffle=Trueとすることでランダムな分割も可能
  • GroupKFold
    • 特定カラムのgroupごとにTrain dataを分割。今回のデータであればTransactionDTから算出したmonth別に分割するなど
  • TimeSeriesSplit

どのCVが良いのかですが、明確な判断基準はないものの、

CVのTrain dataとValidate dataの関係が、最後のPredictionでTrainするdataとTestするdataの関係と同様になるようにCVを設計する

のが重要なようです。

今回で言えば、Test dataはTrain dataより先の月のデータとなっていることがわかっていたため、TransactionDTから算出したmonth別に分割するGroupKFoldを採用することとしました。

9. ハイパーパラメータチューニング

LightGBM公式Documentに従ったチューニングを行うつもりでしたが、結局最後まで特徴量探索に時間をかけていたので、最初にForkしたNotebookの設定値を最後まで使っていました。

一応Optunaを使ってみたりもしたのですが、探索範囲が悪かったのか、広すぎたのか、CVを改善するパラメタは発見できず。

次回コンペの宿題ですね。

10. アンサンブル

アンサンブルは異なるモデルを複数作り、予測値の平均をとって最終的な予測とする手法です。

異なるモデルを複数作る方法は色々あって、

  • モデル構築手法を変える(LightGBM, XGBoost, CatBoost, NNで作った各モデルを混ぜるなど)
  • 特徴量を変える
  • ハイパーパラメータを変える
  • 乱数seedを変える
  • (邪道ですが)upされているNotebookの予測値と自分の予測値を混ぜる

などとありますが、今回はモデル構築をLightGBM一本でやっていて、かつ特徴量探索にほとんどの時間を振ったため、乱数seedを変えるseed averagingと、upされているNotebookの予測値と自分の予測値をsimple averaging / rank averagingする程度のことしかしませんでした。

ちなみにアンサンブルの各手法はこちらにまとまっています。

簡単なアンサンブルの結果、Public LBは0.952+まで到達しましたが、0.953の壁を破ることができず、Public LBでもPrivate LBでも銅メダル圏内に終わりました。

この0.953の壁が非常に高く、コンペ最後の1週間ほどは、努力が報われない辛さと不規則な生活によるダブルパンチでなかなかシンドイ日々を送っていました。。。

余談:毒入りKernel

余談ですが、コンペ終盤にPublic LBが0.9532のNotebookがupされました。これは当時銀メダル相当のNotebookで、一瞬色めき立ったものです。

しかし自分の予測値との相関をとってみると、初めの10万行は0.99+ですが、最後の10万行は0.09ほどしかないではありませんか! (今回のTest Datasetは初めの20%のレコードがPublic LB算出に使われ、残りの80%がPrivate LB算出に使われることはDiscussionから分かっていました)

つまりこのNotebookはPublic LBに過学習したもので、これをアンサンブルに取り入れてしまったりすると大きくPrivate LBを落としてしまうわけです。

TwitterではこのNotebookのことを「毒入りKernel」と呼んでいる方がいて、言い得て妙だなと思いました。

勝負事らしい騙し合いも一部では繰り広げられていましたという余談です。

感想

次回コンペに向けて

多くの時間を極端に特徴量エンジニアリングに振る戦略をとりましたが、それ自体は間違っていなかったと思っており、

Discussionを読み込む中で気になったものはすぐに実装に落として検証する、という姿勢を貫くことが次回コンペに向けては重要だと思いました。

後は、なんだかんだで投入した時間は平日夜は毎日2時間ほど、土日計16時間ほどに達していて、相当家庭に負担をかけてしまったなと思っており、

今回作成した特徴量作成のスクリプトなどを再利用できる形にして、効率的に戦うことも重視せねばと思いました。

匿名コンペについて雑感

今回のコンペはuserを特定し特徴量作成することが重要だったわけですが、当然ながらコンペのデータ提供者はuserデータを保持しており、匿名化されていたことになります。

つまり既に分かっている情報を解き明かすことに多くのKagglerの力が注がれていて、それって無駄じゃない?という考えも当然あります。

私も基本的には同意で、ただ難しいのは履歴データはデータが多ければ多いほど匿名性が落ちるので、userを仮名化していても、プライバシー保護しきれないリスクをデータ提供側が憂慮する気持ちも分かります。

加えて今回はFraudというsensitiveな情報が含まれるデータなので、k-匿名性を担保できない状態では、user情報を削除せざるを得なかったと想像します。

データサイエンスコンペは、仮に成果物が実務で役に立たなくとも参加者のスキルアップに繋がるし、何より1つの競技として面白く価値は高いと思うのですが、 一方で実務で役に立たないものに人生の多くを捧げている人もいることを思うと、資源が無駄使いされているようにも思います。

悩ましさを感じつつも、まずは不満の出ないコンペを開催することよりも議論を呼ぶコンペを開催することが正だと信じて、突き進もうと思います。

DAG(有向非循環グラフ)に対する最長経路問題(AtCoder Beginner Contest 139より)

最近はKaggleを優先していてなかなか競プロの時間を取れないのですが、AtCoderのABCには参加しています。

で、1週間遅れになってしまいましたが、先日のABC139でDAGの問題が出ました。
DAGは今後も重要そうな気がして、YouTube公式解説のC++のコードを読み解き、Python化しました。

問題内容・解法

E - League

atcoder.jp

解法の考え方については以下の公式解説が非常に分かりやすいです。

www.youtube.com

簡単に紹介しておくと、問題で与えられたデータは、リーグ戦をイメージして、各選手について対戦したい選手の順番が決まっているというものですが、これを試合idに読み替えます。

f:id:mhiro216:20190908141016p:plain

すると、これはDAG(有向非循環グラフ)に対する最長経路問題であると読み替えることができます。

f:id:mhiro216:20190908141439p:plain

上の例では、頂点Aから頂点Eへの移動が最長経路となり、値は4、つまり試合日程を全てこなすのに必要な最小の日数は4日である、ということになります。

DAGということはループが存在しないわけですが、この問題でなぜそう読み替えられるかというと、
「選手1はまず選手2と対戦したくて、選手2はまず選手3と対戦したくて、選手3はまず選手1と対戦したい」などというデータがあった場合、これを満たす試合日程を組むことはできないわけですが、これはグラフ上ではループとして検出できます。
問題文では条件を満たすように試合日程を組めなければ'-1'を返せと言っているので、ループが検出されたら'-1'を返すように実装することになります。

さて、以下がPythonによる実装になります。

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

MAXN = 1005
MAXV = MAXN*(MAXN-1)//2
to = [[] for _ in range(MAXV)] # 頂点間の辺の情報
id = [[[] for _ in range(MAXN)] for _ in range(MAXN)] # 試合のid=DAGの頂点番号
def toId(i,j): # 選手idから試合idを返す関数
    if i > j: # i,jが逆になっても試合idは同じ
        i,j = j,i
    return id[i][j]

visited = [False]*MAXV
calculated = [False]*MAXV
dp = [1]*MAXV # Vからスタートしたときの最長経路。頂点の個数ベースで経路の長さを数えるので、初期値は1

def dfs(v):
    if visited[v]:
        if not calculated[v]:
            return -1 # 計算が終わっていない頂点を2度訪れるのはループがあるということ
        return dp[v]
    visited[v] = True
    for u in to[v]: # 全ての辺をなめる
        res = dfs(u)
        if res == -1: return -1 # ループがあれば-1を返す
        dp[v] = max(dp[v], res+1)
    calculated[v] = True
    return dp[v]

def main():
    n = int(input())
    a = [[int(i) for i in readline().split()] for _ in range(n)]
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1 # 選手idを0始まりに変換
    V = 0
    for i in range(n):
        for j in range(n):
            if i < j:
                id[i][j] = V
                V += 1 # 0から順に各試合にidを割り振る
    for i in range(n):
        for j in range(n-1):
            a[i][j] = toId(i,a[i][j]) # 選手idを試合id(頂点番号)に置き換える
        for j in range(n-2): # 頂点間の依存関係はn-2個
            to[a[i][j+1]].append(a[i][j])
    ans = 0
    for i in range(V):
        res = dfs(i)
        if res == -1:
            print('-1') # ループがあれば-1を返す(問題文の指示)
            return
        ans = max(ans, res)
    print(ans)
    return

if __name__ == '__main__':
    main()

ここで(大)問題は、Pythonでsubmitすると一部のテストケースでTLEになってしまいます(泣)。
リスト内包表記を入れるとかしてチマチマ高速化しようか悩んでいたところ、Pypyでsubmitしてみるという手があることを知りました。

[https://juppy.hatenablog.com/entry/2019/06/14/Python%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E9%AB%98%E9%80%9F%E5%8C%96tips%28Python%E3%81%A7Atcoder%E3%82%92%E3%82%84%E3%82%8B%E9%9A%9B%E3%81%AB%E5%80%8B:embed:cite]

Pypyで提出すると、無事ACとなりました。
低級言語への乗り換え圧力を強く感じましたが、なんとか乗り切ったことにします。

LeetCode / Number of 1 Bits

ビット表現祭りその2。

https://leetcode.com/problems/number-of-1-bits/

Write a function that takes an unsigned integer and return the number of '1' bits it has (also known as the Hamming weight).

Example 1:
Input: 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:
Input: 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:
Input: 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

Note:

Note that in some languages such as Java, there is no unsigned integer type. In this case, the input will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3 above the input represents the signed integer -3.

解答・解説

解法1

下1桁が1であれば1を足すビット演算を32桁繰り返せば良いので、以下のように処理できます。

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        res = 0
        for _ in range(32):
            res += n&1
            n>>=1
        return res

時間計算量・空間計算量ともにO(1)なのでここで満足しても良いのですが、若干改善の余地があります。

解法2

32桁走査せずとも処理を完了できる可能性がある解法がこちら。

class Solution(object):
    def hammingWeight(self, n):
        res = 0
        while n != 0:
            res += 1
            n &= n-1
        return res

n&(n-1)のビット演算を行う手法です。
どういうことかというと、n = n&(n-1)のビット演算を行なうごとに'1'のbitの数が1つずつ消えていくので、nが0となるまでの処理の回数をカウントしてやれば良いんです。
具体例を示します。

n : 00000000000000000000000000001011

n : 00000000000000000000000000001011
n-1 : 00000000000000000000000000001010
n&(n-1): 00000000000000000000000000001010

n : 00000000000000000000000000001010
n-1 : 00000000000000000000000000001001
n&(n-1): 00000000000000000000000000001000

n : 00000000000000000000000000001000
n-1 : 00000000000000000000000000000111
n&(n-1): 00000000000000000000000000000000

という形ですね。

LeetCode / Reverse Bits

ビット表現祭り。

https://leetcode.com/problems/reverse-bits/

Reverse bits of a given 32 bits unsigned integer.

Example 1:

Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10101111110010110010011101101001.

Note:

Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2 above the input represents the signed integer -3 and the output represents the signed integer -1073741825.

与えられたintegerに相当する32桁のビット表現を逆順にした際の、それに相当するintegerを返す問題です。
Javaではなんだか注意点があるようですが、、、僕はPythonista!関係ない!といつまで言ってられるか分かりませんが、スルーします。

解答・解説

解法1

Pythonでintegerを32桁のビット表現に変換するには、'{0:032b}'.format(n)と表記します。
変数nを32桁のビット表現に変換 → 逆順にソート → 32桁のビット表現をintに戻す
という処理を行えばOKです。

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        return int('{0:032b}'.format(n)[::-1], 2)

解法2

ビット演算・シフト演算だけで行うことを考えると、以下のように書けます。

class Solution:
    def reverseBits(self, n):
        res = 0
        for _ in range(32):
            res = (res<<1) + (n&1) # res<<1:1桁だけ左にずらし、空いたビットに0が入る, n&1:下1桁の値だけ取り出す
            n>>=1 # n>>1: 1桁だけ右にずらし、押し出された下1桁のビットは消える
        return res

解法3

ビット・シフト演算を利用して、このように書くこともできます。

class Solution:
    def reverseBits(self, n):
        n = (n >> 16) | (n << 16)
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8)
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4)
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2)
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1)
        return n

途中16進数の表現が入っていますが、分かりやすく32ビットの2進数表現に直すと

0xff00ff00 : '11111111000000001111111100000000'
0x00ff00ff : '00000000111111110000000011111111'
0xf0f0f0f0 : '11110000111100001111000011110000'
0x0f0f0f0f : '00001111000011110000111100001111'
(以下略)

のようになっています。

つまり、まず上16桁と下16桁の位置を交換し、次に各々の上8桁と下8桁の位置を交換し、次に各々の上4桁と下4桁の位置を交換し、次に各々の上2桁と下2桁の位置を交換し、次に各々の上1桁と下1桁の位置を交換すると、全体を逆順にしたことになる、というものです。

簡単のために8桁で、各桁の値の移り変わりを見ると、以下のようになります。
abcdefgh -> efghabcd -> ghefcdab -> hgfedcba

LeetCode / Rotate Array

https://leetcode.com/problems/rotate-array/

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:
Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]

Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:
Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]

Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?

Rotate Arrayということで直訳すると配列を回転させろ、ということですが、インデックスを前後にずらす操作を行う問題です。
解法を最低3つ、さらに空間計算量はO(1)で、と言われています。AND条件ではなくOR条件だと思いますが、意外に難しく感じました。

解答・解説

解法1

私の力ではどうしても空間計算量がO(n)になってしまいました。

インデックスを前後にずらす=元のリストを2つのリストに分割し組み替えて再結合することになるので、以下コードで正しい値が得られます。

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        k %= len(nums)
        nums[:] = nums[-k:]+nums[:-k]

今回はnumsそのものを操作して戻り値にするという指示があるため、リストに対して破壊的な操作をするためにnums[:]としてコピーを作成します。

リスト内包表記で書くこともできます。

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        k %= len(nums)
        nums[:] = [nums[i] for i in range(-k,len(nums)-k)]
解法2

空間計算量がO(1)の解法その1。
以下Solutionの転載ですが、

Original List : 1 2 3 4 5 6 7
After reversing all numbers : 7 6 5 4 3 2 1
After reversing first k numbers : 5 6 7 4 3 2 1
After revering last n-k numbers : 5 6 7 1 2 3 4 --> Result

3つの手順から成り、1.リスト全体を逆順にソートし、2.リスト後方のk個の要素だけで逆順にソートし、3.残りのn-k個の要素だけで逆順にソートするという手法です。

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        k %= len(nums)
        self.reverse(nums, 0, len(nums)-1)
        self.reverse(nums, 0, k-1)
        self.reverse(nums, k, len(nums)-1)
    def reverse(self, nums, start, end):
        while start < end:
            tmp = nums[start]
            nums[start] = nums[end]
            nums[end] = tmp
            start += 1
            end -= 1

空間計算量を抑えた解法の中で、これが最も明快だと思います。

解法3

空間計算量がO(1)の解法その2。しかしこれは難しいと思いました。

手順は大きく分けると2つから成り、nums後方のk個の要素を正しい位置に入れ替え、次に残りのnums前方のn-k個の要素を正しい位置に入れ替えます。
入れ替え対象のリストは初めはnums全体ですが、入れ替えが完了するまで徐々に狭まっていきます。

具体例で示します。以下、
n: 入れ替え対象のリストの要素数
k: インデックスをずらす要素数
j: 入れ替え対象リストの始点インデックス
とします。つまり常に n + j == len(nums) となります。

nums = [1, 2, 3, 4, 5, 6, 7] を例に考えます。このとき、n = 7, k = 3, j = 0 です。
初めの入れ替えで、以下のように進みます。

[5, 2, 3, 4, 1, 6, 7]
[5, 6, 3, 4, 1, 2, 7]
[5, 6, 7, 4, 1, 2, 3]

ここまで来て、さらに入れ替える必要があるのは後方の [4, 1, 2, 3] です。
このとき、n = n - k, j = j + k, k %= n と計算し、n = 4, k = 3, j = 3 です。

次の入れ替えは以下のように進みます。

[5, 6, 7, 1, 4, 2, 3]
[5, 6, 7, 1, 2, 4, 3]
[5, 6, 7, 1, 2, 3, 4]

これで、入れ替え完了です。
先ほどと同様に、n = n - k, j = j + k, k %= nと計算し、n = 1, k = 0, j = 6 です。

入れ替え完了の判定方法は、n <= 0 と k % n == 0 の2パターンがあります。
n <= 0 になると、入れ替え対象のリストが存在しないので終了し、
k % n == 0 になると、インデックスをずらしても1周回って同じリストとなってしまうので、終了します。

以上をコードに落とすと、以下のようになります。

class Solution(object):
    def rotate(self, nums, k):
        n, k, j = len(nums), k % len(nums), 0
        while n > 0 and k % n != 0:
            for i in range(0, k):
                nums[j + i], nums[len(nums) - k + i] = nums[len(nums) - k + i], nums[j + i] # swap
            n, j = n - k, j + k
            k = k % n

初見でこの解法にたどり着く人は神なんじゃないかな。

LeetCode / Factorial Trailing Zeroes

今日は算数の問題です。大人より小学生の方が解けるかも?

https://leetcode.com/problems/factorial-trailing-zeroes/

Given an integer n, return the number of trailing zeroes in n!.

Example 1:
Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:
Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Note: Your solution should be in logarithmic time complexity.

nの階乗で得られた数値に、trailing zero、つまり後置の0がいくつあるかを返す問題です。
空間計算量のオーダーをlog(n)とすることも求められています。つまり、馬鹿正直にnの階乗を計算するのではない方法が求められます。

解答・解説

解法1

まず気付くべきは、「後置の0が幾つ存在するかは、nの階乗の中で10が何回掛けられるかと同値である」です。
次に気付くべきは、10を素因数分解すると2×5ですから、「後置の0が幾つ存在するかは、nの階乗に2が幾つ存在するか(2で何回割り切れるか)と5が幾つ存在するか(2で何回割り切れるか)の最小値と同値である」です。
そして当然、2で割り切れる回数と5で割り切れる回数では後者の方が小さいですから、5で割り切れる回数を計算すれば、それが答えになります。

さて、以上の考察をそのままコードに落とすと、以下のようになります。

class Solution(object):
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        ans = 0
        while n > 0:
            n //= 5
            ans += n
        return ans

上記コードの中では、5で割り切っているわけではなく5で割った商を足し合わせています。5で割り切るコードよりも短く書けます。横着とも言います。
空間計算量はlog5nになります。

ちなみにPython2だとint同士の割り算はintが返るんですね。上記も n /= 5 としても正解が得られます。知らなかった。。。

解法2

recursiveに書くこともできます。計算量は変わりません。

class Solution(object):
    def trailingZeroes(self, n):
        return 0 if n == 0 else n // 5 + self.trailingZeroes(n // 5)

LeetCode / Excel Sheet Column Number

https://leetcode.com/problems/excel-sheet-column-number/

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...

先日の記事はFrom列インデックスTo列名でしたが、今回はFrom列名To列インデックスの変換がお題です。
From列インデックスTo列名の問題が解ければ、こちらも易しいです。

解答・解説

解法1

英字に相当する値を、26のn乗(nは1の位であれば0, 10の位であれば1, 100の位であれば2,,,)に掛け、合計を取ればOKです。

from string import ascii_uppercase

class Solution(object):
    def titleToNumber(self, s):
        """
        :type s: str
        :rtype: int
        """
        d = {}
        for i,e in enumerate(ascii_uppercase):
            d[e] = i+1
        ans = 0
        for i,e in enumerate(s[::-1]):
            ans += d[e] * pow(26,i)
        return ans

こちらの解法が先に思いついてしまいましたが、文字列数分のループを2度回してしまっているところが改善すべき点です。

解法2

アスキーコードを取得するord関数を使えば、ord(char) - 64 に対して26のn乗を掛けるだけで済むので、1度のループで済みます。

class Solution(object):
    def titleToNumber(self, s):
        """
        :type s: str
        :rtype: int
        """
        return sum((ord(char) - 64) * (26 ** exp) for exp, char in enumerate(s[::-1]))