はじめに
1年ぶりに競プロやったら悲惨な状況だったけーとらです。
競プロって便利な関数1つ知っているだけで解けるような問題もあるんですけど、細かな仕様まで覚えておけるはずもなく。。。この現象、もう何度目なんだろう。。。
飽きては久々にやって悲惨を繰り返しているのでここにまとめておきます。
解法のテクニック
問題のパターンで瞬殺できるタイプのテクニック。
問題文に誤魔化されない
数値が2^64以上（10^19より大きい）の場合は、文字列として処理する。
例えば、次のような問題がこれに該当する。
問題文
高橋君は、レジ打ちの仕事をしています。
レジの機械には 00, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9の11個のボタンがあります。 レジの機械には、はじめ0が表示されています。 ボタン00を押すと、表示されている数が100倍されます。 それ以外のボタンを押すと、表示されている数が10倍されたあとに、押されたボタンに書かれている数が加算されます。
高橋君は、レジに整数Sを表示させたいです。 レジにSが表示されている状態にするためには、少なくとも何回ボタンを押す必要があるか求めてください。
制約
https://atcoder.jp/contests/abc283/tasks/abc283_c
- 1≤S≤10^1000000
- S は整数
入力が整数だとか、数を10倍とか、なんだか数値型で扱うようなことが書いてある。ところが、入力を文字列として扱って、先頭から順に00が何個あるか数えるだけで良かったりする。
円は長さ2倍の列として
円の列になっているようなものは、長さを2倍の列として扱えば、始点を決めて処理できる。
例えば、次のような問題がこれに該当する。
問題文
N個のピースに分かれている円形のホールケーキがあり、時計回りでi番目にあるピース（以下、ピースiとする）の大きさはAiです。1≤i≤N−1に対し、ピースiとピースi+1は隣接しており、ピースNとピース1も隣接しています。
ケーキのある連続するピースを選ぶ方法であって、選んだ部分が全体の大きさのちょうど10分の1になるものは存在するか、判定してください。
制約
https://atcoder.jp/contests/typical90/tasks/typical90_bx
- 1≤N≤10^5
- 1≤Ai≤10^9
- 入力は全て整数
ピースの大きさ配列を要素N個だけで用意すると、末尾をまたぐような処理が辛い。
これを要素N個の配列の末尾に同じ配列をくっつけた要素2N個の配列を用意すると、ピース0からピースN-1のいずれのピースから初めても一周分のピースが配列の後ろに用意される。
C++のテクニック
その名の通り、C++で使えるテクニック。
標準ライブラリは一括でインクルードする
「bits/stdc++.h」を使うと、C++の標準ライブラリ（iostream、string、vector、map、set、queue、stack、algorithm等）を一括でインクルードすることができる。
#include <bits/stdc++.h>
GCC(GNU Compiler Collection)環境においてのみ利用可能で、他のコンパイラや環境では使用できないため、競プロ以外では恐ろしくて使えない。
配列の要素を探索する
ソート済みのコンテナ（配列、vector）を二分探索する場合、以下の関数が使える。
- lower_bound：指定された値以上の最小の要素を指すイテレーターを返す
- upper_bound：指定された値より大きい最小の要素を指すイテレーターを返す
- binary_search：指定された値が存在するかどうかをbool値で返す
以下、サンプルコード。
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int x = 5;
// lower_bound関数を使用して、vectorから指定された値以上の最小の要素を探す
auto lb = lower_bound(vec.begin(), vec.end(), x);
if (lb != vec.end()) {
cout << "x以上の要素は" << *lb << endl;
} else {
cout << "x以上の要素はありません" << endl;
}
// upper_bound関数を使用して、vectorから指定された値より大きい最小の要素を探す
auto ub = upper_bound(vec.begin(), vec.end(), x);
if (ub != vec.end()) {
cout << "xより大きい要素は" << *ub << endl;
} else {
cout << "xより大きい要素はありません" << endl;
}
// binary_search関数を使用して、vectorに指定された値が存在するかを探す
if (binary_search(vec.begin(), vec.end(), x)) {
cout << "xは存在します" << endl;
} else {
cout << "xは存在しません" << endl;
}
return 0;
}
最後に
随時更新。。。の予定。
あまりにも増えてきたら記事分けます。
コメント