2017.03.01
競技プログラミングに挑戦してみよう！ [第4回]
「AtCoderではじめる競技プログラミング」競技プログラミングの楽しさが最も伝わるのは実際に参加してみることです。AtCoderに登録し問題を解くまでの流れを実践解説します。
競技プログラミングで強くなるためには問題を解くのが一番！
さて、これまで競技プログラミングがどのようなものかを説明してきましたが、競技プログラミングの楽しさはやはり実際に参加してみることで最も伝わるのではないかと思います。
競技プログラミングで強くなるためには、競技プログラミングの問題を解くことが一番大切です。
そこで今回はAtCoderに登録し、問題を１問解いてみるところまでの流れを実際にやっていきたいと思います。
登録から練習ページで問題を解いてみるところまでの解説ですので、すでに登録が済んでいたり、AtCoderにすでに参加している方は、 回は読み飛ばしてしまってかまいません。
AtCoderの登録
AtCoderの登録は、以下のページから行うことができます。
登録ページを開くと、上のようなページになるかと思います。
| 項目名 | 説明 |
|---|---|
| ユーザ名 | 日本語のコンテストで表示されるユーザ名です。 |
| ユーザID | ログインに使うユーザIDです。英語のコンテストだとこちらが表示されます。 |
| メールアドレス | 登録したいメールアドレスです。 |
| パスワード | パスワードです。8文字以上の半角英数両方を使ってください。 |
| 所属 | 自由記入欄です。学校名でも会社名でも好きなものを入れてください。 |
| Twitter ID | TwitterのIDを入力してください。公開されるので、見せたくない場合は記入しなくても構いません。 |
| 生年 | 生年を入力してください。本選進出基準の確認などに使われます。 |
| 国籍 | 国籍を入力してください。国際コンテストの場合、名前の横に国旗が表示されます。 |
以上を入力したら、個人情報の取扱いについて確認、新規登録ボタンを押せば登録完了です。
AtCoder練習ページを活用しよう！
AtCoderでは、コンテストに出場したり過去問を解いてみる前に練習ページで、実際に出力フォーマットの確認をすることを推奨しています。［問題］をクリックして「問題名」をクリックしてみてください。
練習ページでは、以下のような問題が出題されています。
問題
制約
今回は非常にシンプルな問題ですが、一応入出力例を見ていきましょう。 以下のような入力が与えられたとします。
12 3test |
これが入力された時、出力するべき答えは、1 + 2 + 3 = 6のため、
6 test |
です。問題としては何も考えるところのない問題ですが、入力フォーマットの確認としてはこんなものでしょう。
この問題は、
・ 1行に1つだけの数の入力
・ スペース区切りの数の入力
・ 文字列の入力
の3つについて学べる問題となっております。
読者の中には、プログラミングに慣れていないためこの問題をどう書いて良いかわからない、という方もいるかもしれません。 AtCoderからプログラミングを始めたような人は、苦戦されるのではないかと思います。
そこで、この練習ページには、問題ページ（※Atcoderにログインしていないと表示されません）に、各言語の正解ソースコードがあらかじめ用意されています。
今回はその中から、いくつかの言語での解答例を実際に見ながら、どのようなソースコードを提出すれば良いかを学んでいきましょう！
C++のコード
まずは競技プログラミングではド定番のC++からです。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #includeusing namespace std;int main(){ // 整数の入力 int a; cin >> a; // スペース区切りの整数の入力 int b,c; cin >> b >> c; // 文字列の入力 string s; cin >> s; // 出力 cout << (a+b+c) << " " << s << endl; return 0;} |
C++については、入力は実は非常に簡単です。iostreamに含まれているcinを使えば、 '>>'演算子を用いるだけで、簡単に入力を受け取ることができます。
出力も、coutと'<<'演算子を組み合わせるだけで簡単にできるので、あまり説明をする必要はないでしょう。
基本的にはこれだけでできてしまいます。ごくごくまれに入力が 100 万行などの膨大なパターンがあり、 そうした場合はcout, cinの組み合わせでは間に合わないので、scanfやprintfを使うことになりますが、 こちらもあまり必要ありません。
Javaのコード
続いて、Javaのコードを見ていきましょう。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | import java.util.*;public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); // 整数の入力 int a = sc.nextInt(); // スペース区切りの整数の入力 int b = sc.nextInt(); int c = sc.nextInt(); // 文字列の入力 String s = sc.next(); // 出力 System.out.println((a+b+c) + " " + s); }} |
Javaは、Scannerという文字列の構文解析が可能なクラスが存在するので、 それを使うと簡単に入力を受け取ることができます。
ただし、こちらは正規表現を使っているので、10 万行程度で制限時間が 厳しくなってしまいます。その場合は、BufferedReader.readLineで 1 行ずつ読み込み、 String.splitで半角スペースごとに分割する、などの手法を使うと、同様に手早く実装できます。
Javaも、競技プログラミングでは非常にメジャーな言語であるため、 十分コンテストに出場することが可能です。
C#のコード
もう１つ、僕が普段使っているC#のコードを見ていきます。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | using System;class Program{ static void Main(string[] args) { // 整数の入力 int a = int.Parse(Console.ReadLine()); // スペース区切りの整数の入力 string[] input = Console.ReadLine().Split(' '); int b = int.Parse(input[0]); int c = int.Parse(input[1]); // 文字列の入力 string s = Console.ReadLine(); //出力 Console.WriteLine((a+b+c) + " " + s); }} |
C#で入力を受け取るときは、基本的には 1 行ずつ受け取ります。 もしスペース区切りの入力が与えられた場合は、まず 1 行ずつ受け取り、 それを半角スペースでSplitしてから、int.Parseなどを用いてパースしていきます。
様々な言語で記述された同じ目的のコード
さてみなさん、ここまでくればお気づきの人も多いかと思いますが、 AtCoderのコンテストでは同じ目的のコードを様々な言語で記述することになります。 つまり、同じ問題を他の言語でどうなるか、というのをほかの人が提出したものを閲覧することが可能です。 この特徴を用いると、各言語の基本的な処理を非常に簡単に覚えることが可能です。
もちろん、競技プログラミングで使われるような処理だけなので、例えばjsonをパースする方法や、 httpで他サイトにアクセスする方法、などを学ぶことはできません。 ですが、基本的な構文やコードの書き方を学ぶには良い環境なのではないでしょうか？
C++だけは特殊なマクロを使用している人が多いため、競技プログラミングの書き方しか学べない部分も多いですが……。
ちなみに、競技プログラミングに本気で取り組む気があるのであれば、今回とりあげたようなある程度実行速度が速い言語を使うことを推奨しています。Rubyなどを使って競技プログラミングに取り組んだ場合、C++と比べて数十倍計算が遅いので、難しい問題になればなるほど実行時間制限が厳しくなり、どうやっても正解することができない問題も出てきてしまいます。
もちろん、単純に競技プログラミングを使って言語を覚えてみようとか、お試しや気まぐれで参加するような形であれば、どの言語でも大丈夫です。
おわりに
今回は、チュートリアル的な問題について解説を行いました。本来ならこれを第1回にするべきだったかもしれません。 プログラミング経験者でも、標準入出力を扱ったことがない、という人をよく見かけるため、 標準入出力についての各言語の解説を挟んでみました。 特にRubyやPythonなどを使っている人が苦戦していることが多い印象ですが、そのまま使いたい場合は、 AtCoderのPractice Contestの問題ページから、実際にどう書くか確認してみてください。
次回は、競技プログラミングの基本となる全探索から、その先につながる考え方について解説していきます。 問題を解く上で基本となる考え方についてまず説明しますが、もしかしたら応用方法についても少し触れるかもしれません。
次回の連載をお楽しみに！
