C++で、AtCoder の問題を色々解いたときのメモ

2020 年は、AtCoder Problems を見ながら、ABC 全部解くことを目標に 1 日 1 問、A から解き進めました。 解き忘れる日もありましたが、続けられてよかったです。

ここから先は、解いたときのメモです。

メモ

下記を見て、解いていくのが良さそう。

• レッドコーダーが教える、競プロ・AtCoder 上達のガイドライン【初級編：競プロを始めよう】 - Qiita
• レッドコーダーが教える、競プロ・AtCoder 上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita

STL

• 参考: 厳選！C++ アルゴリズム実装に使える 25 の STL 機能【前編】 - Qiita

(B + A − 1)/A は B/A の切り上げ

• 問題: A - お茶

制約によっては全部計算しても問題ない

制約
・ 1 ≦ N ≦ 100

• 問題: B - Break Number

vector の要素の削除

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

int main()
{
  int N;
  cin >> N;

  vector<int> vec = { 1, 2, 3, 4 };

  // 2 削除
  vec.erase(vec.begin() + 1);

  // 3 削除
  vec.erase(vec.begin() + 1);

  for (int i = 0; i < vec.size(); i++) cout << vec.at(i) << " ";
	// => 1 4
}

• 問題: C - Alchemist
• 参考: C++ - 要素の削除 | c++ Tutorial

vector の先頭に追加

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

int main()
{
  int N;
  cin >> N;

  vector<double> v(N);

  // 100 を先頭に追加
  v.insert(v.begin(), 100);
}

• 問題: C - Alchemist
• 参考: std::vector::insert

vector の最大値・最小値

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

int main()
{
  int N;
  cin >> N;

  vector<int> vec(N);

  for (int i = 0; i < N; i++)
  {
    cin >> vec.at(i);
  }

  int minElement = *min_element(vec.begin(), vec.end());
  int maxElement = *max_element(vec.begin(), vec.end());
}

• 問題: C - Rally
• 参考: 忘れがちな C++ の標準ライブラリの使い方 - Qiita

小数点以下の桁数を指定して表示

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

int main()
{
  double X = 11;
	double Y = 3;

  cout << fixed << setprecision(10) << X / Y << endl;
	// => 3.6666666667
}

• 参考: c++ 浮動小数点数 表示方法 - Qiita
• 問題:
  • A - Entrance Examination
  • C - Alchemist

構造体

• 双方向連結リスト

よくわかっていない。

• 問題: Aizu Online Judge
• 参考:
  • AB - 3.04.構造体
  • ALDS1_3_C:

配列に存在するか

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

int main()
{
  vector<char> ACGT = {'A', 'C', 'G', 'T'};

  string S;
  cin >> S;

  int tmpMax = 0;
  int ans = 0;

  for (int i = 0; i < S.size(); i++)
  {
		// ACGT 配列に S.at(i) が存在するか
    if (find(begin(ACGT), end(ACGT), S.at(i)) != end(ACGT))
    {
      tmpMax++;
      ans = max(ans, tmpMax);
    }
    else
    {
      tmpMax = 0;
    }
  }

  cout << ans << endl;
}

• 参考: c++ - 与えられた int が配列に存在するかどうかを確認するにはどうすればよいですか？例えば、私は、この配列を

数値を文字列に変換

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

int main()
{
  int N;
  cin >> N;

	// 数値を文字列に変換
	to_string(N);
}

• 問題: B - Uneven Numbers
• 参考: to_string - cpprefjp C++日本語リファレンス

文字列を数値に変換

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

int main()
{
  string A = "10";

  cout << stoi(A) * A.size() << endl; // => 10 * 2 = 20
}

• 参考:
  • stoi - cpprefjp C++日本語リファレンス
  • B - 足し算

char → int に変換

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

int main()
{
  char N;
  cin >> N;

	// char を int に変換
	a = (int)(N - '0');
}

• 参考: char 型を int 型に変換する方法と注意【数値化 キャスト 文字列変換】

ユークリッドの互除法

