「政策評価のための因果関係の見つけ方 ランダム化比較試験入門」

「政策評価のための因果関係の見つけ方 ランダム化比較試験入門」を読んだ。政策評価というよりは因果推論の勉強の一環で読んだ。エビデンスに基づいた政策決定(EBPM)において、日本は後進国であると思うが、そのEBPMを進めるためのランダム化比較試験入門(RCT)の簡易的なレビューとして、どちらかというと政策評価に興味あるひとにRCTを紹介する本になっている。

www.nippyo.co.jp

 

帯でうまく隠してあるけど、裏表紙にデカデカと近頃何かと話題のエルゼビアの名前がある(購入してから気づいた)。レビュー論文っぽいやつを輪講ののち、翻訳し40ページ近い解説をつけて本にしたらしい。元が論文であって、教科書ではないことが重要で、薄さと安さの割に比較的広範な話題をカバーしているが、記述の丁寧さはその分譲歩している書き方だと思う。ただ、ついている解説記事が結構丁寧に書かれているので、エッセンスを捉えることは容易だと思う。この本だけで勉強が完結できるとは考えず、気になった各論については都度各自で他の文献等で調べる、という使い方をお勧めしたい。

 

因果推論の教科書には不足しがちな実際に実験を行う際に留意する点(サンプルサイズや検定力の見積もり、他国でのRCTによる教育政策決定事例の紹介、完全にRCTできないケースでどのような手法が取られてきたかという先行研究の紹介など)が書かれていて、特に他国での研究の例では政策評価に主眼を置いていない読者の私でも楽しむことができた。

 

最初に述べたようにEBPMが主眼であり、これだけでRCTについては万事OKかというと、おそらくそうではないだろう。ただ、RCTにおいて何が重要か俯瞰図を得るためには十分であり、かつ実際にRCTを試行する際の留意点が得られるという点で優れたものだと思う。政策決定以外の分野の人にとっても(全く興味がない方なら苦痛かと思うが)RCTの理解についての良い橋頭堡になっている。付き合い方を理解した上で読むにはとても良い本だと思う。

データサイエンス100本ノック(構造化データ編)SQL版全問題解説

データサイエンティスト協会スキル定義委員によるデータサイエンス100本ノック(構造化データ編)をやってみたので、簡単に解説を書いていきます。全問題といいましたが風呂敷を広げすぎたので、適宜端折ります。今のところ、おおよそ数問毎にどのような知識が必要かというガイドライン程度に止まっていますが、目安になると幸いです(問題個別の解説になるように定期的に改善していく予定)。

 

githubレポジトリはこちら。

GitHub - The-Japan-DataScientist-Society/100knocks-preprocess: データサイエンス100本ノック(構造化データ加工編)

 

問題を解くためのセットアップはこちらの記事を参考にしました。

qrunch.net

 

Windows 10 ProであればDocker Desktop推奨。

 

Macの方はこちら。

qiita.com

 

ちなみにIEやEdgeではlocalhost:8888とやってもJupyter Labが走らないので気をつけてください。

 

ちなみに100本ノックに臨む前にSQLの最低限の記法を知っているほうが良いと思います。ただ、答えを見つつ、ググりつつやれば(プログラミングの経験がある人などは特に)初学者でも進められるかもしれません。SQLの文法を気楽にまず学びたい方で英語が得意な方は実際に実行しつつ学べるKaggleの二つのSQL Courseがあります。もちろん、100本全てを解けるだけの題材はカバーしてないのですが、基礎事項は押さえられると思います。日本語が良い方は自分に合いそうな本や記事を探してみてください。

www.kaggle.com

www.kaggle.com

 

1-9問目

基礎の基礎です。最初の9問は

SELECT文でカラムの名前を指定する

FROM文で参照するテーブルの名前を指定する

WHERE文でデータを取ってくるときの条件を指定する

(実際に何千行もある全データを表示できないので)LIMIT文で表示するデータの行数を指定する

この4つさえわかっていれば進めることができます。

 

SELECT *で全てのカラムを指定できること

文字列は'(シングルクォーテーション)で囲むこと

WHERE文の条件は複数のものをANDやORでつなげられること

などがちょっと進んだ概念としていくつかの問題で必要になってきます。

 

10-16問目

WHERE文の中で文字列を比較する問題が続いて出てきます。

where 変数 like '文字列'で比較できます。PostgreSQLでは%によって任意の文字を表すことができます。

