データサイエンティストが競技プログラミングをやるべき理由
前回の記事からだいぶ時間があいてしまいましたが、平成最後ということでひとつ書かせてください。
はじめに
先日登壇した勉強会で「データサイエンティストはエンジニアリングスキルを高めるべき」という趣旨の主張を展開した上で、「エンジニアリングスキルを高めるために競技プログラミングをやっている」と言ったところ、参加者から以下の質問を頂きました。
「競技プログラミングと実務のエンジニアリングはどのように関係があるのですか？」
本記事では上記の疑問に対する自分なりの考えをまとめていこうと思います。
アルゴリズム重視や可読性の低いコードばかりで実務に役立たないと思われがちな競技プログラミングですが、実はいろんな側面で業務に役立つことを学ぶことができます。
今回の記事はエンジニア全般を対象とした話をするので、データサイエンティストでない方にも読んでいただきたい内容になっています。
以下に当てはまる読者には特に刺さるかもしれません
- 周りと比べて仕事が遅い気がする人
- なんとなく勢いで進めた結果、手戻りしがちな人
- 問題・仕様の理解に時間がかかる人
目次
競技プログラミングとは
競技プログラミングとは、プログラミングを使って速く・正確に・多くの問題を解き、その結果を競う競技です。現在、世界中でオンラインコンテストが実施されています。
有名なところだと Topcoder, Codeforces, Google Code Jam などがあります。
とりわけ日本で競技プログラミングの話がされる場合は、Atcoderというオンラインコンテストサイトが連想されることが多いです。Atcoderは日本語で問題が出題されることが特徴で、毎週末開催されるコンテストには約5000人がエントリーしているほど有名になってきました (2019/04時点)。
Atcoder Beginner Contest 124 より
ほとんどの競技プログラミングサイトではオンラインジャッジという仕組みが採用されています。これは出題された問題に対するソースコードを提出すると、問いの条件を満たすようなテストケースを自動でチェックしてくれるというものです。提出コードがすべてのテストケースを満たしていて、実行時間も制限時間内だったとき初めてその問題をクリアしたことになります。
オンラインコンテストでは100~120分という制限時間の中で、複数の問題を世界中の人と同時に解き、その結果を競います。
競技プログラミングで身につくスキル
競技プログラミングで身につくスキルは、開発の各フェーズで必要とされるスキルにかなり近いです。まずは開発業務にどのようなフェーズがあるのか確認していきます。
開発を行う時のフェーズはおおよそ以下のようになります。
これをベースに、競プロでどのようなスキルが身につくのかをみていきましょう。
仕様の理解
問題や仕様の理解はコンテストにおいては最も重要なポイントです。問題の理解を誤ったまま先に進んでしまうと、すべて最初からやり直しとなってしまいます。これでは素早くたくさんの問題を解くことができません。仕事で炎上するときもだいたい認識の齟齬が原因ですよね。
問題読解能力は国語力でもあり、業務を行う上でもとても大切なスキルです。競技プログラミングを始めると、問題文から瞬時にイメージを正確にとらえるスキルを身につけることができます。
例えば次のような問題があります。
Atcoder Beginner Contest 125 より
上級者であれば瞬時に理解して実装に落とし込めるようですが、私は凡人なのでまず紙でイメージを書き出します。
この問題では隣り合ってる数字のペアの正負を何回でも操作して入れ替えられるよということなので、それを書き出すとこんな感じになります。
全ての数字を正にすることができました。入出力例と合っているのでこの解釈で間違いなさそうです。
もうひとつ例を書くと
今度は全ての数字を正にすることはできず、１つだけ負の数字が残っています。
このように問題を理解し、イメージをアウトプットすることが大切です。チーム開発などでは認識齟齬が致命傷になることが多いですが、実際の業務でも仕様を理解してイメージをチームメンバーと共有することが大事だと思います。競技プログラミングを始めてから、このような作業が速く・正確に行えるようになった気がします。
実装設計
問題の理解ができたら、次は実装方針の設計を行います。特にデータサイエンティストの人はこの設計をせずにコードを書き出してしまう場合が多い*1ですが、開発では設計を必ず行いましょう。もっとも競技プログラミングで上位を目指すのであれば設計をしている暇なんてありませんが…慣れるまでは急がば回れで堅実にやっていきましょう。
「仕様の理解」パートで、この問題設定では以下のパターンがあることがなんとなくわかりました。
- すべての数字を正にできるパターン
- １つだけ負の数字が残ってしまうパターン
ここで、いくつか入力例を書き出してみます。
-10 5 -4 → 10 5 4 → 19 10 -4 -8 -11 3 → 10 4 8 11 -3 → 30 10 -5 2 8 → 10 5 -2 8 → 21 9 -4 3 -1 5 → 9 4 3 1 5 → 22
ここまで書くと、以下のことがわかります。
- 負の数字が奇数個のとき ⇒ １つだけ負の数字が残ってしまう
- 負の数字が偶数個のとき ⇒ すべての数字を正にできる
つまり、以下のような設計方針を立てることができます。
- 負の数字をカウントする
- 負の数字カウントが偶数なら、入力数列の絶対値の和をとる
- 負の数字カウントが奇数なら、入力数列の絶対値の和から最小数の絶対値 * 2 を引く（既に足した分も引くため）
また、コンテストでは実行時間制限が設けられているため、おおまかな計算量を試算しておく必要があります。頑張ってコードを書いて回した結果、計算時間オーバーではもったいないです。
今回の方針は、入力列(長さN)に対して1回のループを回すためO(n)で解けそうだということがわかります。
テスト設計
前段でテストパターンを洗い出したものの、これで全パターンを満たせているでしょうか？
競技プログラミングでは全てのテストケースを通過しなければ、正解とはなりません。さらに、Atcoderではミスをおかす度にペナルティが付与されてしまうため、テストケースに漏れがないかよく確認したいところです。
実装する前にテスト設計を行う理由としては、テストパターンに漏れがあった場合に実装方針に影響が出てしまうからです。手戻りは未然に防ぎたいですよね。
先の例で、入力パターンをいくつか用意して設計を行い、これを実際のテストパターンとして使う開発手法はテスト駆動開発と呼ばれていたりします。テスト設計と実装設計を同時にやってしまうようなものなのですが、テストパターンが完璧に押さえられている場合は、これを満たすようにロジックを実装するだけなのでとても楽で確実です。
前章で列挙した入力パターンを確認すると、どうやら0が入るパターンを考慮できていなかったようです。このパターンでは、負の数字カウントが奇数なのにもかかわらず全ての数字を正にすることができています。
テストケース漏れ？？と思いましたが、そもそも0が入る場合は最後に引くものがないため問題なさそうです。
負の数字カウントが奇数なら、入力数列の絶対値の和から最小数の絶対値 * 2 を引く（既に足した分も引くため）
符号が変わるポイントは忘れがちなので、与えられる数字の範囲に注意してテストケースを設計したいです。念のため新たな入力例もテストパターンに加えて準備万端です。あとは、これらのテストケースが全て通るようなコードを書くだけです。
実装・テスト
多くのオンラインコンテストでは、好きなプログラミング言語を選んで実装することができます。高速で実行ができるという点で、C++を使っている方が多いですが、実務で使っている好きな言語で書けば良いと思います。
実装方針はすでに立っているので、実装をしていきましょう。
以下が私がPythonで書いたコードです。
# read input n = int(input()) x_list = [int(i) for i in input().split()] minus_count = 0 abs_list = [] for x in x_list: if x < 0: # x is minus minus_count += 1 abs_list.append(abs(x)) # take abs if minus_count % 2 == 0: # minus_count is even print(sum(abs_list)) else: # minus_count is odd print(sum(abs_list) - 2 * min(abs_list))
競技プログラミングはプログラムを書くことがメインだと思われがちですが、実は実装に入るまでにほとんどのことは終わっています。上記のコードはプログラミング初心者でもぐぐったら書けるレベルですし、初心者向けの問題であれば実装の高度なテクニックは求められません。
他にも、Atcoderではいろいろな人のコードをみることができます。例えば以下の例は、同じ方針を短いコードでまとめあげています。
n=int(input());a=list(map(int,input().split()));c=0 for i in range(n): if a[i]<1:c+=1 a[i]=abs(a[i]) a.sort() print(sum(a) if c%2==0 else sum(a)-2*a[0])
最後に、用意した全てのテストパターンを通過することを確認しコードを提出します！
まとめ
競技プログラミングで得たスキルと実務の開発がどのように関係しているかということについて紹介しました。
仕様理解、設計、実装、テストという流れは一般的な開発フローと似ていますし、アルゴリズムや実装テクニックといった部分以外にも実務に役立つことをたくさん学ぶことができます。実装に入るまでにほとんどのことが終わっていると書きましたが、実務でもこのように仕様理解と設計をしっかりと行うことが早く仕事をこなす近道だと思います。急がば回れです。
今回はアルゴリズム以外の部分に着目しましたが、今後はアルゴリズムや計算量を意識した実装に関する記事を書ければいいなと思います。
*1:Jupyter notebook の副作用でしょうか…
