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

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

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

##もう一度解くリスト

• 7
• 13
• 14
• 21
• 22
• 23
• 27
• 31
• 32
• DP系
• 59
• 63
• 65
• 66
• 67
• 逆元
• 78
• 79
• 84

全探索：全列挙

1　ITP1_7_B - How Many Ways?

2　AtCoder Beginner Contest 106 B - 105

3　AtCoder Beginner Contest 122 B - ATCoder

4　パ研杯2019 C - カラオケ

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

5　AtCoder Beginner Contest 095 C - Half and Half

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

7　JOI 2007 本選 3 - 最古の遺跡

8　Square869120Contest #6 B - AtCoder Markets

9　JOI 2008 予選 4 - 星座探し

全探索：ビット全探索

10　ALDS_5_A - 総当たり

11　AtCoder Beginner Contest 128 C - Switches

12　AtCoder Beginner Contest 002 D - 派閥

13　JOI 2008 予選 5 - おせんべい

14　Square869120Contest #4 B - Buildings are Colorful!

全探索：順列全探索

15　AtCoder Beginner Contest 145 C - Average Length

16　AtCoder Beginner Contest 150 C - Count Order

17　ALDS_13_A - 8 クイーン問題

二分探索

18　ALDS_4_B - 二分探索

19　JOI 2009 本選 2 - ピザ

20　AtCoder Beginner Contest 077 C - Snuke Festival

21　AtCoder Beginner Contest 023 D - 射撃王

22　AtCoder Regular Contest 054 B - ムーアの法則

23　JOI 2008 本選 3 - ダーツ

深さ優先探索

24　ALDS_11_B - 深さ優先探索

25　AOJ 1160 - 島はいくつある？

26　AtCoder Beginner Contest 138 D - Ki

27　JOI 2009 予選 4 - 薄氷渡り

幅優先探索

28　ALDS_11_C - 幅優先探索

29　AtCoder Beginner Contest 007 C - 幅優先探索

30　JOI 2011 予選 5 - チーズ

31　JOI 2012 予選 5 - イルミネーション

32　AOJ 1166 - 迷図と命ず

33　AtCoder Beginner Contest 088 D - Grid Repainting

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

34　ALDS_10_A - フィボナッチ数

35　DPL_1_B - 0,1ナップザック問題

36　DPL_1_C - ナップザック問題

37　DPL_1_A - コイン問題

38　ALDS_10_C - 最長共通部分列

(ここから先は、どのような DP で解けるのかは書きませんが、全部ナップザック DP またはその亜種で解くことができます。)

39　JOI 2011 予選 4 - 1 年生

40　JOI 2012 予選 4 - パスタ

41　JOI 2013 予選 4 - 暑い日々

42　JOI 2015 予選 4 - シルクロード

43　パ研杯2019 D - パ研軍旗

44　AOJ 1167 - ポロック予想

45　AOJ 2199 - 差分パルス符号変調

動的計画法：区間 DP

46　ALDS_10_B - 連鎖行列積

47　JOI 2015 本選 2 - ケーキの切り分け 2

48　AOJ 1611 ダルマ落とし

動的計画法：bit DP

49　DPL_2_A - 巡回セールスマン問題

50　Square869120Contest #1 G - Revenge of Traveling Salesman Problem

51　JOI 2014 予選 4 - 部活のスケジュール表

52　JOI 2017 予選 4 - ぬいぐるみの整理

動的計画法：その他

53　DPL_1_D - 最長増加部分列

54　AtCoder Beginner Contest 006 D - トランプ挿入ソート

55　AtCoder Beginner Contest 134 E - Sequence Decomposing

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

56　GRL_1_A - 単一始点最短経路

57　JOI 2008 予選 6 - 船旅

58　JOI 2016 予選 5 - ゾンビ島

59　JOI 2014 予選 5 - タクシー

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

60　GRL_1_C - 全点対間最短経路

61　AtCoder Beginner Contest 012 D - バスと避けられない運命

62　AtCoder Beginner Contest 079 D - Wall

63　AtCoder Beginner Contest 074 D - Restoring Road Network

最小全域木問題

64　GRL_2_A - 最小全域木

65　JOI 2010 春合宿 - Finals　(問題pdf)

66　AOJ 1127 - Building a Space Station

67　AtCoder Beginner Contest 065 D - Built?

高速な素数判定法

68　NTL_1_A - 素因数分解

69　AtCoder Beginner Contest 084 D - 2017-like Number

高速なべき乗計算

70　NTL_1_B - べき乗

71　Square869120Contest #1 E - 散歩

逆元を使う問題

72　AtCoder Beginner Contest 034 C - 経路

73　AtCoder Beginner Contest 145 D - Knight

74　AtCoder Beginner Contest 021 D - 多重ループ

75　AtCoder Beginner Contest 149 F - Surrounded Nodes

累積和

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

77　JOI 2010 本選 1 - 旅人

78　JOI 2011 本選 1 - 惑星探査

79　AtCoder Beginner Contest 106 D - AtCoder Express 2

80　GigaCode 2019 D - 家の建設

(ここから先は、「いもす法」というアルゴリズムを使う場合があります。)

81　AtCoder Beginner Contest 014 C - AtColor

82　AOJ 2013 - 大崎

83　JOI 2015 本選 1 - 鉄道運賃

84　JOI 2012 本選 4 - 釘

Union-Find

85　DSL_1_A - 互いに素な集合

86　AtCoder Beginner Contest 075 C - Bridge

87　AtCoder Beginner Contest 120 D - Decayed Bridge

その他のテクニック

「圧縮」によって解ける問題たちです。

88　JOI 2008 本選 1 - 碁石ならべ

89　JOI 2013 本選 1 - 電飾

「単純な幾何計算」によって解ける問題たち

90　Square869120Contest #5 B - Emblem

91　AtCoder Beginner Contest 144 D - Water Bottle

実装問題

92　AOJ 1193 - 連鎖消滅パズル

93　Square869120Contest #3 B - 石落としゲーム

94　AOJ 1149 - ケーキカット

数学的な問題

95　AtCoder Beginner Contest 149 B - Greedy Takahashi

96　AtCoder Beginner Contest 139 D - ModSum

97　AtCoder Beginner Contest 150 D - Semi Common Multiple

98　三井住友信託銀行プログラミングコンテスト2019 予選 E - Colorful Hats 2

99　DDCC2020 予選 D - Digit Sum Replace

100　Tenka1 Programmer Beginner Contest D - Crossing