また、いくつかの問題は「正規表現」というSQLに限らずプログラミング言語ではよく出てくる別の記法で解く必要があります。その場合、likeではなく~(チルダ)を代わりに使います。where 変数 ~ '正規表現'

 

17-33問目

大きなトピックとして、GROUP BY, ORDER BY, HAVING文と、SUM(),AVG(),MIN(),MAX()などの集計関数が出てきます。また、Rank(), Row_number()といった少しハイレベルな集計関数も出てきます。

GROUP BYと集計関数を使うことで、とあるカラムに注目して、集計ができるようになります(例:genderに注目して、異なるgenderごとに売り上げの合計や平均を取るなど)。

ORDER BYでは行の順番を指定します。例えば、売り上げの合計が大きい順に顧客IDを表示できたりします。

また、GROUP BYとセットで使用されるHAVING文があります。これはGROUP BYで着目するグループに条件を課すことができる点でWHEREに似ています。例えば、顧客毎に売り上げの合計を算出する時、そもそもIDがZで始まる顧客は非会員なので計算から除外する場合などに使います。

 

34-44問目

大事な構文として、WITHとJOINそしてUNIONが出てきます。

WITH句はいったん集計して一時的な表を作るもので、その後最終的な表や数値を出すために使います。たとえば一旦WITHで顧客ごとに今までの売り上げを合計しておき、最終的には顧客ごとの合計売り上げの平均を取ることで、顧客一人あたりの売り上げを出すといったクエリを書くことができます。

JOINは複数のテーブルを(横に)統合することができます。例えばreceiptというテーブルにはカラムとして商品が売れた日時と売れた商品の商品コードがあり、productというテーブルにはカラムとして商品コードと商品の名前が書かれているとします。これらreceiptとproductというテーブル二つを共通のカラムである商品コードを参照として統合することで、いつなんという名前の商品が売れたのかという新しいテーブルができることになります。JOINにはINNER JOIN, LEFT JOIN, OUTER JOINなどの種類があり、それらの違いを理解していくことも重要です。(ちなみにPostgreSQLでは何もついていないJOINはINNER JOINとして解釈されます。)

UNIONは複数のテーブルを縦に結合する(つまり単純に行数を増やす)ものです。このノックで2-3回だけの出番でした。

 

また、Tableを作る、消すといった作業が必要になる問題も問題43で出てきます。

 

そのほかの重要な概念として、NULL値が入っていた場合に補完できるcoalesce()、時系列データなどで集計の際、n個手前の時刻(行)の数値を参照できるlag()、条件分岐に応じて入れる数値を指定できるcase文などが出てきます。もちろん、それ以前に用いた構文等もフル活用するので、このあたりから少しづつ難しくなっていくかと思います。焦らず復習するなどして、少しづつ理解していきましょう。

 

45-74問目

DATE型、timestamp型といった時刻を表すデータの扱いと、文字列型の扱い、そして標本標準偏差や対数、小数点切り捨てといった数値を計算する問題が並んでいます。必要なものは多岐に渡るので、また個別の解説を書く際に詳しく言及しようと思います。特に時刻は関数もたくさんあり、引数の違いなどにも気を使う必要があります。

また、既出の構文ですがcase文を用いて、ダミー変数を作るという問題も出てきます。機械学習系の人にはよく使う技術の一つですね。

 

 

75-88問目

サンプリングや欠損値の比較、そして欠損値の補完や名寄せといった実務上とても重要なものが出てきます。またここでは、nestされたカラムというのが初めて出てきます。ちょっとややこしい概念の内の一つだと思いますが、ここでしか出てこないようです。新しい概念を一度の問題で複数学ぶ必要も出てきうるので、一つ一つ丁寧に理解していく必要があります。わからない場合は思い切って飛ばして後で戻ってくるのも良いかと思います。

 

89-100問目

データセットの作成や、ファイル出力といった問題が並んでいます。問題43や80で使ったテーブルの作成方法を思い出しつつやっていきましょう。データセットの作成にはサンプリングをするのでやはり今までに習ったことを使う必要があります。早く終わらせたくなる気持ちはわかりますが、これを機に復習しつつ進めてみてください。

 

 

くどうれいん『うたうおばけ』

歌人くどうれいんさんのエッセイ集。ISBNがついていない『わたしを空腹にしないほうがいい』をやっと手に入れて読んでとても良かったので、今作も見つけた瞬間購入を決めた。

 