2 つの自然数の最大公約数を求める手法

最大公約数

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

// gcd() 書かなくても numeric ライブラリの中にある
int gcd(int a, int b) {
  if (a % b == 0) {
    return b;
  } else {
    return gcd(b, a % b);
  }
}

• 参考: gcd - cpprefjp C++日本語リファレンス

最小公倍数

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

// lcm() 書かなくても numeric ライブラリの中にある
int lcm(int a, int b)
{
	return a * b / gcd(a, b);
}

• 参考:
  • lcm - cpprefjp C++日本語リファレンス
  • 【C++】2 つの値の最大公約数と最小公倍数を求める｜かみやかずさ｜ note

vector

後で書く

stack

後で書く

queue

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

int main()
{
	queue<int> xx;

	// 追加
	xx.push(1);
	// 表示
	xx.front();
	// 削除
	xx.pop();
}

• 参考:
  • queue::empty - cpprefjp C++日本語リファレンス
  • スタックとキューを極める！ 〜 考え方と使い所を特集 〜 - Qiita

return 0

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

// return 0 で正常終了, main() 以外では必ずつけるようにする
int xxx() {
	return 0;
}

// 途中で、return 0 したらそこで終わる
int main() {
	return 0;

	// 実行されない
	cout << "a" << endl;
}

• 参考: C 言語の return 0 の有用性が今更わかった話 - Qiita

大文字か小文字か判別

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

int main()
{
	char S = 'A';

	isupper(S);
	islower(S);
}

• 問題: A - αlphabet
• 参考: 【C++】文字が大文字か小文字か判定する方法｜かみやかずさ｜ note

小文字を大文字に変換

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

char upper(char c)
{
  return c - ('a' - 'A');
}

• 参考: C 言語での大文字 ⇔ 小文字変換の方法を解説

配列の重複削除

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

int main()
{
	vector<string> vec = { 'aaa', 'ccc', 'bbb', 'aaa' };

	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());
}

• 問題: C - gacha
• 参考: vector から重複した要素を削除する - ゲームが作れるようになるまでがんばる日記

vector

初期値は false

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

int main()
{
	vector<bool> vec(3);
}

• 問題: B - Trick or Treat
• 参考: 'vector | Programming Place Plus C++編【標準ライブラリ】第５章'

string → int

C++11 以降で使える関数

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

int main()
{
	string S;

	stoi(S);
}

https://atcoder.jp/contests/apg4b/tasks/APG4b_y?lang=ja 型変換

x 文字目から、y 文字目まで取得

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

int main()
{
  string S = "abcdefghijklmnopqrstuvwxyz";

  // 0 文字目から 3 文字目
  cout << S.substr(0, 3) << endl;
	// => abc

  // 4 文字目から 8 文字目
  cout << S.substr(4, 8) << endl;
  // => efghijkl

  // 23 文字目から 100 文字目
  cout << S.substr(23, 100) << endl;
	// => xyz
}

• 問題: B - ... (Triple Dots)

• 参考: C++ の文字列操作まとめ - Qiita

0 埋め

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

int main()
{
  cout << setfill('0') << right << setw(4) << 1 << endl; // 0001
}

数字を 0 埋めで表示する (C++) - ためすう

1 の位を取得

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

int main()
{
  int N = 123;
  cout << N % 10 << endl;
}

• 問題: A - ∴ (Therefore)

1 行を空白区切りで取得

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

int main()
{
	while(cin >> S) {
	}
}

• 問題: Aizu Online Judge

• 参考: 競プロ等における C++の標準入力 - Qiita

べき乗

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

int main()
{
  int A = 10;

  cout << pow(A, 2) << endl; // => 100
}

整数で表示

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

int main()
{
  int A = 999;
  string B = "999";

  cout << (A * pow(10, B.size()) + stoi(B)) * 2 << endl; // => 2e+06
  cout << (int)(A * pow(10, B.size()) + stoi(B)) * 2 << endl; // => 1999998
}

場合分け

• 問題: B - Easy Linear Programming