#0. はじめに
はじめまして。高校1年生のyuma220284と申します。
競技プログラミングコンテストを開催する国内最大のサイト、AtCoder。
最近はABCの参加者も5000人を超え、競技プログラミングの存在を知る人も多くなってきました。
そんな中、初めてコンテストに出る人にはある大きな壁が待ち受けています。ABC-Aです。
通常の業務とはまた変わった形式に戸惑った方も多いでしょう。
「合ってるはずなのに通らない...」
「何がいけないのか分からない...」
といってやめてしまうのは勿体ない！
この記事を読んで、ABC-Aをマスターしましょう！
なお、この記事ではC++を使用します。
Q.何故C++以外は書かないのか?
-筆者がC++以外を使っていないからです... Pythonなどは、勉強し次第追記するかもしれません。
Q.何故C++を使うのか?
-C++は数ある言語の中でも特に高速に動作するからです。
-競技プログラミングにおいて、この速さは大きな武器となります。
ところで、ABC-Aは150問以上あります。プログラミングの基礎を学ぶのには十分な量と質です。
そこでこの記事では、ABC-Aを解けるようになると共に、基礎をしっかり抑えていこうと思います。
「解けた！」という快感を是非味わってください。
#目次
| 章 | タイトル | おまけ |
|---|---|---|
| 0. | はじめに | 目次 |
| 1. | 入出力をする | scanf/printfを用いた入出力 |
| 2. | 提出をする | 便利コンテンツ紹介 |
| 3. | 型とはなにか | コードを書きやすくする裏技たち |
#1. 入出力をする
初めてコードを書いたとき、"Hello World!"とパソコンに表示させた人は多いと思います。
競技プログラミングにおいて、入出力は必須です。
あなたが頭の中でA+Bの答えを出せたとしても、機械がA+Bを出力できていないと意味がありません。
まずは、入出力の書き方をマスターしましょう。
##1-1. practice contest-A [Welcome to AtCoder]
整数$a,b,c$と文字列$s$が与えられます。$a+b+c$の計算結果と文字列$s$を並べて表示してください。
$1\leq a,b,c\leq 1,000$
$1\leq |s| \leq 100$
3つの整数$a,b,c$と1つの文字列$s$を入力するようです。
まずは、入力の方式を確認しましょう。
a
b c
s
おや、どうやら改行や空白が入っていますね。間違えて読み込まれてしまうと厄介です。
しかし、C++なら問題はありません。
上から下へ、同じ行なら左から右へ、空白で区切りながら入力してくれます。
標準入出力なので、入力ではcinやscanfという関数を用います。まずは、cinを使ってみます。
順番に気を付けて、入力部分を実装してみましょう！
#include <iostream>
#include <string>
using namespace std;
int main() {
int A, B, C;
string S;
cin >> A >> B >> C >> S; //入力
return 0;
}
実装例です。intやstringなど、見たことが無いものがあるかもしれませんが、後程解説します。
このように、空白や改行を気にせずに、連続で入力します。
cinで入力するときは>>です。気を付けましょう。
さて、入力が終わったので、次は答えを出力してみましょう！
$a+b+c$とsを空白区切りで1行に出力せよ。
また、出力の末尾には改行を入れること。
出力にはcoutやprintfなどを用います。まずは、coutを使ってみます。
おや？どうやら意味ありげな文章が書かれていますね。
出力の末尾には改行を入れる必要があるそうです。
改行は**endl(coutのみ)や"\n"**で入れることが出来ます。一番後ろに置きましょう。(実装例参照)
また、空白は" "で入れることが出来ます。
では、実装してみましょう。
#include <iostream>
#include <string>
using namespace std;
int main() {
int A, B, C;
string S;
cin >> A >> B >> C >> S; //入力
cout << A + B + C << " " << S << endl; //出力
return 0;
}
このように、出力の所で計算することも可能です。
また、coutで出力するときは**<<**を用います。cinの時と向きが逆なので気を付けましょう。
さて、これにて実装は終了です。答えがあっているか確認してみましょう。
その前に、ちょっと余談。先ほど出てきたscanf関数とprintf関数での実装も見てみましょう。
余談なので、先に進みたい方は第二章へ。
#1'. scanf/printfを用いた入出力
scanf/printfは、cin/coutに比べて若干書くのが大変ですが高速です。
また、書式付きで入出力するので、小数点以下何桁などの指定も可能です。
なので、大量の入出力がある時や、小数の許容誤差が小さい時などはこっちを使う必要があります。(特に小数の時)
scanf/printf関数の使い方は、これらの記事に分かりやすく載っています。
scanfの使い方,printfの使い方
型を指定する必要があるので、型がなにか分かっていない方は、第三章を先に確認することを薦めます。
実装例を載せておきます。
#include <iostream>
using namespace std;
int main() {
int A, B, C;
char S[101];
scanf("%d %d %d %s", &A, &B, &C, S); //入力
printf("%d %s\n", A + B + C, S); //出力
return 0;
}
scanfで文字列を読み込むときは必ずchar型の配列を使いましょう。
文字列を読み込むときはアドレス演算子(&)が必要なかったり、使い方が難しいので、基本的にscanfよりもcinを使う方がいいと思います。
printfは小数の出力という別の使用用途があるので、使い方を知っておくと得です。
また、AtCoderでは問題ないですが、Visual StudioなどのエディタではもしかしたらC4996エラーが起きると思います。
これは何かというと、scanfが非推奨(安全でない)という警告です。
競技プログラミングで用いる分には問題ないので、コードの一番上に
#define _CRT_SECURE_NO_WARNINGS
と記述してあげてください。
意味はあまり気にしなくて大丈夫です。おまじないみたいな物だと思ってください。
#2. 提出をする
閑話休題。実装が終わったのでコードを提出してみましょう！
まず、問題の画面を少し下にスクロールしてください。すると次のようなものが表示されると思います。
これはSampleです。ここの入力例を使って、出力例と一致するか試してみてください。右上のボタンを押すとコピーできます。(これかなり便利)
おそらく正しい答えが出力されるはずです。もしも間違っていたら、実装を見直してみましょう。
また、一見同じ答えに見えても、改行が入っていなかったり、末尾に余計な空白が入っていたりすると間違った答えとして見做される可能性があります。十分注意しましょう。
ここで答えが一致していたとしても、それが正しい答えとは限りません。
提出をしてみましょう。
さらに画面を一番下までスクロールしてください。
(これはチュートリアルなので実装例が表示されますが、本番では当然表示されません)
まず、言語を選びます。デフォルトはC++14(GCC)です。これ以外の言語を使用する方は、ここで変更してください。
そして、ソースコードを貼り付けます。最初から最後まで一文字残らず全てコピー&ペーストしましょう。
すると、次のような画面になります。
最後に、下の「提出」ボタンにカーソルを当て、エンターキーを押す！！！！
これで提出完了です！！自動的に次の画面に移動します。
ここで結果の確認が出来ます。
最近提出したものから順に上の方に来ています。結果(上写真赤楕円)を見るとACと表示されていることが分かります。
ACはAcceptedの略です。つまり正解ということですね！！
運営が用意したテストケースに全て正解すると、正しいコードと判定されます。
もし一問でも間違っていたら、WA(Wrong Answer/誤答)やTLE(Time Limit Exceeded/実行時間超過)など、不正解の種類で結果が分かれます。(詳しくは用語集を参照してください。)
なお、不正解の詳細な情報はコンテスト中に他人に伝わらないので、絶対に言及しないようにしてください。(詳しくはルールを参照してください。)
右の方の「詳細」をクリックすると、テストケースの内訳や実行時間など確認することが出来ます。
あなたが提出したコードも全て記録されるので、いつでも見直すことが出来ます。
また、このページは画面上部の「提出結果」(上写真青楕円)を押して、出てきた「自分の提出」ボタンを押すといつでも見に来ることが出来ます。
さらに、通常ではコンテスト終了後に「提出結果」から「すべての提出」を押すことで、他の人の提出を確認することが出来ます。強い人の書き方をみて、新しい知識や技術を手に入れられるかもしれません。
おっと、言い忘れていたことが一つありました。
仮に、B問題を読んでいるときにA問題が解けたとしましょう。
この時、いちいちA問題のページに戻るのは面倒ですよね。
そこで、画面上部にある「提出」(下写真緑楕円)を押してみてください。「提出結果」のすぐ左にあります。
問題と言語を設定して、コードを貼って提出すればオッケーです！！
これにてAtCoderの基本的な使い方は以上です。
これから過去問を解いていくわけですが、いちいちコンテストを探すのは手間がかかりますし、何よりAC済/未ACの管理が大変です。そこで、有志による超絶便利なコンテンツを紹介します。
#2'. 便利コンテンツ紹介
##AtCoder Problems
過去問がコンテストごとに整理されていて、回答状況も把握できます。
Difficultyという難易度推定機能もあり、それを基に自分に合った問題を薦めてもらえます。
また、AC数やCurrentStreak(新規AC連続日数)などで他の競技者と切磋琢磨することもできます。
さらに、最近Virtual Contestの機能も追加され、Problemsの枠に留まらない多様な使い方が出来ます。
kenkooooさんが提供してくださってます。
##AtCoder Scores
点数ごとに整理されていて、Writerで検索したり、問題を自分の指定した点数(または点数の区間)でランダムに出題してくれたりします。
また、「精進グラフ」というものがあり、解いた問題の点数に比例して得点が増えていきます。知り合いと比較してみたり、解いた問題の総得点の目標を決めたりすると、精進のモチベーションにもつながるかも。
やざてんさん,えびちゃんさん,tsutajさん,たっとさんが提供してくださってます。
##AtCoder Virtual Contest
AtCoder上の問題を集めて、自分で疑似コンテストを開くことができます。公式のものが同一コンテスト中のものしか扱えないのに対し、色々な問題を集めることができるので、自由度が高いです。
本気で問題に取り組みたいときは、ここでコンテスト感覚で解くのもお薦めです。
notさんが提供してくださってます。
##AtCoder Tags
AtCoder上の問題をジャンルごとに検索したり、タグ投票をしたりできます。
自分の得意/不得意も分かるので、自分に合った問題を探すことが出来ます。
ぬるぬるさんが提供してくださってます。
他にも多くのコンテンツがあります。
AtCoderでの競技プログラミングがもっと楽しくなるサイトまとめ (Noiminさんのブログ)
便利リンク集 (公式サイト)
などで探せます。自分に合った競技環境を見つけてください。
#3. 型とはなにか
第一章でしれっと出てきていたintやstring。その正体が型です。
型は、いわばデータの種類のことです。
例えば、Aは文字。2は整数。5.2は小数。といった感じで種類分けをします。
人はこの区別が出来ますが、機械は全て0と1で保存するわけですから、それぞれの役割をしっている必要があります。
数字では65(10進数)でも、文字では'A'になるわけです。ややこしいですね。
PythonとC++の大きな違いもここにあります。
Pythonでは動作中に機械が型を判断しますが(こういう言語を動的型付け言語といいます)、
C++はデータ型の宣言をする必要があります(こういう言語を静的型付け言語といいます)。
ならば、Pythonの方が書く量が少なくていいんじゃないか？と考える人もいると思います。
しかし、当然C++にもメリットが沢山あります。
C++ではあらかじめデータ型を決めるため、メモリ領域を最適化することができたり、エラーをコンパイルの時に出してくれたりします。
まあどちらも好みが分かれるところなので、自分が好きな方を選べばいいと思います。
さて、データ型が何なのかを雰囲気で掴んだところで、具体的にどういう型があるのか見てみましょう。
##3-1. 数値型
主に使うものはintとlong longです。それぞれ表せる数の範囲が違います。
intは32bit整数です。おおよそ-20億~20億($210^9$)くらいの整数を保持できます。
long longは64bit整数です。おおよそ-900京~900京($910^8$)くらいの整数を保持できます。
他にもいろいろありますが、使うのはほとんどこの2つです。
詳しい値の範囲などの情報は、この記事をご覧ください。
##3-2. 浮動小数点型
主に使うのはdoubleです。
これで、おおよそ$\pm10^{-308}$~$10^{308}$の値を扱うことができます。
ただ、coutでは6桁しか表示できないため、出力にはprintfを用いる事が殆どです。
精度などの詳しい情報はこの記事を参照してください。
##3-3. 文字型
主に使うのはcharです。
文字にはそれぞれ番号が割り振られています。番号はASCIIコード表で確認できます。
ちなみに、この番号自体は整数のように扱うことが可能です。
例えば、'A'は65,'B'は66なので、'A'+1は'B'になります。
このことを知っておくと後々便利です。
##3-4. 文字列型
stringです。文字列を扱えます。
これを使うと、文字列の長さを調べたり、文字列と文字列を連結したりできます。ほかにもいろいろな操作ができるので、この記事で確認してください。かなり便利です。
ただし、使うときはstringファイルを読み込む必要があります。具体的に言うと、
#include <string>
を、最初に書いておく必要があります。これを書かないと使えないので、忘れないように。
よく使うのは大体これくらいです。
第四章からは、実際に問題を解きながら、それぞれ個別に焦点を当てて詳しい使い方を確認していきます。
これにてPart1終了です。ここまで読んでくださってありがとうございます。
#3'. コードを書きやすくする裏技たち
ここからはおまけです。
コードは見やすいことが大事ですが、競技プログラミングにおいて自分が書きやすいようにすることも重要です。
不注意によるミスやタイムロスを減らすための裏技をご紹介します。
##3'-1. using namespace std;
おまじないです。
C++では(というか大抵の言語は)自分で関数を作ることが可能です。
しかし、仮に既存の関数と名前がかぶってしまうとどうなるでしょう？
もしかしたら希望通りの動作をするかもしれませんが、大抵は想定外の挙動をします。
それを回避するのが名前空間です。
C++が標準で用意している関数は、名前空間にstdが用いられています。(standardの略)
なので、maxという関数を使うときは、
std::max
と表記する必要があるわけです。
しかし、いちいちstd::と打つのは面倒ですよね？
そこで最初に
using namespace std;
と書いてあげると、省略することができます。
ただし、これを書くと自作の関数と標準関数の区別がつかなくなるので、自作関数の命名は気を付けましょう。
ちなみにmax,min,count,gcdは既にあります。もし書くときは、大文字にしましょう。
標準関数に何があるのかは、この記事で確認できます！！(2020/01/26 追記)
##3'-2. bits/stdc++.h
stringや、いずれ使うデータ構造(vectorやqueueなど)は、最初にそれぞれのヘッダファイルを読み込む必要があるわけですが、問題に応じて書き分けるのは少々面倒ですよね？
そこで、bitsファイルを作り、その中にstdc++.hを作成すると、そのなかでファイルを読み込むだけで良くなります。
具体的な記述方法はこんな感じです。
#include "bits/stdc++.h"
また、この仕様はAtCoderでも同じなので、そのまま提出することができます。とても便利
stdc++.hに何を記述するかはこの記事を参照してください。
一応筆者のものも書いておきます。
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
##3'-3. マクロ
long longをいちいち書くのが面倒だったり、for文(後ほど説明)が冗長だと感じた時は、マクロを作りましょう。
#defineを使うことで書けます。
例えば、long longをllと書きたいときは、
#define ll long long
と書けばいいです。
詳しいことはこの記事に書いてあります。
ただし、long longをintと書くときは十分注意しましょう。
main関数が正常に動作しなくなり(返り値がintからlong longになるので)、
printf関数がprlong longf関数になってしまいます。
以上です。
最後に一つだけ注意しておきますが、これによって不具合を引き起こす可能性もあります。(特にマクロ)
そのことを考慮したうえで、よく考えて使ってください。
では、コーディング環境が整ったところで、いよいよ実践編です。