食べ物がテーマの前作と違って周りの人にフォーカスした作品が多かったように思う。最近短歌が気になっていて、特に自分+/-10歳くらいの世代の短歌を読みあさっている。初谷むい、九螺さらら、千種創一とか。自分の中の感覚に近いけど自分では思いつかないような感性を見つけるのがとても良い。くどうさんのエッセイにも似たものを感じる。

 

特に自分が好きだったのはお婆ちゃんの話だ。おれもこんなお婆ちゃん欲しい。あんまり試し読みせずにエイヤッと買って読んで欲しいが、出版社のnote.comからこの話は読めるということを後で知った。(note.comの連載は読んだことがなかった)

 

https://note.com/kankanbou_e/n/nca5906988281?magazine_key=m332e3bb4947d

 

くどうさんの短歌を残念ながらあまり読んだ事がないので、今度はそちらも読んでみたい。

Kaggleの"Intro to SQL"をやってみた

自分用メモ。ドットインストールの動画をさっと眺めたぐらいでSQLを触ったことがなかったが、勉強がてらやってみた。とりあえず無料のものでいい&自分の環境でやるのはめんどくさいので、Kaggleのチュートリアルを使うことにした。

 

Learn Intro to SQL Tutorials | Kaggle

 

SQLとBigQuery

SQLにはいくつか種類があることは理解しているが、MySQLとPostgreSQLの違いが何かとか、まったくわかっていない。細かい違いはあるがたぶんここに出てくるような公文で大きな違いはないっぽい。KaggleのSQLはGoogle BigQueryを使っているらしい。

 

SELECT, FROM, WHERE

SELECTで引出したい項目を、FROMで対象となるテーブルを、WHEREで条件を指定する。

SELECT * 

FROM table

WHERE country=US

でcountryの項目がUSであるsub tableが生成される。

 

GROUP BY, HAVING, COUNT()

COUNT()は数を数える。たとえばCOUNT(ID)とあるとIDの数が何種類あるか数える。ID0-99までの顧客リストがあるとCOUNT(ID)は(IDが重複していない限り)顧客数100を返す。SUM()などと同様にこういう複数の値から一つ値を返す関数なのでaggregate functionという。

GROUP BYはCOUNT()の結果を種別に返す。たとえば先ほどの顧客リストにregionという項目があって関東、関西などとある場合、COUNT(ID) とGROUP BY regionによって

関東 25

関西 19

東北 13

...

四国 1

などというような地域別のID数(顧客数)を表示できる。

HAVINGは条件式である。GROUP BY region HAVING COUNT(ID)>1で顧客数が2以上の地域別顧客リストが返る。なのでさきほどの例で言えばリストから四国(IDが1なので)が消える。

 

COUNT(1)で行の数を数えられる。

 

 

ORDER BY

順番を決められる。DESCで降順。なのでORDER BY COUNT(1) DESCで個数順

 

AS WITH

ASはaliasだが、WITH...ASと合わせることで一時的なtable(Common Table Expression, CTE)を作ることができ、可読性をあげることができる。

query_with_CTE = """ 
                 WITH Timetable AS 
                 (
                     SELECT DATE(timestamp) AS trans_date
                     FROM `bigquery-public-data.bitcoin.transactions`
                 )
                 SELECT COUNT(1) AS transactions,
                        trans_date
                 FROM Timetable
                 GROUP BY trans_date
                 ORDER BY trans_date
                 """

のような感じ。例えばたくさんのトランザクションのデータから、顧客ごとに合計額を算出して、それから全顧客に対して平均をとるような処理などに使える。

 

Joining data

pandasのmergeのような感じ。複数のtableをid等を目印に統合する。left join, full joinなどの種類がある。

 

実際全部やるのに5時間くらいだったと思う。Advanced編をやったり、100本ノックをしてみたい。

Learn Advanced SQL Tutorials | Kaggle

 

github.com

AtCoderで緑色になったので振り返りつつ数理科学系大学院生に趣味としてオススメする

はじめに

f:id:ekotto32:20200520092440p:plain

先日のAtCoder Beginner Contest(ABC)168で今年の目標にしていたランク緑色まで到達しました!AtCoder界隈では、色変記事といって、ランクが上がったときに自分が何をしたか振り返り記事を書くようで、多数の良記事があります。私も書こうと思ったのですがせっかくなので振り返りをしつつ、私のもう一つのコミュニティであるポスドク・大学院生に「AtCoder・競技プログラミングは院生の趣味の選択肢として結構アリだと思う」という記事を書きます。

