t11hi

hene.dev

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

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

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

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

メモ

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

STL

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

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

制約
・ 1 ≦ N ≦ 100

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
}

vector の先頭に追加

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

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

  vector<double> v(N);

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

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());
}

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

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

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

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

構造体

  • 双方向連結リスト

よくわかっていない。

配列に存在するか

#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;
}

数値を文字列に変換

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

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

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

文字列を数値に変換

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

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

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

char → int に変換

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

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

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

ユークリッドの互除法

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);
  }
}

最小公倍数

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

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

vector

後で書く

stack

後で書く

queue

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

int main()
{
	queue<int> xx;

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

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;
}

大文字か小文字か判別

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

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

	isupper(S);
	islower(S);
}

小文字を大文字に変換

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

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

配列の重複削除

#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());
}

vector

初期値は false

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

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

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
}

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;
}

1 行空白区切りで取る

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

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

べき乗

#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
}

場合分け