Search

Computer House Random
Computer House Random
  • Randomについて
  • ブログ
  • Project
  • 作品紹介
  • 部員紹介

ABC186~195のA~Dまで必要な知識を調べてみた。

競技プログラミング

Haniwa
2021/04/11

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が始まるのでさようなら~

新入生向けブログリレー2021

2021年度オンライン部活動説明
競技プログラミング 記事を共有
Avatar
Haniwa

ハニワです。

Computer House Random はパソコンによる創作活動を行っている大阪府立大学の部活動です

Avatar
Haniwa

ハニワです。

競技プログラミング 記事を共有

News

ICPC2020参加記

ICPC
pngn
2021/05/08

コンピュータハウスランダムってどんな部活?

【1日目】5分でわかるランダムのこと
NEGI
最終更新 2020/04/18

はじめまして、らんだむちゃんです!

自己紹介と最初の動画
らんだむちゃん
最終更新 2020/03/19

作品紹介

【18日目】難波駅構内をblenderで再現してみた

途中経過
うっかり侍
2021/08/31

【17日目】ウィルダネスアドベンチャー(?)

いつかリベンジする
クマイザサ
最終更新 2021/08/30

【16日目】CHICKEN NIGHTS

正直、すまんかった
Marcus
最終更新 2021/08/29

Tag Cloud

作品紹介 (48) 新歓ブログリレー2021 (46) 新歓ブログリレー2020 (37) 競技プログラミング (34) 新歓ブログリレー2022 (33) 雑談 (32) ゲーム (30) ゲーム制作 (24) 競プロ勉強会 (22) 作品展示リレー2021夏 (19)

最新の投稿

【38日目】OneDriveでファイルを管理して授業や部活で活用しよう!

オム大、クラウド1TBくれるってよ
Kwang
最終更新 2022/04/29

【37日目】受けループやらメタビートやらのすゝめ

(ゲームにおいては)人の嫌がることをするのが最も楽しい
クマイザサ
2022/04/28

【36日目】マイクラのMODパックで遊ぼう

MODパックの導入は難しそうって思ってない?
neuron
2022/04/27

【35日目】大阪公立大学 中百舌鳥図書館利用のススメ

かなり長め
Rikky
2022/04/26
READ MORE

関連記事


ARC120-F解説

ARC120 F

Avatar

ICPC2020参加記

ICPC

Avatar

主客転倒について

コストの寄与を考える

Avatar

AHCに参加してみた。

競プロ勉強

Avatar

競プロのすすめ

そろそろ復帰したい

Avatar

競プロ成長録的なもの

精進しよう

Avatar

Random
Randomについて
ライセンス
Privacy Policy
お問い合わせ
部員専用サイト
Project
新入生向けブログリレー2022
作品展示リレー2021夏
競プロ勉強会
Web
らんだむちゃん
ブログ
作品紹介
LT会
グラフィック
DTM
タグ一覧
Copyright © 2020 Computer House Random
引用
コピー ダウンロード