私自身、AtCoderを本格的に始めたのは5ヶ月前でもう既にポスドクをやっていましたが、大学院生時代からやっておけば(サービスをそもそも知らなかったのですが、AtCoder自体は2012年あたりからあるようです)よかったなあと思ったので、この記事を書きました。

 

そもそもAtCoderとは?(競プロ勢は読み飛ばしてください)

AtCoderは競技プログラミングのオンラインコンテスト開催サイト名であり、そのサービス(AtCoder jobsのように就職支援も含まれます!!)を提供している会社の名前です。コンテスト参加は無料です。必要なのはPCと電気代と通信費だけです。PCも高いスペックは必要ないです。

コンテストは(典型的なABCと呼ばれるものだと)100分間の間に問題A-Fの6問出題され、解いた問題に応じて得られる点数の合計およびその速さを競うものです。問題文があって、それにそった入力を受け取り、答えを出力するプログラムを書いて、提出すると、20ケースほどのテスト入力にたいして正しく出力されているかチェックされ、全てのテストに正しい答えを出した場合問題クリアとなります。同じ点数を取ったユーザー間では最後の問題を解いた時間+間違えたプログラム提出数に応じたペナルティ時間で順位がつけられます。

atcoder.jp

規程時間終了後、順位に応じて「パフォーマンス」という数値が計算され、今までのコンテストのパフォーマンスに応じて「レーティング」という数字が決まります。レーティングに応じて複数の色(段位みたいなもの)に分かれていて、下から灰色、茶色、緑色、水色、青色、黄色、橙色、赤色...となっています。ランクに応じてどんなスキルが身に付くのか、詳細については、下のAtCoder社長さんのブログが良いと思いますので、ご参考ください。

chokudai.hatenablog.com

AtCoderは日本のサイトなのですが、同様の海外サイトで著名なものにCodeforces、Topcoderなどがあげられます。他のサイトのコンテストに出ていないので詳細な言及は避けますが、問題文が英語である、開催時刻が日本時間の夜中になる可能性がある、コンテストのルールや開催頻度が異なるなどの違いがあるようです。ちなみにAtCoderの人気はうなぎのぼりのようで、最近のコンテストには海外からの参加者も含め、10000人以上が参加しているとのことです。

良い成績を残すには、もちろんプログラミング能力(アルゴリズムや計算にかかる時間を考える、バグらずにコードを書く)も問われますが、所謂一般的な数学の知識(高校数学~大学基礎科目くらい?)も問われる場合があります。例えば前回は時計の針(分針、時針)の間の距離を求める際に、三角関数の知識を用いる問題がありました。もちろん高校で習う知識なので大半の参加者(中学生とか若い参加者もいらっしゃいます)は最低でも三角関数を「知っている」状態ではありますが、「いつも使っているのでパッと解法が浮かんでくる」とスピードの面で有利です。数理科学系の大学院生だと、こういったところにアドバンテージがあるかと思います!

atcoder.jp

もちろん、数理的な能力・プログラミング能力だけではなくて、解法を思いつく発想力や、典型例を応用する能力、また、よりメタな能力として新しいことを学ぶ力が鍛えられるかと思います。競技という側面はありますが、自分との戦いという面が強く、コミュニティの中でいろいろと解説を出してくれている競技者の方がたくさんいらっしゃいますし、ランクが上がった場合(Twitter等で報告すれば)皆に祝福されます。コツコツとやっていってランクが上がったときの楽しさはあつ森を超えます(当社比)!!

個人的には学んだことが直接役に立たなくてもいいかなと思っていますが(趣味なので)、実際には「あー大学院生時代にこれ知っておけば〇〇のコードもっと速くなったかもなあ」といった件も存在しました。一個人の考えですが、研究は思い通りに進まないものなので、大学院生時代には「研究と違ってやったらある程度進捗があって気分転換になるもの」を趣味とするのはより良い大学院生活を送る一つの方法だと思います。競プロは(もし、自分に合っているなあ、と思うのであれば)ストレスをそこまで貯めずにかつ「趣味だけど、ある程度実用性もある」くらいのポジションでいてくれるので悪くない選択かと思います。

もちろん、同じ数理科学系の大学院生の中にも多種多様な人がいて、素養があって楽に上に行ける人もそうでない人もいるのは重々承知しています。個人に必要な努力の質や量は目標にも応じて変化します。無理のない範囲でやってみる、くらいのスタンスがお勧めです。

