【超初心者向け】AtCoderの問題を解いてみる【C++】

そまちょ

はじめに

この記事では、プログラミング初心者の方に向けて優しく解説しています。

  • プログラミング初心者で、競技プログラミングを始めてみたい人

  • C++ について勉強したい人

このような方におすすめです。

繰り返し処理するfor

■問題文
N 個の整数の2つの組（A₁, B₁）,（A₂, B₂）,・・・,（Aₙ, Bₙ）が与えられるので、A＋B をそれぞれ出力してください。

■入力
N
A₁, B₁
A₂, B₂
⋮
Aₙ, Bₙ

A - Many A+B Problems - AtCoder Beginner Contest 288

入力を受けとって、N 回足し算をするプログラムを書きます。
この問題の C++ の解答コードです。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  
  // N 回繰り返し処理する
  for (int i = 0; i < N; i++) {
    int A, B;
    cin >> A >> B;
    
    cout << A + B << endl;  // A＋B の出力 
  }
  return 0;
}

このように、処理を繰り返すときには for を使います。
for は次のように書きます。

for （初期設定部；　条件判定部；　インクリメント部）｛
　　処理；
｝

全探索

■問題文
文字列 S が与えられるので、a が現れないなら -１ 、現れるなら最後に現れるのが何文字目か出力してください。

■入力
S

A - Rightmost - AtCoder Beginner Contest 276

文字列について、1文字ずつ a かチェックしていきます。
次が、解答コードです。

#include <bits/stdc++.h>
using namespace std;

int main() {
  string S;
  cin >> S;
  
  // 出力する答えを保存する変数
  int answer = -1;
  
  // 文字列 S を1文字ずつ繰り返し処理する
  for (int i = 0; i < S.size(); i++) {
    if (S[i] == 'a') answer = i + 1;  // 例えば、1文字目は i = 0 になるので 1 増やす
  }
  
  cout << answer << endl;
  return 0;
}

a の現れる位置を保存する変数 answer を宣言しています。
そのあとの処理で、a が見つかればその位置で answer の値を上書きするので、初期値として -1 を代入しています。

int answer = -1;

1文字ずつ繰り返す処理には for を使います。

// 文字列 S を1文字ずつ繰り返し処理する
for (int i = 0; i < S.size(); i++) {
    
}

文字列が何文字あるかは size() を使えばわかります。

#include <bits/stdc++.h>
using namespace std;

int main() {
  string S = "hello";
  cout << S.size() << endl;  // => 5
  
  S = "1234567";
  cout << S.size() << endl;  // => 7
  return 0;
}

文字列の1文字目を見たいときには S[0] のようにアクセスすることができます。1文字目が 0 になるので注意してください。

#include <bits/stdc++.h>
using namespace std;

int main() {
  string S = "1234567";
  cout << S[0] << endl;  // => 1
  
  cout << S[2] << endl;  // => 3
  
  cout << S[6] << endl;  // => 7
  return 0;
}

a かどうかのチェックは if を使います。式が true と判断されたときに処理が実行されます。

if（式）処理；

if (S[i] == 'a') answer = i + 1;  // 例えば、1文字目は i = 0 になるので 1 増やす

ここで式は S[i] == 'a' です。文字列の i 番目の文字が a かを判断しています。

C++ では、文字列は「”（ダブルクォーテーション）」でくくりますが、文字は「'（シングルクォーテーション）」でくくります。

出力するのは、a が文字列の何文字目かです。

1文字目が a だったとき、i は 0 になります。そのため、answer には i +1 を代入しています。

文字コード

■問題文
英小文字 a, b, ・・・, z の ASCII 文字コードはこの順番に 97, 98, ・・・, 122 です。整数 N（97～122）が与えられるので ASCII 文字コードが N の英小文字を出力してください。

■入力
N

A - ASCII code - AtCoder Beginner Contest 252

文字コードを文字に変換して出力します。C++ で文字は char 型になります。
次が、解答コードです。

#include <bits/stdc++.h>
using namespace std;

int main () {
  int N;
  cin >> N;
  
  // N を文字として出力
  cout << (char)N << endl;
  return 0;
}

以下のコードで、整数を char 型に変換して出力しています。

cout << (char)N << endl;

整数に加算することで、英小文字を変更することもできます。

#include <bits/stdc++.h>
using namespace std;

int main () {
  int N = 97;
  
  cout << N << endl;  // => 97
  cout << (char)N << endl;  // => a
  cout << (char)(N + 1) << endl;  // => b
  return 0;
}

これを利用して、次の問題も解くことができます。

■問題文
整数 K（1～26）が与えられます。
英大文字を A から昇順に K 個つなげて得られる文字列を出力してください。

■入力
K

A - Generalized ABC - AtCoder Beginner Contest 282

英大文字 A は文字コードだと 65 です。

#include <bits/stdc++.h>
using namespace std;

int main () {
  int N = 65;
  
  cout << (char)N << endl;  // => A
  return 0;
}

