2:00am, Writing code

Roughly coding. Posted from Berlin.

AtCoder Beginner Contest072に参加してみたので感想とか

最近アルゴリズムとデータ構造の勉強の一環として競技プログラミングに興味が出てきたので少し試してみたりしている。AtCoderでほぼ毎週プログラミングコンテスト(プロコン)が開催されているということだったので、参加してみた感想を参加記録代わりに残しておく。

AtCoderには基本的にAtCoder Beginner Contest(ABC)とAtCoder Regular Contest(ARC)の2種類があり、レベルに応じて参加するコンテストを選択できる1。自分はプロコン初心者なのでABCに参加した。言語は最近メインでJavascriptを使っているのでJavascriptを使用した。

問題は全4問で標準入力から入力を受けとり標準出力に解答を出力するという形式になっている。ABC072の問題は以下を参照。

1問目は超単純な計算をするだけなので特に難しいところは何もない。AからBを引いた結果が0以上ならその値を、0以下なら0を出力するという単純な問題だった。自分の場合こういう単純な条件を見た場合三項演算子が真っ先に浮かんでくるので、以下のようなコードを書くことが多い。

const num = a - b > 0 ? a- b : 0;

しかし解説を見るとmaxを使う方法が説明されていたのが割と目から鱗な感じだった。上記のコードをmaxを使って書くと以下のようになる。

const num = Math.max(a - b, 0);

普段のプログラミングではmax(に限らず標準的な数学操作とか組み込み関数全般)を使う必然性はあまりなく、なんでもかんでも条件文や三項演算子などで処理しがちなのでなんとなく新鮮な感じがした。多分もっと複雑な問題を解く時にこういう発想で問題を抽象化していく必要があるんだろうなーとか思ったり。

2問目は標準入力から文字列が与えられ奇数番目の文字を出力するだけというもの。文字列をループさせて奇数番目の時だけ出力すればいいのでこれも特に難しいところはない。文字列のループ方法は色々考えられるが一例としては以下のようになる。

const str = 'abcdefg';
str.split('').map((c, i) => {
    if (i % 2 === 0) {
        console.log(c);
    } 
});

1つだけ注意しないといけないのは文字列のインデックスと奇数がずれている(インデックスの値が偶数の時に奇数番目の文字を示す)ので、そこを考慮する必要がある。

ここまでは基本的なプログラミングスキルがあれば難なく解ける問題だったが3問目から一気に難易度があがったように思う。まず一目で問題の複雑度が全問までよりもはるかに高いことがわかる。自分の場合、入出力例と問題文を何回か見比べてみてようやく問題の意味がわかった。

このレベルになるとプログラミング以前の話で仕様を理解する読解力があるかという問題だと感じた2。問題を理解した後もさっぱり解法が思いつかなかったが、しばらく考えているうちに総当り的な方法を思いついて試してみたらなんとか正解していた。こういう時に複数の解法をパッと思いついておおよその計算量を把握して適切なアルゴリズムを書くという一連の流れがプロコン上達のためには必要なんだなーとか思った。

4問目も最初は問題文の理解に手間取ったが、最終的にはなんとか正解することができた。

雑感

実際にやってみた結果、問題を読んで仕様を理解し適切な実装パターンを考慮して制約条件を満たした上で特定ケースもカバーできる実装をするという、およそ実務で必要なほぼ全ての能力を短時間で発揮する必要があるので、プログラミング力の底上げには非常にいいんじゃないかと思った。

最近のアプリ開発だとAPIを適切に組み合わせてイベントフローを制御するアルゴリズムを考える必要があるが、プロコンにはそれとはまた違った趣があるので、興味があればとりあえず参加してみるのもいいかもしれない。

ということで今回はなんとか全問正解できたので一応満足した(ビギナーレベルだけど)。実は前回のABCにも参加してみたけどその時は2問しか解けなかったので多少はましになったのかなー。


  1. 不定期でAtCoder Grand Contest(AGC)というさらに高レベルなコンテストも開催されている模様

  2. まぁビギナーレベルなんですけど