と、いうわけで勧誘はこのくらいにして自分の開始当時の様子や緑色に上がるまでやったことをつらつらと書いていきます。 

 

自己紹介(AtCoderはじめる前はどんなだったか)

AtCoderを始める前の自分を思い返してみると、

研究で必要だったので、独学でC++をやっていた(授業等で、体系的に学んだ経験がないので、知識がちぐはぐ)

物理をやっていたので、高校-大学基礎くらいの数学は馴染みがある。最大公約数・最大公倍数がなんたるかはわかっているし、三角関数もわかる。整数問題も(わかるというと語弊があるのですが)苦手ではない。Nが素数であるか判定するのにはSqrt(N)に比例した時間でわかる、というのがわかる。「グラフ」というのが界隈では図を意味するのではなく、辺と頂点によるアレだと認識している。(AtCoderは整数やグラフに関連した問題が多い。最初から知っている必要はないけど苦手意識がない方が楽しくできる。)

標準入出力はできる。四則演算+商の余りを求められる。if, for文は書ける。配列というものを知っている。STL(C++についてる標準ライブラリ)はvector(可変長配列)ぐらいしかしらない。文字列の編集はあまり知らない、substr()は知っている程度。文字から数値、数値から文字への変換もググらないと思い出せない。

計算量という概念は知っている。ランダウの記法(O(n)とか)も物理で似たような議論があるので知っている。実際に計算量を気をつけてプログラミングした経験は指折り数える程度。

(余談ですが計算量という概念について、以下の記事が面白かったです。実務でも大事な時がある。)

qiita.com

再帰という概念は知っているけど、実装したことはない。累積和、幅優先探索(bfs)、深さ優先探索(dfs)、動的計画法(DP)についても言葉を知らなかった。貪欲法という言葉は知らなかったけど、こういった素直なアルゴリズムは自分で時間をかければなんとなく実装できるくらいの感じ。しゃくとり法、いもす法、ダイクストラ法などは今でもあんまりできない。Unifon Find木やセグメント木もできない。

タッチタイピングがあまりできない。速くないし、ミスも多い!(NとMを打ち間違えていることに気づかず、ペナルティでパフォーマンスを約10%損したことがあります)(でも、典型的なコードを先に作っておいて、コピペして最小限を手打ちにすることである程度カバーできます。)

個人の傾向として、簡単な問題を人より速く解くのは得意。難しい問題をじっくり考えるのが苦手。

といった感じだったと思います。いくつかの専門用語が出てきてこれからAtCoderをはじめようかと気になっている方はギョッとするかもしれませんが、5ヶ月前の私もDPとかセグ木とか聞いたこともありませんでした。焦らず少しずつ学んでいければ良いので、あまり過剰に身構える必要はないかと思います。

 

AtCoderを始めた頃~茶色まで

昨年の夏くらいに何も知らずにAGC(AtCoder Grand Contest、難しい方のコンテスト)に出て、一回挫折しかけましたが、年末からコツコツABCをやり始めました。Ratedコンテストに出た回数はそこから数えると緑色になるまで18回です。最初のコンテストは37分3完+4ペナ(×5分)=57分で、茶色のパフォーマンスだったようです(この回のC問題は比較的素直な問題で、運がよかったです)。

手元で環境構築はしていなくて、AtCoderコンテストサイトのコードテストページに打ち込んでやっています。キルリングとか補完が使えないので、本当は手元で環境を整えてやる方が良いと思います...ただ、プログラミング始めた頃に私が嫌だったのが環境構築なので、そういった意味では本当に初心者でも気にせずに始めることができるのが良いところです。

その後7-8回かけて茶色まで行きました。AtCoderは参加コンテスト数が少ないうちはレーティングが低めに出る補正がかけられているので、最初のうちはあまりレーティングは気にせずに個々のコンテストの結果(=パフォーマンス)を気にしていました。また、どうしてもコンテスト形式の慣れは必要です。もちろんプログラミングの中身も大事ですし、自分の実力を伸ばすことがまず大事ですが、落ち着いた回答を心がけたりミスをしない仕組みづくりをするなど、総合力でコンテストで良い結果を出すようにしていました。といっても最初は全然ダメで、例えば(もう二度とやらないと誓っていますが)開始20分後から参加して(同じ問題を解いた場合速さで決まるので)順位が大きく下がってレートを下げてしまったこともありますし、コードテスト(後述)をしないまま提出してしょうもないミスをしたことも多々あります。

