この記事はNuco アドベントカレンダーの6日目の記事です。
駆け出しエンジニアがまずやるべきこと
今あなたが駆け出しのエンジニア、あるいは未経験からエンジニアを目指そうとしている方であれば、当然ながら一通りの基本的なスキルを備えている必要があります。
何らかのプログラミング言語やSQLの文法、Gitの初歩的なコマンド、その他コンピュータサイエンスの基礎知識などがそれにあたるでしょう。
私はそれらに加えて競技プログラミングの勉強を強くお勧めします。
競技プログラミングとは
競技プログラミング(通称:競プロ)とは、数学的な思考力を持ってプログラミングによって問題を解く競技です。
国内のコンテスト運営会社ではAtCoderが最も有名でしょう。ほぼ毎週末、21:00からオンラインで参加費無料のコンテストが開かれています。
他にもyukicoderは同じく日本語で運営されていますし、世界的にはCodeForcesやTopCoderも有名です。
「競技プログラミングは役に立たない」論
競技プログラミングは、「プログラミング」と名のつくものの、そこで得られる知識が限定的で実務の場で応用されることが少ないことから、しばしば「競技プログラミングは役に立たない」との主張がなされます。
尤も、今でこそアルゴリズム実技検定が実施されたり、AtCoderを介した求人が行われたり(AtcoderJobs)して、このような言説が見受けられることは少なくなってきていますが、高度なアルゴリズムやデータ構造を初心者エンジニアが実務で使う場が頻繁にあるかと 問われれば答えは依然としてNoです。
しかし、もし駆け出しエンジニアのあなたがこのような根拠から競プロを敬遠しているのであれば、その考えを改めることを強く推奨します。
駆け出しエンジニアにこそ競プロは役に立ちます。
エンジニアに必要な基礎体力がつく
競プロはどのような点で駆け出しエンジニアの役に立つのでしょうか。
それはエンジニアとして働くのに不可欠な基礎体力がつくということに集約されます。
ここでいう基礎体力とは次のようなものを指します。
- 論理的思考力
- プログラマ的思考力
- 実装力
- もっとメタに、考える体力や問題解決力
もちろんこれらの能力を磨く場は競プロには限らないと思います。
数独などのパズルを解いたり、日曜プログラマとして開発をしたり、方法はいくらでもあるでしょう。
しかし、競プロは中でもシンプルで無駄のない学習材料です。
競プロでは「問題を解き、実装する」という純粋なプログラミングの反復演習がスムーズに行えるため、この基礎体力を身につけるのにとても適しているのです。
環境構築やセキュリティなど、基礎体力の観点からは些末で非本質な部分に気を取られることはほとんどありません(裏を返せばこれらの知識は別で補う必要があります)。
実践編
AtCoderを始める
善は急げ。競プロを始めましょう。
基本的にAtCoderに取り組んでいれば十分なので、ここでもAtCoderに絞って解説します。
必要なものは、インターネットにつながったパソコンと、何らかの言語の基本的な文法の知識のみです。
本気で高レート帯を目指すのでなければ言語は馴染みのものでいいです。
その言語の入門書レベルの文法の知識があればすぐに取り掛かれます。
問題を解くまでのステップは、
- アカウントを持っていなければまずは新規登録。
- 標準入出力の扱い方や提出・正誤の確認方法などをpractice contestで確認。
ここまでで準備は終わり。 - 解きたい問題を選ぶ。AtCoder Problemsという非公式サービスでは過去問(過去のコンテストで出題された問題)がまとまっているので便利。
- 問題を解いてコードを書き上げる。
- テストして入出力例に合致しているか確認する。環境構築をしていなくてもコードテストを利用して簡単にテストができます。
- 必要があればデバッグ。問題がなさそうなら提出！
- 解説や他の人の提出を読むこともできます。
勉強するだけなら過去問を解くのみで十分ですが、興味があれば毎週末のコンテストにリアルタイムで参加してみましょう！世界中の競技プログラマと競い合うことができます。
目安としては、AtCoderBeginnerContest(AtCoderで最も多く開催される、初~中級者向けコンテスト)で300点問題が解けるようになってくる頃、レートで言えば茶色中位(500~700程度)の実力ならば、駆け出しエンジニアが備えるべき競プロ力としては十分です。
まずはここを目指しましょう。
例題
AtCoderから、基礎的で、考え方や実装の実用性・応用性の観点からより役立ちそうな問題をピックアップしました。
アルゴリズムを考えるのみでも十分得られるものはあると思いますが、実装し、提出し、デバッグし、AC(正解)する過程にも大きな意味があります。
ぜひ実際に手を動かしてみてください。
例題1
問題文
$1,…,N$ と番号付けられた $N$個の都市と、都市間を結ぶ$M$本の道路があります。
$i(1≤i≤M)$番目の道路は都市 $A_i$と都市$B_i$を結んでいます。
以下の指示に従い、$N$行にわたって出力してください。
都市$i(1≤i≤N)$と道路で直接結ばれた都市が$d_i$個あるとし、それらを昇順に都市$a_{i,1},…,a_{i,d_i}$とおく。
$i(1≤i≤N)$行目には、$d_i+1$ 個の整数$d_i,a_{i,1},…,a_{i,d_i}$を、この順番で空白区切りで出力せよ。
制約
$2≤N≤10^5$
$1≤M≤10^5$
$1≤A_i<B_i≤N\quad(1≤i≤M)$
$(i \neq j)$ ならば $(A_i,B_i)\neq(A_j, B_j)$
入力される値は全て整数
コメント1
実装する上では多次元配列を使う必要があるでしょう。
多次元配列やfor文・if文のネストなどは実務のプログラミングでも避けては通れません。
理論や原理を理解するだけなら簡単かに思えますが、実際に遭遇した際に実装しようとすると案外詰まります。
競プロで日常的に耐性を身につけていれば動じなくなります。
例題2
問題文
整数$X$と、長さ$N$の整数列$p_1,…,p_N$が与えられます。
整数列$p_1,…,p_N$に含まれない整数 (正とは限らない) のうち$X$に最も近いもの、つまり$X$との差の絶対値が最小のものを求めてください。そのような整数が複数存在する場合は、そのうち最も小さいものを答えてください。
制約
$1≤X≤100$
$0≤N≤100$
$1≤p_i≤100$
$p_1,…,p_N$はすべて異なる。
入力中のすべての値は整数である。
コメント2
方法はいくつかありますが、できるだけシンプルで計算量の少ない方法を考えてみましょう。
例えば、$X, X-1, X+1, X-2, X+2...$と優先度の高い順に見ていって条件を満たした時に処理を打ち切るのが良い方法です。
実装は、例えばwhile文でiを0からインクリメントしていきながら$X-i$と$X+i$をこの順に調べることで実現できます。
処理の順番や優先度に意識を向けて適切に実装する必要に駆られることは実務でも多いです。
例題3
問題文
二次元平面があります。$1$以上$9$以下の整数 $r,c$ について、$S_r$の$c$番目の文字が # であるとき座標 $(r,c)$にポーンが置いてあり、$S_r$の$c$番目の文字が . であるとき座標$(r,c)$に何も置かれていません。
この平面上の正方形であって、$4$頂点全てにポーンが置いてあるものの個数を求めてください。
制約
$S_1,…,S_9$はそれぞれ # と . からなる長さ$9$の文字列
コメント3
やや高難度です。
4点が正方形状に並ぶことは、人間が視覚的に判断するのは容易ですが、厳密に数学的な表現に落とし込んでプログラムしようとするとなかなか難しいです。
ここではベクトルを用いながら重複・漏れに気をつけて数え上げましょう。
このように感覚的なやりたいことをきちんとコードにすることは、日々プログラムを書く上で頻繁に訪れます。
実務での応用例
仮想的な実務の現場での応用例を考えてみましょう。
実際に私が遭遇したケースから非本質な部分を捨象したものです。
問題
あなたはGoogleSpreadsheetの自動化を行いたいです(GoogleAppScript(通称GAS)というJavaScriptに似た言語を用います)。
categoryとnameの列を持つソートされた表が与えられます。
いくつかの行を削除することでcategoryとnameのユニークな組み合わせを一つずつ抽出するアルゴリズムを考えてください。
(便宜上、下の例ではcategoryの値とnameの頭文字が同じになっていますが、その保証はないとします。)
ただし行の削除はrowの値を1つ指定することでのみ行われ、行を削除するとそれ以下の行が1行ずつ上に移動するように表が変化します。
| row | (before)category | (before)name | → | row | (after)category | (after)name |
|---|---|---|---|---|---|---|
| 1 | A | Alice | 1 | A | Alice | |
| 2 | B | Bob | 2 | B | Bob | |
| 3 | B | Bob | 3 | C | Carol | |
| 4 | C | Carol | 4 | C | Cameron | |
| 5 | C | Cameron | 5 | D | David | |
| 6 | D | David | 6 | D | Dennis | |
| 7 | D | Dennis | 7 | D | Dick | |
| 8 | D | Dennis | 8 | E | Edgar | |
| 9 | D | Dick | 9 | E | Edwin | |
| 10 | E | Edgar | 10 | E | Edward | |
| 11 | E | Edwin | 11 | F | Fred | |
| 12 | E | Edwin | ||||
| 13 | E | Edwin | ||||
| 14 | E | Edward | ||||
| 15 | E | Edward | ||||
| 16 | F | Fred |
この例ではbeforeの状態からrowを7, 3, 11, 9, 11の順に指定して行を削除すると、afterの状態が得られ、beforeからユニークな組を一つずつ取り出した表になっています。
適切な行の削除の仕方は複数考えられますが、そのうちの一つを求めればよいです。
解答例
方法はいくつか考えられます(そもそもGASを持ち出すまでもないかも)が、シンプルなアルゴリズムの一つは表を降順に走査することでしょうか。
GASの行削除メソッド(deleteRow())は、問題文の通りそれ以下の行にも影響が及んでしまうので、このメソッドで$n$行目を削除する時には、「もう$n$行目以下には操作を施さない」状況であるとよいでしょう。
具体的な疑似コードは以下です。
N ← 表の行の数
for i ← N to 2 (iを1ずつ減らす)
if i行目と(i-1)行目が同じ
i行目を削除
この擬似コードに沿うと、上の例では15, 13, 12, 8, 3の順にrowを削除することになります。
もちろんforで前から走査してもできますが、少し考えると添字の扱いが少し面倒になることに気づきます。
for文では多くの場合 i をインクリメントしていきますが、競プロではデクリメントなどのそれ以外の更新もよく使います。
競プロに慣れると、このような細かい添字の取り扱いやシンプルで簡素なコーディングのスキルも自ずと身に付きます。
これこそが競プロで培われる基礎体力の一つです。
おわりに
いかがでしたでしょうか。
競プロの醍醐味は高度なアルゴリズムやデータ構造の知識のもと思考力を駆使して計算量を削減して問題を解くことですが、このように比較的簡単な問題で基礎的な思考力・実装力を鍛えることにも十分有用です。
競プロのスキルはエンジニアの十分条件でこそなかれど、大きな必要条件です。
駆け出しエンジニアの皆さん、競プロを始めましょう。
弊社では、経験の有無を問わず、社員やインターン生の採用を行っています。
興味のある方はこちらをご覧ください。