競技プログラミング「AtCoder」をJavaScriptで始めてみた

Udemyもひと段落ということで、前から気になっていた競技プログラミングに手を出してみました。「競技プログラミングって何？」という方に簡単に概要・進め方・約２週間やってみて思ったこと、そして問題の解説も書いてみたいと思います。ちなみに僕がやっているのは「AtCoder」という“競技プログラミング”で検索すれば必ずと言っていいほど挙げられるサービスです。他にも「yukicoder」も国内向け、海外の主催では「TopCoder」「Google Code Jam」「Facebook Hacker Cup」など世界的大企業の名前もあり、Facebookのハッカー精神はこの前のGAFAでも見た通りですね。AtCoder以外のものは試したことがないので比べることはできないですが…取り敢えずAtCoderから始めて僕は問題ありませんでしたし、2問くらい解くと「こういう感じか」とペースが掴めて来るかと思います。

AtCoderとは

オンライン上でほぼ毎週開催されているプログラミングコンテストです。成績上位者には色が与えられ、上位50％で茶色コーダー、トップのレッドコーダーになるには上位0.4%に入らなくてはいけないそうです…企業が主催するコンテストもあり、Yahoo、サイバーエージェント、ドワンゴなどの大企業も優秀な人材を競技プログラミングの世界から探しています。

「競プロなんて意味ない、時間の無駄」という意見があるのも事実であり、たしかに競プロだけではチーム開発やデータベース・フレームワークなどは学べません。しかし純粋にプログラミングに特化した“基礎体力”のようなものなので、これはどの仕事にでも活かせるものであるとも言えるのです。よく言われる「作りたいものを作るのが1番」は確かにそうですが、常にあれこれと作りたいものがあるとは限りませんので、その時にためにトレーニングを積んでおく、という考えでもいいでしょう。

Progateでもレベルが上がって「やった~」がありましたが、この“ゲーミフィケーション”がAtCoderにもあるのでRPGゲームのレベルが上がっていく感覚でプログラミングを学べるのが大きな特徴です。僕も深く考えずAtCoderというゲームを楽しんで2週間プレイしました。

AtCoderの学習の始め方

検索すればすぐヒットするかと思いますが、一応簡単に紹介してその後何をするのかまで書いていきます。と言っても登録は非常に簡単で、AtCoderのページの「新規登録」からユーザーID・メールアドレス・パスワードなどの情報を入力するだけで完了で、これだけで無料で始められます。その後チュートリアルから練習ページへ、「問題」にA問題B問題がありますが、問題文を読んでも「で、何するの？」がいまいちわからないと思います。僕もそうでした…使用するプログラミング言語にもよりますが、まず書き方の型を理解するのに時間が掛かりますし、僕は「標準入力って何？」で苦戦しましたが、「この形でサンプルの値があなたのコードに送られます」ってことです。難問かやればわかります。

ほぼ毎週コンテストは実施されているようですが、「いきなり本番？ちょっとね…」と思う人は「AtCoder Problems」をやりましょう。これは公式ではないようですが、これまでの過去問が一覧で表示されAtCoderのアカウントを持っていればユーザーIDを入力してすぐに利用可能です。まずはAtCoder Beginner Contest(ABC)の問題から取り掛かることが多いそうで、問題に正解することをAC(Accepted)と言い、例えばABC208のA問題「A Rolling Dice」に正解するとその部分が緑色になります。解いた分だけ画面が緑になっていくので達成感もありますよね、僕もまだ「取り敢えず緑を増やす」この段階で勉強中です。

具体的にどういう問題形式？

何をやるかについてですが、「問題を与えられて解く」これだけです。例を挙げると「Atcoder Beginner Contest(ABC)」の第188回の一番簡単なA問題に

という問題で「X≠Y」「XとYは0~100までの整数」などの制約もあります。これだけ見て「2点差以内ならできるでしょ」とここまではわかるかと思いますが、それを「XとYにどんな数が入ってもYesNoで判定されるコード」を書けるかは別の話ですよね？入力例が問題文の下に与えられているんですが、「3 5」ならXに3、Yに５なら出力はYesになるようなコードを書いてくださいという意味です。入力例２は「16 2」これはNo、入力例3は「12 15」これは逆転できないのでNoです。

if (X > Y) {
    if (X < Y+3) {
      console.log("Yes");
    } else {
      console.log("No");
    }
  }

この記述だけでは正解になりませんが、こんな感じのコードが思い付きましたか？正解はたくさんありますので、他にも紹介します。

let x = input[0] - input[1] 
    if(x <= 2 && x >= -2 ){
        console.log("Yes");
    } else {
        console.log("No");
}

これは2つの差が「２以下かつ-2以上の時Yes」つまり絶対値が2以下、こういう書き方は初めはイメージ出来ないかと思いますが、これも問題数をこなして身につく思考力だと思います。

