こんにちは。あずびわです。
この記事は競プロアドカレ2023の10日目の記事として書いています。
AtCoderを始めてから入茶するまで、つまずいたこととその答えを自分なりに簡単にまとめてみました！
AtCoder始めたばかりで困っている方や、初心者に教える方の参考になればと思います！
目次
はじめに
いろんな入茶記事読んで、AtCoder Problems使って過去問解きつつ鉄則本読めば良い...？となった後の疑問集です。
私自身は、AtCoder始めた時点でプログラミング未経験でしたが、数日間のプログラミングワークショップには参加したことがあったので、if文やfor文については理解していました。
算数・数学については、算数は算数オリンピックもやっていたのでそこそこ、高校数学は一応文系範囲は履修済みなもののあまり自信がないくらいでした。
A問題も難しすぎる
AtCoder Problemsのdiff (難易度)を見ましょう。
円の数字の部分が小さい問題から解くと良いです。
入出力とは
競プロでは、変数などを入力として受け取り、答えを出力します。
この記事や派生したC++以外の言語の記事を参考にすると分かりやすいです。
Pythonでは、1行で複数の値を入力するときはinput().split()になるなど、注意が必要です。
a = input() # aに入力
print(a) # aを出力
int a; // 数値型のaを定義
cin >> a; // aに入力
cout << a << endl; // aを出力
continueとbreakの違い
for文やwhile文などのループで用いられるcontinueとbreakの違いは何なのか。
continueはそのループの間 (for(int i=0; i<n; i++)のiが同じ数字である間)、continueの後の操作をスルーしますが、breakではループ自体をやめます。
for (int i=0; i<5; i++) {
if (i%2 == 0) continue; // iが2の倍数の場合continue
cout << i << endl;
}
1
3
iが偶数の場合はループ内の以降の文、つまりcout<<i<<endl;が行われないため、何も出力されません。
iが奇数である、1と3が出力されます。
for (int i=0; i<5; i++) {
if (i%2 == 0) break;
cout << i << endl;
}
iが0から始まり、0%2==0はtrueのため、ループの最初にbreakしてループを抜けます。
そのため、何も出力されません。
グラフとは
Q. グラフとは？
グラフは、簡単に言うと点とそれを結ぶ辺の集まりです。
よく例に挙げられるのは路線図や人物相関図などで、AtCoderでは道路の最短経路を求める問題などで用いられていて、頻出です。
Q. グラフをプログラム上でどう扱うのか？
例として、このグラフが与えられる場合を考えてみます。
入力として、1行目に点と辺の個数、2行目以降にそれぞれの辺が結ぶ頂点が与えられます。
5 5 // 点が5つ、辺が5つ
1 2 // 点1と点2を結ぶ辺
2 5
1 3
1 4
5 4
これを配列の形で利用します。
具体的には、それぞれの点がどの点と結ばれているのかの配列、そしてそれをまとめる配列の2次元配列になります。
graph[0] = {2, 3, 4} // 配列は0から数えるので、点1の結ばれている点
graph[1] = {1, 5}
graph[2] = {1}
graph[3] = {1, 5}
graph[4] = {2, 4}