コンテストを解く際に気をつけていたこととして、コードの内毎回書く部分は予めどこかにストックしておいて、コピペしていました。極力タイプミスをなくすためです。また、典型的な〇〇というアルゴリズムを使えば良いとわかったが実装したことがない際に他人のコードをコピーして問題に合うように修正したりしていました。コードの中身を一行づつ理解できていれば問題ないかと思います。AtCoderの一つの問題に対して書くコードは(我々のようなレベルの問題では)そんなに長くないので、新しい概念でもその場で動くプログラムを組む状態まで持っていくことは可能だと思います。

めんどくさいんでA問題とかスルーしたくなりますが、コーナーケース(業界用語で入力な極端な場合という意味だと思います)で間違った答えを出したり、先述のしょうもないミスをしたりするので、コードテスト(問題に含まれている入力例に対して出力例を正しく返答できるかチェック)しておくのは大事だと思います。戦略として「AB問題早とき!Cはどうせ解けない!」といったことを行う場合にはもしかしたら数秒を争うのでコードテストの時間を端折りたくなりますし、わたしもそうだったのでわかります。ただ、ペナルティが5分なのでそこが大きすぎることを考えると、きちんとテストして提出する方が良いと思っています。

コンテストが終わった後の復習として解説pdfを読むのはオススメです。もちろん時間をかけて解説動画をみた方がきっと良いのですが、そこは解説を読んでもわからなかったら、という形か、あるいは数日後にググって他の方の記事を読んでみるというのも良いかとも思います。基本的にB問題まで解けたらC問題、C問題まで解けたらD問題だけ復習しました。自分がギリギリ解けなかった問題だけ復習して、それ以上の問題は(コンテスト中にCが解けなくて時間をかけてDを考えたけどやっぱダメだった、みたいな場合にC,D両方解説読んだことはありますが)基本的には時間を割く必要はあんまりないかと思います。

いわゆる精進と界隈で言われますが。そういった過去のA問題全埋めやB問題全埋めは行ませんでした。全部解いていたら時間の割りに(それなりにわかっている問題も多いので)得るものは少ないかなと思っていました。ただこれも工夫次第で、多様な問題に触れることを念頭に、各問題をチラッと見て、実装したことないような解法があれば練習がてらやってみる、というのをやっても良かったかなと反省しています。

茶色になるころには、文字列の操作について昔より詳しくなりましたし、mapやvectorなどのC++のSTLを簡単な場合ならスッと実装できるようになりました。「昔の研究の〇〇の場面でこれ知ってたらもっと楽に□□できたかも」と思ったりしたので、茶色になるだけでも(研究で簡単なプログラミングをする場合は)ちょっと役に立つ場合があるかもしれません。

 

茶色から緑色になるまで

Atcoder Problemsというサイトがあって、茶色になるまえから知っていましたが、茶色になったあたりから活用するようになりました。何日連続でAC(Accepted, 正解すること)したか表示される機能があって、これを目安に一日一問解くようにしていました。解く問題の難易度はその日によってマチマチで、時間があるときには自分がギリギリ解けるくらいの問題や、ググって解法を調べないと解けないくらいの問題を解きましたが、時間がないときには簡単に解法を思いつく問題をとりあえず解いていたりしました。「毎日15分くらいでいいのでコツコツ問題に触れる」というのは実力アップにとても重要だと思います。

https://kenkoooo.com/atcoder/#/table/

私の現状の埋まり具合下記のようになっていて、あんまり精進が足りてないのがわかるかと思います。

f:id:ekotto32:20200524052216p:plain

また、chromeの拡張等をつかっていくつかAtCoderサイトの表示をカスタマイズしました。本来であれば茶色になるまえからやっておけば良かったです。

 

greasyfork.org

greasyfork.org

greasyfork.org

どれも好きですが、上二つはコンテスト中により詳細な情報が目に入るので、もしかしたら使いたくない人もいるかもしれません。

茶色になったころ(少し前だったかも?)、それまでAtCoderを始めるまでの貯金でやっていた自分がもうちょっとできるようになりたいと思って、勉強したのが累積和でした。実際Webで検索すると多くの人の解説記事があります。私はいろんな記事でトライして(自分に合った記事を見つけたというよりは、単純にその記事を読んだときにモチベーションが最も高かっただけかもしれませんが)とある記事である程度実装までできるようになりました。記事を読む→コピペでもいいから実装する→見ずになんとなく実装にトライしてみる→ダメだった場合、実装のどこかで論理を理解していないのでそこをやり直す、といったステップを踏んだように記憶しています。早速勉強したそのあとすぐか、あるいはその次のコンテストで累積和を使う問題が出たような記憶があります。