このような感じでAtCoder ProblemsでACを増やして画面を緑にして、「そろそろ本番も挑戦してみようかな」と思えたら週末のコンテストに参加してみましょう。本番ももちろん無料です。

ちなみに実行時間(最初は気にしなくても…)といって書いたプログラムがどのくらい早く効率よく処理されるかも得点に影響するようで、言語は「C++」「Python」「Java」がお勧めで挙げられることが多いのですが、僕はこれらの言語を書けないですし、このために勉強する気もないし、取り敢えずのゲームなのでJavaScriptで書いています。皆さんも得意な好きな言語で書きましょう。

ABC208-A

制約はAは1~100,Bは1~1000、A,B共に整数

算数の問題では見ない形ですが、「合計がBになるか」であって「合計はいくつですか？」ではないですよ。入力例１は[2 11]出力例は[Yes]2回で11を作ることは可能です。[5,6][6,5]がその場合ですが「何通りですか？」でもなく作れるならYes、作れないならNo、これだけです。制約も読んだ方がいいですが、A問題B問題はそこまで注意深く読まなくても与えられている例を読みそれを実装できればいいです。入力例2は[2 13]で出力されるのは[No]になります。

細かいことですが[2 13]は配列[2,13]ではありません。「2半角スペース13」なので気をつけてください。数値型・文字列・配列などの“値の扱い”まずはここで躓きます…

早速ですが答えです。

'use strict'
function main(input) {
  input = input.split(" ");
  const A = parseInt(input[0]);
  const B = parseInt(input[1]);

if (A <= B && B <= 6 * A) {
  console.log("Yes");
} else {
  console.log("No");
}
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));  

まず見慣れないrequire(‘fs’)~などの記述ですが、これは決まりみたいなものなのでコピーでいいです。問題ページの下で「言語」を選択し、このコードを「ソースコード」に張り、「提出」を押すと、main()関数の引数に色々とファイルが入り「この数字の時は~Yesか、良し!次の数字は~No 正解！~~」と様々な数字があなたのコードで試され正しくYesNoが出力されるかチェックされ、全て正しい出力だと「AC」になるわけです。他にも不正解「WA」や実行時エラー「RE」などもあります。[2 11]がよくても他の数字の時はダメだとACにはならないので直しが必要です。コードを修正して再度提出することも可能なのでよ～く考えてみてください。

A問題のアルゴリズムは少し考えればわかるものが多いと思いますが解説です。まずBはA以上であること(A<=B)、3回振って「３」は作れても「3より小さい」は作れません。かつBはAの6倍より小さいこと(B<=A*6)、回数Aが「１」の時「６」は出来ますが、「6以上」を作ることはできません。この二つが成り立つ時”Yes”を出力します。

先ほども書いた通り入力出力が慣れないと大変です。基本の型はコピーで大丈夫です。

'use strict'
function main(input) {

}
main(require('fs').readFileSync('/dev/stdin', 'utf8')); 

mainという関数を作ってそれを実行するためこの中に処理を書いていきます。続いてB問題もどんな難易度か見ていきましょう。

ABC208-B

階乗でお金の単位が上がるので問題文を理解するのに時間が掛かるのですが、例を見るとなんとなくわかります。例1では入力が「9」出力が「3」つまり「9円の商品を最小の枚数で払うには？」が問われていて、1! 円硬貨(1円)を1枚、2! 円硬貨(2円)を1枚、3! 円硬貨(6円)を1枚で「答えは3枚」ということです。ここでポイントは“下から決める”ということで、

このような法則があり、「余り」を削っていきます。下から割って余りが枚数です。商は次の割り算に持ち越します。

例1の「9」は

まず2で割って4余り1の「１」が1!円硬貨の枚数で

次は4÷3は1余り１で2！円硬貨が「1枚」

１÷4は０余り１で３！円硬貨は「1枚」の計3枚です。

例2の「119」は

119÷２=59…１で1!円硬貨は１

59÷3=19…2で2!円硬貨は2

19÷４=4…3で3!円硬貨は3

4÷5＝0…4で4!円硬貨は4枚

最小枚数は1+2+3+4で10枚になります。もう気付いたと思いますがB問題から難易度はグッと上がります…これをコードにするのも一苦労で

'use strict'
function main(input) {
  let P = parseInt(input);
  let count = 0;
  let x = 2;

  while(P > 0) {
    count += Math.floor(P % x);
    P = P / x;
    x++;
  }

  console.log(count);
}
 main(require('fs').readFileSync('/dev/stdin', 'utf8')); 

となりますが、取り敢えず読めますでしょうか？parseIntでinputを数値型にしています。2で割るところからなのでx=2からスタートです。%は余りを出すだけでMath.floorで小数点以下切り捨て、countにその余りを足し上げるループです。Pも2で割り、xを一つ増やして次のループへ、これをPが0より大きい間続けて、ループが終わった時のcountを出力します。…難しいですね、例が良くなかったかも…もっと簡単なB問題もありますので、心配し過ぎずに。