競技プログラミング
ABC186~195のA~Dまで必要な知識を調べてみた。
公開日:
2021/04/11
ABC186~195のA~Dまで必要な知識を調べてみた。

ABCとは

ABCとはAtCoder社が開催している初心者向けの競技プログラミングのコンテストです。
競技プログラミングとは与えられた問題に対してその解答を出力するようなプログラムを実装して他の競技者と競い合うといったものです。
問題はA~Fの6問あり、解いた問題の点数で点数が同じなら解いた速さで順位が決まります。後ろの問題になればなるほど難しくなります。
今回は10回分のABCのA~E問題についてどのような知識が必要だったのかを(独断で)まとめていくので、問題の雰囲気や傾向をつかんでいってください。

A問題の必要な知識

ABC186

算数、割り算の切り捨てかどうか

ABC187

あまりの出し方、各桁の数値の求め方

ABC188

if文

ABC189

if文、文字の扱い

ABC190

if文

ABC191

if文、算数

ABC192

あまりの出し方,算数

ABC193

小数型、算数

ABC194

if文(else if必須級)

ABC195

あまりの出し方


この内容からA問題を解きたい人は、if文、あまりの出し方、算数あたりの知識を最低限知っておく必要があると言うことがいえますね!

B問題の必要な知識

ABC186

二次元配列、二重for文、最小値の求め方

ABC187

二重for文、配列、中学レベルの数学

ABC188

for文、配列

ABC189

for文、(配列)、小数

ABC190

for文、(配列)

ABC191

for文、配列

ABC192

for文、文字列、文字と数字との対応

ABC193

for文、(配列)、最小値

ABC194

for文、(配列)、最小値

ABC195

for文


この内容からB問題を解きたい人は、for文、配列、最小値(最大値)の求め方の知識を最低限知っておく必要があると言うことがいえますね!

C問題の必要な知識

このあたりから解法が複数個あったり、どこまでを知識としてみるかが分からなくなってきたのでだいぶ適当だけど参考程度に見ていってね!

ABC186

10進数からn進数への変換

ABC187

map(hash_map)の知識,TLEの概念

ABC188

最大値の求め方,TLEの概念

ABC189

最小値の求め方,TLEの概念

ABC190

bit全探索

ABC191

グラフの概念(なくても解けなくはない)

ABC192

各桁の取り出し方

ABC193

平方根,計算量の推定

ABC194

TLEの概念,式の変換

ABC195

TLEの概念


競技プログラミングでは実行時間の制約が設けられています。その時間を超えるようなプログラムを書くとTLEとなり不正解扱いとなります。
この内容からC問題を解きたい人はどうするとTLEになるのかをしり、TLEにならないようにするためのmapや数値をまとめたりなどの手法を知っておくべきだといえます。
また、bit全探索などの全探索のコードも書けるようになっておく必要がありそうです。

D問題の必要な知識

ABC186

累積和、ソート

ABC187

貪欲方、ソート

ABC188

priority_queue、pair、累積和、(座圧)

ABC189

論理積、論理和、(動的計画法)

ABC190

O(logN)でのNの約数列挙、等差数列の和

ABC191

浮動小数点数の誤差とその丸めこみ、三平方の定理

ABC192

二分探索

ABC193

組み合わせの数の求め方

ABC194

期待値について(期待値の線形性、確率1/pで成功する操作を成功するまで繰り返した場合にかかる回数の期待値がp)


この内容から、priority_queueなどのデータ構造や、期待値などのそこそこの数学の知識、浮動小数点数の誤差について知っておく必要があるようです。 また、問題に対して効率的に解く方法を二分探索などのアルゴリズムなども伴わせて考えなければならない問題もあります。

結局何をすれば良いの?

これだけ見ても何から始めれば良いのかわからないですよね。
まずはC++入門 AtCoder Programming Guide for beginners (APG4b)をやるといいでしょう。
これをやって、あとはA、B問題を練習すれば、B問題までは解けるようになるはずです。
C問題に関してはB問題でやってきたことに加えて、TLEにならないように工夫することを意識して練習していけばいつか解けるようになると思います。
TLEに関してはとりあえずfor文で繰り返される回数の合計が5億回以内に収まるかどうかで判定してもらえれば大丈夫です。
D問題に関してはC問題まででやってきたことに加えて、解説で出てきたアルゴリズムなどをネットで調べて、ライブラリ化できるものはライブラリ化していくのがおすすめです。
最後の方は何を言っているのか分からなかったと思いますが、もし興味がある人はインターネット上の他の記事を見るか(僕よりすごい人が書いたすごい記事がたくさんある)、あるいはコンピューターハウスランダムに入ってみてはいかがでしょうか?
それでは、今からAGCが始まるのでさようなら~

loading...