これを利用すれば、次のように解答できます。

#include <bits/stdc++.h>
using namespace std;

int main () {
  int K;
  cin >> K;
  
  for(int i = 0; i < K; i++){
    cout << (char)(65 + i);  // 65 は A
  }
  return 0;
}

for で繰り返して出力しています。

  • i = 0 のとき：(char)(65 + 0) つまり (char)65 => A

  • i = 1 のとき：(char)(65 + 1) つまり (char)66 => B

  • i = 2 のとき：(char)(65 + 2) つまり (char)67 => C

文字コードの 65 ではなく、直接 'A' に加算して出力することもできます。

#include <bits/stdc++.h>
using namespace std;

int main () {
  int K;
  cin >> K;
  
  for(int i = 0; i < K; i++){
    cout << (char)('A' + i); 
  }
  return 0;
}

文字列

■問題文
文字列 atcoder の L 文字目から R 文字目までを出力してください。

■入力
L R

A - "atcoder".substr() - AtCoder Beginner Contest 264

for 文を使うことで解答できます。文字列の1文字目は添え字は 0 になるので、L 文字目は L- 1 になることに注意してください。  

#include <bits/stdc++.h>
using namespace std;

int main () {
  string s = "atcoder";
  
  int L,R;
  cin >> L >> R;
  
  for(int i = L - 1; i < R; i++){
    cout << s[i];
  }
  return 0;
}

別の解き方として、string 型の substr を使ってみます。

substr : 指定した位置から始まる文字列から最大でいくつかの文字の部分文字列をコピーします。

文字列.substr(開始位置, 文字数)

#include <bits/stdc++.h>
using namespace std;

int main () {
  string s = "123456789";
  
  cout << s.substr(0, 3) << endl;  // => 123
  cout << s.substr(3, 3) << endl;  // => 456
  cout << s.substr(3) << endl;     // => 456789
  
  return 0;
}

問題は atcoder の L 文字目から R 文字目までの出力です。
例えば、L = 3、R = 6 のときの出力は code です。

substr を使うときに必要なのは、次の2つです。

  • 開始位置

  • 文字数

開始位置は L になりますが、1文字目は 0 になるので、L - 1 にします。

a ：1文字目。開始位置は 0。
t ：2文字目。開始位置は 1。
c ：3文字目。開始位置は 2。
o ：4文字目。開始位置は 3。
d ：5文字目。開始位置は 4。
e ：6文字目。開始位置は 5。
r ：7文字目。開始位置は 6。

次は文字数です。これは R - L + 1 で計算します。R - L だと1文字少なくなります。
L = 3、R = 6 のとき、出力は code の4文字になります。
R - L = 6 - 3 = 3 になるので +1 して R - L + 1 = 6 - 3 + 1 = 4 と計算します。 

#include <bits/stdc++.h>
using namespace std;

int main () {
  string s = "atcoder";
  
  int L,R;
  cin >> L >> R;
  
  cout << s.substr(L - 1, R - L + 1) << endl;
  
  return 0;
}

substr を使って解ける問題をもう1つ紹介します。

■問題文
数字 1, 2, ・・・, 9 からなる文字列 S があります。S から連続する3個の数字を取り出し、これを整数 X とします。
X と 753 の差（の絶対値）は最小でいくつになるでしょうか。

■入力
S

B - 754 - AtCoder Beginner Contest 114

文字列から 3個の数字を取り出すのに substr を使います。
次が、解答コードです。

#include <bits/stdc++.h>
using namespace std;

int main () {
  string S;
  cin >> S;
  
  // 答え用の変数を大きい値で初期化
  int answer = INT_MAX;
  
  for (int i = 0; i < S.size() - 2; i++) {
    
    // S から3文字分を整数として取得
    int X = stoi(S.substr(i, 3));
    
    // 現在の答えの値と 753 - X の絶対値の小さい方を代入
    answer = min(answer, abs(753 - X));
  } 
  
  cout << answer << endl;
  
  return 0;
}

考え方とすれば、文字列 S から取り出せる X を全探索して、最小値を探すという形です。

いきなりは難しいので、まずは実際の入力例について考えていくのがオススメです。

入力が 1234567876 だとして考えてみます。
この文字列について考えられる X は次の 8個です。

  1. 123：1文字目から取り出し

  2. 234：2文字目から取り出し

  3. 345：3文字目から取り出し

  4. 456：4文字目から取り出し

  5. 567：5文字目から取り出し

  6. 678：6文字目から取り出し

  7. 787：7文字目から取り出し

  8. 876：8文字目から取り出し

これを取り出すコードが次のコードです。

#include <bits/stdc++.h>
using namespace std;

int main () {
  string S;
  cin >> S;
  
  for (int i = 0; i < S.size() - 2; i++) {
    
    // S から3文字分を出力
    cout << S.substr(i, 3) << endl;
    
  } 
  
  return 0;
}