茶色になってからもう少ししてできるようになったことで一番本質であったと現在思っているのが、全探索です。もともと、情報系やコーディング畑ではないので、どちらかというと長いコードをしっかり書いて探索するよりは発想でうまく計算の楽をすることを念頭に置く、きれいに問題を解きたいタイプでした(「ハンマーを持つと問題が全部釘にみえる」に通ずるところもあります)。しかし、全探索で間に合うのにそうやってしまうのは競技プログラミングの基本からはちょっと外れてしまうのかな、と思うようになり、問題をみるとまず全探索できるか、というのを検討するようになりました。本質的な技術というよりは意識の問題が大きかったと思いますが、最初はこれが本当にできていなくて、AtCoderに慣れてきて茶色になれた頃から少しづつ意識的に問題をみるようになりました。全探索できるかという点においては計算量という概念が必要で、元々計算量についてはなんとなく知識がありましたが、解説記事等一通り眺めて勉強しなおしました。問題をみてしっかりコードを書けば時間内に全探索できるケースだ、ということが判断できるようになったのがレートを上げるためには一番大きかったと思います。

その他のアルゴリズムについて話しておくと、私のやったことの中にDP,DFS,BFSがあります。動的計画法(DP)については、茶色になった後累積和を学び終えたころにQiita等を参考にして簡単な問題について実装してみました。複数の解説記事があがっているので、各々が合う記事をみつけてやってみるのをお勧めします。深さ優先探索(DFS)、幅優先探索(BFS)についても同様です。DPをやってこちらに移るのが理解がより容易になるかと思います。もちろん実装できたり手法自体を理解したりすることも大事ですが、問題をみて「「最短経路」と問題にあるし、BFSかも?」とか「全通り試すにはDFSが使えそうだな」といったように、どういう場合にこの解法に落ち着くのか、といった判断を行えることがまず大事だと思います。

ダイクストラ法や、しゃくとり法など、典型的なアルゴリズムは他にも何個かありますが、私はまだできていません。緑色になるために全てを知っている必要はないですし、同じ緑の人でもきっとできることはそれぞれ違っているかと思います。コンテストにたくさんでそうなものから覚えた方が、自分のレーティングが上がる機会もそれだけ増えるのでアプローチの一つかと思います。あるいは、自分がとっつきやすいものから取り組んでいくのもモチベーションを保つ上で一つの手かもしれません。緑色の次の水色になるには典型的な解法・アルゴリズムのほとんどをある程度こなせる必要があると思っていて、それが緑色から水色にあがることが特に難しいと(個人的に)思っていることの一つです。

 

まとめ&これから

というわけで、AtCoderと自分の今までの取り組みについて簡単に紹介してきました。個人差はありますが、緑色までは自分の得意なことだけ(私で言えば簡単な問題の早解き+少数の典型アルゴリズムの習得)である程度進めると思います。もちろん、大学院生の中にも多種多様な方がいらっしゃるので一概に言えませんが、特に数理系の方で競技プログラミングの面白さに目覚めるかたは一定数いると思います。研究に役立つこともありますがかといって近すぎもせず、私個人としては息抜きとして良い選択肢でありつつ、楽しんで学び続けられたと思っています。あまり目線を高くせずに、まずは茶色や緑色を目指して気軽に無理のない範囲で時間のある週末に参加してみることをお勧めします!

ただ、個人的に趣味としては「楽しい」「負担にならない」などが重要だと思っています。もちろんどんどんレベルが高いところを狙う段階になってくると逆に苦しくなることもあるので、個人の判断で適度にやめるのも良いかと思います。

私個人としては、もちろんうまくいかなかった時の苦しさはなかったといえば嘘になるのですが、目標を達成したときの面白さを感じたので、これからも頑張って次の水色を目指したいと思います。とはいってもここからは一段と厳しいのは重々承知しているので、焦らず半年くらいかけてコツコツとやっていきたいと思います。データ分析コンペであるKaggleに出てみたいという目標もあるので、そちらと折り合いを付けつつ、うまく時間を割り振っていけたらいいなと思います。

思えば今まで二回ほどABCDを素早く解いて水色パフォーマンスを出しましたが、E問題を時間内に解いたことはないので、Dまで落ち着いて素早く解けるようになりつつ、時々Eを解けるようになりたいなと思っています。DP,DFS,BFSといった典型アルゴリズムについて、まだしっかり自分のものにした感覚はないので、関連した問題を解いて精進していきます。

