初めてAGCのA問題の茶色級*1を解くことができたので、解法を記載する。 問題 atcoder.jp問題は「最小値A、最大値Bの長さNの数列が与えられる。この数列の総和は何通りあるか？」である。 制約はN, A, Bともに1〜10^9をとる。「○通り求めよ」系の問題は一瞬身…

初心者は紙に書いて考えないと手こずる系の問題。atcoder.jp 問題概略 N個の都市とM本の道路がある。 i番目の都市は、他の都市と1本の道路で結ばれている。 このときi番目の都市が、他のいくつの都市と結ばれているか? 出力は、i行目にi番目の結果を出力せよ…

C++のSTLにはstd::pairという関数が用意されている。 2つの値の組を表し、使い方も単純で pair<値1の型, 値2の型> 変数名; で宣言して make_pair(値1, 値2); を使って値を突っ込んでいくだけだ。いろいろな場面で活用できるのだが、先日AtCoderの過去問を解…