AtCoder Beginner Contest (ABC)のC問題・D問題を解くための思考プロセスと必要知識

はじめに

この記事では、AtCoder Beginner Contest（以下、ABC）のC問題・D問題が解けずに伸び悩んでいる方向けに、コンテストの問題を解くために必要な典型パターンをご紹介します。
アルゴリズムそのものの紹介だけでなく、「どうしてそのアルゴリズムを用いるのか」や「どうすれば解法を思いつけるのか」といった思考プロセスを重視して記事を書いていこうと思いますので、ABCが解けずに伸び悩んでいる方の一助となれば幸いです。
ABCには難易度が低い順にA問題～F問題がありますが、
A・B問題は難易度が低いので割愛し、E問題・F問題は一概に攻略法的なものをまとめるのが難しかったので、
本記事ではそこそこの難易度であり、かつある程度解法を一般化できるC・D問題を対象としています。
（本記事の内容ですべてのC・D問題を攻略できることを保証するものではありませんが、解ける確率は高くなると思います）
（本記事では「双対」や「貪欲」といった用語が出てきますが、詳しい方から見るとやや怪しい使い方をしているように見えるかもしれません。ですが、これらの概念を拡大解釈した使い方として大目に見ていただけると幸いです。）

なお、本記事で紹介するプログラムはC++14を想定していますが、
思考プロセス的な部分はほかの言語を使う場合にも共通して当てはまると思います。

また、本記事で解いた問題のコードはgithub上に公開していますので、こちらもご参考にしていただけると幸いです。
https://github.com/gnbrganchan/Qiita/tree/master/ABC

AtCoder Beginner Contestとは？

競技プログラミングコンテストの運営会社であるAtCoderが毎週末（土曜か日曜）に開催している、初級者向けの競技プログラミングコンテストのことです。通称ABC。

C問題・D問題の特徴

C問題

A問題はループがなくても解けますし、B問題は問題文の指示に従って全探索すれば解けるのですが、
C問題からは少し計算量を気にしなければなりません。
計算量とは、「プログラムを実行する速度」のことです。
計算量については計算量のはなしが参考になるかと思います。
与えられた条件で全探索をしようとするとTLEになるので、問題を少し読み替えるスキルが必要になってきます。
問題自体の難易度はそこまで高くはないのですが、C問題を解くのに時間をかけてしまうと後続の問題を解く時間が短くなってしまうので、いかにパターンを見抜いて短い時間で問題を解くことができるかが鍵となります。

D問題

D問題も計算量を気にする必要があるのはC問題と同じなのですが、D問題では少し設定が複雑だったり、最大値計算など必要な処理を高速で行うためのデータ構造を適切に選択する必要がある場合があります。
競技プログラミングを始めて日が浅い方はこのD問題が壁になることが多いのではないでしょうか。

C問題・D問題を解くための考え方

C問題

C問題を解くにあたっては、下記のような考え方が有効なケースが多いです。

• 双対を考える
• 貪欲的に最適解を探索する

実際の問題を解説しながら上記について説明していきます。

例題1

2019-09-07 ABC140 C-Maximal Value

$B_i≥\max(A_i,A_{i+1})$という制約の中で整数列Aの総和の最大値を求めよ、という問題です。
maxが制約式の中に入っていたり、「最大値を求めよ」というのが一つのキーなのですが、こういった問題は双対を考えます。
この問題では、$B_i≥\max(A_i,A_{i+1})$という制約式に注目します。
具体的に$A_i$と$B_i$を並べてみましょう。
ちなみにですが、数列が出てくるような問題では具体的に書いてみる、というのが一つの有効な戦略です。

B_1 ≥ \max (A_1, A_2)\\
B_2 ≥ \max (A_2, A_3)\\
B_3 ≥ \max (A_3, A_4)

ここで双対を考えるとはどういうことかというと、
「$B_i$に注目した形になっている制約式を$A_i$に注目した形に変形するとどうなるか？」
ということです。結果的に同義ですが、
、「maxではなくminで条件式を記述するとどうなるか？」
というほうが双対の概念に近いかもしれません。
最終的なゴールも「Aの最大値」なので、制約式もAに注目したものに変形すると見通しが良くなります。
maxという形のままだと見通しが悪いのでandやorを使って制約式を書き直します。
この、「andやorの形に書き直す」というのも定番の考え方です。
すると、上記の制約式は下記のように書き直せます。

B_1 ≥ A_1 ~{\rm and}~ B_1 ≥ A_2\\
B_2 ≥ A_2 ~{\rm and}~ B_2 ≥ A_3\\
B_3 ≥ A_3 ~{\rm and}~ B_3 ≥ A_4\\