参考文献

学習する上でお世話になったもので、上記以外の物をお礼も込めてリストアップしておきます。

qiita.com

qiita.com

上記二つは最初に読んでみるとイメージがわくかもしれません。

 

qiita.com

この記事は「便利ツール」の欄でお世話になりました。

 

下記はいろいろな解法を調べるときにお世話になっています。

drken1215.hatenablog.com


qiita.com

 

qiita.com

 

最後に色変記事について、すべてが自分にとって正解とは限られませんが、atcoder 〇〇色と検索するとその色になった人等の記事がたくさんヒットすると思います。また、単純に中身関係なく他のプレイヤーの成功をみるとモチベーションアップにもなると思います。

AtCoderで茶色から緑色に上がるには何を勉強すればよいか - テストステ論

AtCoderで緑色になりました - Qiita

 

こういったメタな情報を集めやすくなって皆の実力が上がっていて、とある色になるまでの実力がどんどん上がっていっている?という話もあるようです。事実かどうかはわかりませんが。良いことも悪いことも含んだ話かもしれませんが、何か考えるとっかかりがあることは初心者にとってはありがたいことだと思いますし、私自身他の方の解説記事がなければ緑色に来られなかったでしょう。自分の力で情報を集めて、自分の糧にできる人が伸びて行きやすいのかもしれません。

Python実践データ分析100本ノックのノック35で困ったとき

Python 実践データ分析100本ノックのノック35で

ValueError: Grouper for 'is_deleted' not 1-dimensional

と出て困ったときのメモ。

 

ぐぐるとどうやら"is_deleted"というカラムがpandasのdataframeの中に重複してできているのが原因らしい。

 

customer_clustering = pd.concat([customer_clustering, cust], axis=1)
customer_clustering = customer_clustering.loc[:,~customer_clustering.columns.duplicated()]
customer_clustering.groupby(["cluster","is_deleted"],as_index=False).count()"customer_id","is_deleted","customer_id"

 

のように間に重複を取り除く処理を行えばうまくいく。

AtCoder Beginner Contest 167 D問題 ループ構造を捉える

問題へのリンクはこちら

 https://atcoder.jp/contests/abc167/tasks/abc167_d 

 

街1からスタートして、N個の街をK回移動していく。K回の間に行かない街もありえる。問題はKが最大10^18と大きいので、愚直に計算していくと間に合わない、ということだ。

 

計算量についての一般的な話は下記のけんちょんさんの記事参照。

qiita.com

 

一方、Nは2×10^5と十分小さい。K>Nの場合、鳩の巣原理から、いくつかの街を複数回訪れることがわかる。そして、とある街にいる際に次にいる街は必ず定まることから、最後は閉ループになっていることがわかる。

 

例えば例1を考えてみると、街1→街3→街4→街1→...

とループしている構造に見える。これから、Kをループ内の個数で割ったあまりを考えたら計算量を楽できそうという予想がつく。

 

例えば3N回移動したときはいつも街1にいる。3N+1なら街3、3N+2なら街4だ。

 

f:id:ekotto32:20200510232250p:plain

入力例1の街を辿っていった際の構造。

 

 

この問題は例が優しいので、次に入力例2を見ると、より問題への理解が深まる。

 

次は

(街1→街6→)街2→街5→街3→街2→...となっていて、ループの中に入るまでに二つの街を経由している。一度ループに入ったら出てこないので、ループ前の街をうまく考えてあげて、ループに入った後の移動回数をループ内の町の個数で割った余りに着目してあげれば良さそうだ。

 

f:id:ekotto32:20200510232706p:plain

入力例2の場合のループ構造

 

 

そこで、町の順番を把握するためにwhile文で街1からスタートして、一回行ったことがある街までたどり着くまで街の順番を覚える。ここでは例えば可変長配列vに訪れた街の番号を詰めることを考える。N<2×10^5なのでこの計算は十分早く終わる。

 

ループ前の街の個数をN_out、ループ内の街の個数をN_loopとすると、K-N_outがループの中で移動する回数であることに気をつければ

d=(K-N_out)%(N_loop)でループ内での移動後の位置がわかる。

さっきの町の順番の配列vには、ループ前の街も含めて考えている。そこで、v[N_out+d]とすれば答えの町の場所がわかる。