分野別 初中級者が解くべき過去問精選100問

このページは何?

このブログでは、レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】2-3節にまとめられている100問をPythonで解いています。

AtCoder で水色コーダー、つまりレーティング 1200 を少ない問題数で達成するために、茶色コーダー・緑コーダーにとって適切な教育的良問を 100 問集めました。

分野ごとに問題が分けられています。また、アルゴリズムの確認問題から応用問題まで幅広い層の問題がありますので、是非解いてみることをおすすめします。難しい問題もあるので、水色コーダーを目指す人は 100 問中 70 問正解を目安に頑張ってください。

100 問全部解けたら、水色コーダーどころか青色コーダーくらいの実力が付くと思います。そのため、既に水色コーダー以上であっても、100 問全部を解いていない場合は、解く価値が大きいと思います。

このページは、各解説記事へのリンクをまとめています。

リンク

全探索:全列挙

  1. ITP1 7B 組み合わせの数

  2. ABC106B 105

  3. ABC122B ATCoder

  4. パ研杯2019 3C カラオケ

全探索:工夫して通り数を減らす全列挙

  1. ABC095C Half and Half

  2. 三井住友信託銀行プログラミングコンテスト2019D Lucky PIN

  3. JOI2007本戦C 最古の遺跡

  4. Square869120Countest#6B - AtCoder Market

  5. JOI2008予選4 星座探し

全探索:ビット全探索

  1. ALDS1 5A 総当たり

  2. ABC128C Switches

  3. ABC002D 派閥

  4. JOI2008予選5 おせんべい

  5. Square869120Contest#4B Buildings are Colorful!

全探索:順列全探索

  1. ABC145C Average Length

  2. ABC150C Count Order

  3. ALDS1 13A 8クイーン問題

二分探索

  1. ALDS1 4B 二分探索

  2. JOI2009本選2 ピザ

  3. ABC077C Snuke Festival

  4. ABC023D 射撃王

  5. ARC054B ムーアの法則

  6. JOI2008本選C ダーツ

深さ優先探索

  1. ALDS1 11B 深さ優先探索

  2. AOJ1160 島はいくつある?

  3. ABC138D Ki

  4. JOI2009予選D 薄氷渡り

幅優先探索

  1. ALDS1 11C 幅優先探索

  2. ABC007C 幅優先探索

  3. JOI2011予選E チーズ

  4. JOI2012予選E イルミネーション

  5. AOJ1166 迷図と命ず

  6. ABC088D Grid Repainting

動的計画法:ナップザック DP

  1. ALDS1 10A フィボナッチ数列

  2. DPL1B 0-1ナップザック問題

  3. DPL1C ナップザック問題

  4. DPL1A コイン問題

  5. ALDS1 10C 最長共通部分列

ナップサックDPまたはその亜種

  1. JOI2011予選D 1年生

  2. JOI2012予選D パスタ

  3. JOI2013予選D 暑い日々

  4. JOI2015予選D シルクロード

  5. パ研杯2019 3D パ研軍旗

  6. AOJ1167 ポロック予想

  7. AOJ2199 Differential Pulse Code Modulation

動的計画法:区間 DP

  1. ALDS1 10B 連鎖行列積

  2. JOI2015本選B ケーキの切り分け2

  3. AOJ1611 ダルマ落とし

動的計画法:bit DP

  1. DPL2A 巡回セールスマン問題

動的計画法:その他

  1. DPL1D 最長増加部分列

  2. ABC006D トランプ挿入ソート

  3. ABC134E Sequence Decomposing

最短経路問題:ダイクストラ法

  1. GRL1A 単一始点最短経路

  2. JOI2008予選F 船旅

  3. JOI2016予選E ゾンビ島

  4. JOI2014予選E タクシー

最短経路問題:ワーシャルフロイド法

  1. GRL1C 全点対間最短経路

  2. ABC012D バスと避けられない運命

  3. ABC079D Wall

  4. ABC074D Restoring Road Network

最小全域木問題

  1. GRL2A 最小全域木

  2. ABC065D Built?

高速な素数判定法

  1. NTL1A 素因数分解

  2. ABC084D 2017-like Number

高速なべき乗計算

  1. NTL1B べき乗

  2. Square869120Countest#1E - 散歩 (E869120 and Path Length)

逆元を使う問題

  1. ABC034C 経路

  2. ABC145D Knight

  3. ABC021D 多重ループ

累積和

  1. 全国統一プログラミング王決定戦本戦A Abundant Resources

  2. JOI2010本選A 旅人

  3. JOI2011本戦A 惑星探索

  4. ABC106D AtCoder Express 2

  1. GigaCode2019D 家の建設

いもす法

  1. ABC014C AtColor

  2. AOJ2013 大崎

  3. JOI2015本選A 鉄道旅行

Union-Find

  1. DSL1A 互いに素な集合

  2. ABC075C Bridge

  3. ABC120D Decayed Bridge

その他のテクニック

圧縮

  1. JOI2008本戦A 碁石ならべ

  2. JOI2013本選1 電飾

単純な幾何計算

  1. Square869120Contest#5B - Emblem

  2. ABC144D Water Bottle

実装問題

  1. AOJ1193 連鎖消滅パズル

数学的な問題

  1. ABC149B Greedy Takahashi

  2. ABC139D ModSum

  3. ABC150D Semi Common Multiple

  4. 三井住友信託銀行プログラミングコンテスト2019E Colorful Hats 2

  5. DDCC2020予選D Digit Sum Replace

  6. Tenka1 Programmer Beginner Contest 2018D Crossing

オススメの書籍

この三冊を買っておけば間違い無いです。

終わりに

他にも様々なテーマでまとめ記事を書いているのでよろしければご覧ください。

まとめ記事の一覧

MENTAというサービスでプログラミング学習のサポートをしています。競技プログラミングについてもサポートできるので、ご興味がある方はぜひMENTAのDMでご連絡いただければと思います。

記事情報

  • 投稿日:2020年5月8日
  • 最終更新日:2022年1月8日