アルゴリズムノート

INT_MAXは10^9。
なのでそれを超える値が計算によって求められる場合には、オーバーフローを起こしてしまう。

2進数表記で100000は16桁を超える。
そのため16桁の値を10進数とみなした場合、その値は21億を超えるので入力値をもらう型はlong型でないといけない。

Atcoderの実行制限はO(10^7)なので、これに収まるように計算を見積もる

ends ヌル文字を末尾に挿入する

cinはcのargsと同じで、空白を区切り文字として他の文字を読み込む。
もし改行を入れる場合は、そちらを区切り文字として読み込む。

具体例

#include <iostream>
using namespace std;

int main()
{
	int a, b;
	cin >> a;
	cin >> b;	
	cout << a << b << endl;
}

❯  ./a.out 
12
1
121

❯  ./a.out
12 1
121

値の切り上げを行うには、分子に分母の-1の値を足してから割り算をする。

コンピュータの計算で10 / 6 = 1であるが (10 + (6 - 1))/ 6 = 2 となる。
割り算は分子の値が分母の値いくつ分あるかを答えとするので、分母の値を分子に与えたら商は+1される。

-1をする意味は、例えば 2 / 2などで余りが0の時に、商が1つ増えてしまうからである。
余りが存在しないのに、商が増えるのは切り上げとは呼ばない

問題が条件式を必ず満たすという文がある場合は、loop条件を指定せず無限loopでよい

アルゴリズムを疑う前に型を疑え
アルゴリズムはあってるが、型がintだったためオーバーフローして駄目なケースがあった。
けれどもアルゴリズムがあっているか不明瞭なため、アルゴリズムの方が間違っていると疑ってしまった。
とりあえずオーバーフローをしているかを見ることが大事

整数系の問題は競技プログラミングにおいて規則性があるので、まずはある程度列挙してみるのが順当な方針

ハッシュテーブル
値をkey,valueで保存する順序なし連想配列、keyの値を配列の添字に変換するhash関数を用意、添字を通して値を取得するので計算量がO(1)となる。
しかし、hash関数から生成される添字が違うkeyで同等になる場合が多々ある。その場合は2つの選択が取られる