コーダーのための競技プログラミング入門

ブログ

2018.08.28 コーディング

コーダーのための競技プログラミング入門

ほとんどのコーダーは主に書くのがhtmlとcss、そしてちょっとだけJavaScriptを書いて動きをつける程度かと思う。

そのJavaScriptにしても、ほとんどの場合jQueryプラグインを読み込むだけで完結してしまうことも多い。

その結果いわゆるプログラミング能力が向上しづらく、ちょっとしたイレギュラーなプログラムを書く機会があった時に詰んでしまう人も多いのではないだろうか。Fizz Buzzも書けないエンジニアというのが実在するとかっていう恐ろしい都市伝説を耳にしたこともある。

そこで、プログラミング能力の底上げとして最近アツいのが競技プログラミングだ。採用基準の1つとして利用している企業も増えてきている。

代表的な競技プログラミングサービス

数ある中から有名どころをピックアップすると

Topcoder

http://www.topcoder.com

世界最大規模の競技プログラミングコンテスト。ここで「レッドコーダー」と呼ばれる存在になると引く手あまたな優秀なエンジニアとして認知される。

この辺の上位クラスになると数学オリンピック優勝者とかそういう次元の人がゴロゴロいるので絶望感がすごい。

AtCoder

https://atcoder.jp/

最近認知度がグイグイ伸びている日本発の競技プログラミングサイト。日本語フル対応なので英語が苦手な人にもオススメ。

paiza

https://paiza.jp/

こちらは就職に直結するような形でプログラミング能力診断が提供されている。他の競技プログラミングサイトよりもとっつきやすいかと思う。

問題も易しめ。

 

他にもいろいろあるが、趣旨から外れるのでこれくらいにしておく。興味を持った方は他にも調べてみるといい。

 

で、なにすればいいの?

競技プログラミングとは与えられた問題をいかに多く、速く解き終わるかを競うものだ。

基本的には○月○日の○時~開催されるコンテストに参加することになるのだが、時間的に折り合いがつかないって方も多いだろう。

しかし、なにも無理してコンテストに参加する必要はない。まずは問題を解き、学習を深めてから腕試ししたくなったら参加すればいいだろう。

競技プログラミングガチ勢のほとんどはC++でコードを書いているが、これは実行速度やライブラリの充実さといった面で有利であるからで、決してC++を書かなくてはいけないわけではない。フロントコーダーならJavaScriptで挑戦してみても全然いいのだ。

実際に簡単な問題をJavaScriptで解いてみよう。問題はAtCoderから適当にピックアップする。

AtCoderではA問題、B問題、C問題~と問題の難易度が分けられている。今回はその中でも簡単なA問題とB問題を一問ずつ解いてみよう。

 

A – Multiple of 2 and N

https://beta.atcoder.jp/contests/abc102/tasks/abc102_a?lang=ja

問題文

正整数 Nが与えられます。2とNのどちらでも割り切れる最小の正整数を求めてください。

制約

入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

出力

2とNのどちらでも割り切れる最小の正整数を出力せよ。

 

これは最も簡単なA問題。

まず「2とNのどちらでも割り切れる」ということがなにを意味するのか考えると、Nが偶数であれば自然と2でも割り切れるに決まってるし、Nが奇数だったら2を掛けた数が最小の公倍数となる、ということがわかる。

これをプログラムで書くのなら

「Nが2で割り切れるのならNを出力、そうでなければ2Nを出力」

ということになる。これをJavaScriptで書くと

みたいな感じ。または答えを変数に格納してもいいだろう。

みたいな。

このように、同じ機能を実現するにしても様々な書き方が存在するのが競技プログラミングの面白いところだ。if文を用いるのではなく三項演算子を用いてもいいだろう。

B – Postal Code

https://beta.atcoder.jp/contests/abc084/tasks/abc084_b

問題文

Atcoder国では、郵便番号はA+B+1文字からなり、A+1文字目はハイフン -、それ以外の全ての文字は0以上9以下の数字です。

文字列Sが与えられるので、Atcoder国の郵便番号の形式を満たすかどうか判定してください。

制約

入力

入力は以下の形式で標準入力から与えられる。

出力

SがAtcoder国の郵便番号の形式を満たすならば Yes 、そうでなければ No を出力せよ。

 

これはB問題、の中でも簡単な方だろうか。

素直に考えると「A+1文字目がハイフンであるか、それ以外の文字は数字であるか、Sの文字数はA+B+1文字であるか」を判定すればよさそうだ。

しかし、問題文と制約をよく見ると「Sには数字とハイフンしか含まれない、Sの文字数はA+B+1文字と決まっている」ことがわかる。

よって判定するべきは「ハイフンは1つしか含まれていないか、そのハイフンの位置はA+1文字目であるか」だけでよい。

ではそれらの真偽をどのように判断すればいいのか考えるといくつかやり方が考えられる。

ハイフンが1つだけ含まれるかどうかってのは正規表現を用いてもいいのだが、私はsplitで区切って要素の数を数える方が好き。

そして、splitで区切った時の一番目の要素の文字数が、Aと一致していればハイフンはA+1文字目にあると言っていい。

そんな感じのものをJavaScriptで書くと

こんな感じ。わりとすっきり書けた。文字数の比較では==演算子を用いることで型を無視するという姑息な技を使った。当然

と型指定してもいいだろう。厳密にどっちが速いのかは教えて偉い人。

 

B問題程度までであれば適当に誤判定さえ起きないコードを書けば通過できる。C問題あたりからパフォーマンス(実行時間やメモリ使用量)も考慮した書き方をしないと通らなくなってくる。

様々なアプローチがある中で、より短く速く動作するコードを書くにはどうすればいいのか?そういったことを考える過程でプログラミング能力が向上していく。

普段こういったプログラムを書く機会のないコーダーであっても、学習の一貫と腕試しとして挑戦してみてはいかがだろうか。

CONTACT
お問い合せ・お見積りはこちらから
  • 03-6279-3013 お問い合わせは 月~金 10:00~19:00

  • メールでのお問い合せはこちら