こうすると、$A_i$に注目した形に書き直しやすくなります。
では、$A_i$に注目した形に書き直してみましょう。

A_1 ≤ B_1\\
A_2 ≤ B_1 ~{\rm and}~ A_2 ≤ B_2\\
A_3 ≤ B_2 ~{\rm and}~ A_3 ≤ B_3

このままでも良いのですが、minを使った形式に直すとより実装に向けたイメージに近くなります。

A_1 ≤ B_1\\
A_2 ≤ \min (B_1, B_2)\\
A_3 ≤ \min (B_2, B_3)\\

ここまで来ればもう解けたも同然で、求めたいのは$A$($A_i$の合計値)の最大値ですので、
上記の等号が成立するような$A_i$を合計していけばいいことになります。
実際のコードは記事上では割愛しますので、コードが見たい方はgithubをご参照ください。
https://github.com/gnbrganchan/Qiita/blob/master/ABC/ex1_MaximalValue.cpp

例題2

2019-07-27 ABC135 C-City Savers

勇者$i$が倒すモンスターの数を$C_i$とすると、問題文の制約条件は下記のように書けます。

C_i ≤ \min(A_i+A_{i+1},B_i)

つまり、勇者$i$が倒せるモンスター数はその勇者の能力$B_i$以下でなければならず、また倒せる範囲のモンスターの数$A_i+A_{i+1}$以下でなければならない、ということです。
その中で$C$を最大化することがゴールです。

不等式の形だけ見ると例題1に似ていなくもないですが、
「元から目的変数（$C$）に注目した制約式の形にになっている」
「制約式に2変数（$A, B$）以上ある」
あたりが例題1と異なるため、双対を考えるアプローチはできなくはないかもしれませんが難しいです。

ここで考えるのが、貪欲的なアプローチです。
例によってまずは与えられた条件式を書き下してみましょう。

勇者1 \cdots A_1, A_2からB_1のモンスターを倒す\\
勇者2 \cdots A_2, A_3からB_2のモンスターを倒す\\
勇者3 \cdots A_3, A_4からB_2のモンスターを倒す

ここで貪欲的なアプローチとはどのように考えるのかというと、
「とにかく端から順に最適な解を選ぶ」
ということになります。
今回の例で言うと、
勇者1は$A_1$または$A_2$から倒すモンスターを選ぶことができます。
$A_2$は勇者2でも倒せるので、勇者1, 2の世界だけで考えると、
勇者1は可能な限り$A_1$に戦力を割くのが最適です。
貪欲的に解くので、勇者1の能力は使い切りましょう。
つまり、残った勇者1の能力（があれば）で都市2のモンスターも可能な限り倒しておきます。
すると、都市2の残りのモンスターは$A_2 - \max(A_1 - B_1, 0)$となります。
勇者1のパワーはもう0なので、都市2のモンスターを倒せるのは勇者2のみとなります。
これも貪欲的に勇者2のパワーをすべて使い切る方針で都市2→都市3の順にモンスターを倒します。
以上の考え方を繰り返すと結局、すべての都市のモンスターを最も効率的に倒すことができます。
貪欲法の良いところは人間の素朴な直感に近い考え方という点で、C問題・D問題レベルであれば厳密に証明できなくても貪欲法で解いてみたら上手くいった、ということも少なくありません。
（もちろん、直感的にでもちゃんと証明出来たほうがE問題以降への適用力という意味で力がつきますが）

こちらのコードもgithubにありますのでご参考にしてください。