// 出力結果
/*
123
234
345
456
567
678
787
876
*/

for の条件判定部の i < S.size() -2 に注意してください。

for (int i = 0; i < S.size() - 2; i++) {

文字列 S ＝ "1234567876" のとき、添え字と値の関係は以下のようになります。

添え字：０　１　２　３　４　５　６　７　８　９
値　　：１　２　３　４　５　６　７　８　７　６

添え字が 7 のとき S.substr(7, 3) は 876 になります。
8と9のときは次のようになり、連続した3個の数字になりません。
S.substr(8, 3) =  76
S.substr(9, 3) = 6

したがって、for 文は 7 まで繰り返せばいいことがわかります。

この問題の場合は for の条件判定部が i < S.size() でも不正解にはなりませんが、問題によると間違った答えを出力してしまいます。

解答コードを再掲します。

#include <bits/stdc++.h>
using namespace std;

int main () {
  string S;
  cin >> S;
  
  // 答え用の変数を大きい値で初期化
  int answer = INT_MAX;
  
  for (int i = 0; i < S.size() - 2; i++) {
    
    // S から3文字分を整数として取得
    int X = stoi(S.substr(i, 3));
    
    // 現在の答えの値と 753 - X の絶対値の小さい方を代入
    answer = min(answer, abs(753 - X));
  } 
  
  cout << answer << endl;
  
  return 0;
}

先ほどのコードから、文字列 S から3文字の値を取り出すには、S.substr(i, 3) を使えばいいことがわかりました。

問題は 753 との差を計算する必要がありますが、S.substr(i, 3) は 文字列になります。

そのため、計算するためには整数の型（例えば int 型）に変換する必要があります。

// これはエラーになる
int X = S.substr(i, 3);
cout << 753 - X;

// これもエラーになる
string X = S.substr(i, 3);
cout << 753 - X;

stoi

C++ には、string 型を int 型に変換する stoi という機能があります。

stoi を使って整数 X を取得しています。

// S から3文字分を整数として取得
int X = stoi(S.substr(i, 3));

min

C++ では、2つの値を比較して、小さいほうの値を返す min という機能があります。

cout << min(1, 2) << endl;   // => 1
cout << min(5, 2) << endl;   // => 2
cout << min(-5, 0) << endl;  // => -5

min を使って、全探索する中で最小値がより小さい値であれば、更新しています。

// 現在の答えの値と 753 - X の絶対値の小さい方を代入
answer = min(answer, abs(753 - X));

注意点として、answer の初期値は問題の解答としてあり得ない大きい値を設定しておきます。

// 答え用の変数を大きい値で初期化
int answer = INT_MAX;

INT_MAX は int 型の最大値を表します。

cout << INT_MAX<< endl;  // => 2147483647

answer の初期値を 0 にしておくと、min で値が更新されないので、正しい答えが出力できません。

abs

abs は絶対値を返します。

cout << abs(10) << endl;   // => 10
cout << abs(-10) << endl;  // => 10
// 現在の答えの値と 753 - X の絶対値の小さい方を代入
answer = min(answer, abs(753 - X));

解答コードを再掲します。

#include <bits/stdc++.h>
using namespace std;

int main () {
  string S;
  cin >> S;
  
  // 答え用の変数を大きい値で初期化
  int answer = INT_MAX;
  
  for (int i = 0; i < S.size() - 2; i++) {
    
    // S から3文字分を整数として取得
    int X = stoi(S.substr(i, 3));
    
    // 現在の答えの値と 753 - X の絶対値の小さい方を代入
    answer = min(answer, abs(753 - X));
  } 
  
  cout << answer << endl;
  
  return 0;
}

まとめ

  • 繰り返しの処理には for を使う。

  • 文字列.size() で、文字列の文字数を取得できる。

  • S[0] で、文字列 S の1番目の文字にアクセスできる。

  • 条件分岐させたいときは、if を使う。

  • 文字列は「”（ダブルクォーテーション）」でくくり、文字は「’（シングルクォーテーション）」でくくる。

  • (char) や (int) で整数や文字を変換できる。

  • パソコンの中では、文字は文字コードで表されている。

  • 例えば、a の文字コードは 97、A の文字コードは 65。

  • b は、 (char)(97 + 1) あるいは (char)('a' + 1) で表現できる。

  • 文字列.substr(開始位置, 文字数) で文字列の一部を取得できる。

  • stoi で文字列を int 型に変換できる。

  • min で小さい値を取得できる。

  • abs で絶対値を取得できる。

プログラミングの経験はあるが、C++ は初めてという方に向けての記事も書いています。

過去問を解くのがおすすめです。素晴らしいサイトがあります。AtCoder の過去問をレベル別に並び替えたりすることができます。

書籍では、アルゴリズムなどの知識を体系的に学ぶことができるのでお勧めです。

ここから先は

0字
この記事のみ ¥ 100

ログイン

この記事が気に入ったらサポートをしてみませんか？