[https://github.com/gnbrganchan/Qiita/blob/master/ABC/ex2_CitySavers.cpp]
(https://github.com/gnbrganchan/Qiita/blob/master/ABC/ex2_CitySavers.cpp)

D問題

D問題でも上記で紹介した「双対」と「貪欲法」は機能するのですが、
それだけでは足りない場面が出てきます。
D問題でさらに必要となるのは下記のような知識です。

• ソート、最大値の計算などを最適な計算量で実装したデータ構造
• 整数問題、グラフ問題など典型問題の典型アルゴリズム

一つ目に関しては、つまりC++でいう、vectorやset,map,queue,stackなどの標準的なデータ型を使いこなせる必要がある、ということです。
慣れないうちはコンテスト参加時にカンペ的なページを開いておくと良いと思います。
例えば、下記にC++の代表的なデータ構造をまとめてあります。
【競プロで使える】C++の標準データ構造まとめ

二つ目に関しては、整数問題なら素因数分解を高速に行うとか、グラフ問題なら深さ優先探索や幅優先探索を実装できるとか、そういう知識です。
正直、こういった知識は場数を踏んで覚えていくしかないかなと思うのですが、
「ここは素因数分解をしなければいけないな」とか、「ここは深さ優先探索だ」などといったレベルで解法をイメージできるのであれば、知識部分は検索すれば出てきます。
典型パターンといってもきりがないので、そこはABCに参加する中で一つずつ覚えていくのが良いでしょう。
ただし、C・D問題レベルではそのようなアルゴリズム知識がそれほどなくても解けることが多く、それが本記事の主題であります。
以下では、双対、貪欲法+αで解ける例題をご紹介します。

例題3

2019-09-15 ABC141 D-Powerful Discount Tickets

これは貪欲法で解けます。
$M$枚あるチケットを1枚ずつ使っていくと考えて、その時一番高い商品にチケットを使えば割引額が一番大きい（これが貪欲的な考え方！）ですよね。
実際この問題はそれで解けるので考え方はC問題レベルなのですが、いざ実装するにあたって一つ壁があります。
それは、「1枚ずつチケットを使っていくときに、どうやってその時の一番高い商品を高速に計算するか？」ということです。
この問題は$N, M ≤ 10^5$であるため、$O(NM)$などのアルゴリズムではTLEしてしまいます。
今、チケットを1枚ずつ使っていくので$O(M)$は仕方ないとすると、「一番高い商品を計算する」部分は$O(\log N)$で計算する必要があります。
そんなことができるか？と考えたときに、上述の「ソート、最大値の計算などを最適な計算量で実装したデータ構造」の知識が必要となるのです。
さて、では一番高い商品=最大値を$O(\log N)$で計算できるデータ構造は何でしょうか。
答えはpriority_queue（優先度付キュー）です。
詳細な解説はたくさんありますのでここでは割愛しますが、これは最大値を$O(\log N)$で計算することができます。

それさえわかればあとは実装するだけです。
コードはこちらに置いておきます。
[https://github.com/gnbrganchan/Qiita/blob/master/ABC/ex3_PowerfulDiscountTickets.cpp]
(https://github.com/gnbrganchan/Qiita/blob/master/ABC/ex3_PowerfulDiscountTickets.cpp)

例題4

2019-09-01 ABC139 D-Mod Sum

これは双対（+貪欲？）で解けます。
以下、便宜上、元の数列$1,...,N$を{$A_i$}と呼びます。
ここで言う双対とはどういうことかと言うと、元の問題では「{$A_i$}を並び替えた数列{$P_i$}を選ぶ」とあるのですが、これを「$P_i$を$1,...,N$に固定したときに最適な元の数列を選ぶ」というように読み替えます。
（これを双対と呼ぶと叱られるかもしれませんが、「問題の本質を変えずに視点を変える」という意味であると思ってご容赦ください）
そして、$P_1$から順に「どのような数を$P_i$で割ると$M_i$が大きくなるか？」ということを考えていきます。
（たとえば、ある数を5で割った余りが5以上になることはないので最大値は4です）
ここは貪欲法っぽいですね。
それをまとめると以下のようになります。

$P_i$	$M_i$の最大値	$M_i$が最大となるときの$A_i$
1	0	すべて
2	1	1,3,5,...
3	2	2,5,8,...
4	3	3,7,10,...
$\vdots$	$\vdots$	$\vdots$
$N$	$N-1$	$N-1$

これを見ればあとはほぼ自明なのですが、$M = M_1 + \ldots + M_N$の最大値は$0 + 1 + 2 + \ldots + N-1$でそれは上記の表で一番小さい$A_i$を選んでいけばよいです。
$P_i = 1$の行の$A_i$は$N$を選びます。

これを$A_i$を固定して$P_i$を考えると辛いのですが、双対（っぽいもの）を考えるだけでぐっと見通しが良くなります。
こちらもコードはgithubにあるのでご参考にしていただけると幸いです。
[https://github.com/gnbrganchan/Qiita/blob/master/ABC/ex4_ModSum.cpp]
(https://github.com/gnbrganchan/Qiita/blob/master/ABC/ex4_ModSum.cpp)

まとめ

ABCのC・D問題を解くための考え方として

• 双対を考える
• 貪欲的に最適解を探索する
• ソート、最大値の計算などを最適な計算量で実装したデータ構造
• 整数問題、グラフ問題など典型問題の典型アルゴリズム

ということをご紹介しました。
すべての問題がこれで解けるというわけではありませんが、
上記のセオリーを意識していただくとより早く解答にたどり着けるようになるのでは、と思います。
最後までお読みいただき、ありがとうございました。