概要
これをc++で解く。
この問題を解くには、生成しうる数列を全て作って各々数列の得点を求め、最大値を見つける。（制約より、数列の数はそれほど多くない）
得点を求めるのは難しくないので後回しにして、条件を満たす数列を作ることを考える。
改めて数列に関する条件を確認すると
- 長さ $2 \le N \le 10$
- $1 \le A_1 \le A_2 \le \cdots \le A_N \le M \le 10$
要は、例えば $N=3, M=4$ のとき
\begin{align} &(1,1,1), (1,1,2), (1,1,3), (1,1,4), (1,2,2), (1,2,3), (1,2,4), \cdots , \cr &(2,2,2), (2,2,3), (2,2,4), \cdots ,\cr &(3,3,3), (3,3,4), (3,4,4), \cr &(4,4,4) \end{align}
と、こんな具合の数列を生成すれば良い。
さて、こういう時に「深さ優先探索（DFS）」を使うと良いとのこと。
DFSの概念自体は難しくない、と思うので解説は省略。いわゆる「樹木図」を辿っていくようなもの。
ただ、検索すると、この問題に関しては再帰関数を用いた回答ばかり見つかった。まあやってることは結構わかりやすいのでそれでも良いのだが、あえてDFSでやりたい理由がある。
先日ABC151-D
をやっているときに「幅優先探索（BFS）」に触れており（参考スタックとキューを極める！ 〜 考え方と使い所を特集 〜 - Qiita）、『BFSのアルゴリズムで使っているキューを、スタックにすることでDFSになる』という話を聞いたので、スタックを使う方法で実装してみようと思った。
結論から言えば、成功したので、その考え方や途中でミスった点を記録する。
解答
ABC165-Cを解くための「数列の得点」のことは一旦忘れて、とりあえず、「数列生成」のことだけを考える。
コード
#include <bits/stdc++.h> using namespace std; using vi = vector<int>; int N, M; void show(vi &A){ //配列Aを簡易的に書き出す for(int x: A)cout<<x<<","; cout<<endl; } void dfs(){ //条件を満たす配列を 深さ優先探索 する vector<vi> uncalced; //「発見したけど処理してない配列」を入れる配列。スタックとしてケツから入れてケツから出す。 uncalced.push_back({}); //初期状態を空配列にする while(!uncalced.empty()){ //探索すべき配列がなくなるまで vi current = uncalced.back();//積んである最後尾の配列を読む（取り出されない） uncalced.pop_back(); //最後尾を捨てる if(current.size()==N){ //N桁になってたら書き出す show(current); }else{ //短かったら伸ばしたのをスタックに積む //last : 取り出した配列の最後尾 = 付け足す値の最小値 int last = (current.empty()? 1: current.back()); for(int i=last; i<=M; i++){ //currentにiをくっつけて積む vi next = current; next.push_back(i); uncalced.push_back(next); } } } } int main(){ cin>>N>>M; dfs(); }
標準入力を3 4としてこれを実行すると（お手元の環境やAtCoderのコードテストを使う）次のような出力が返ってくる。
4,4,4, 3,4,4, 3,3,4, 3,3,3, 2,4,4, 2,3,4, 2,3,3, 2,2,4, 2,2,3, 2,2,2, 1,4,4, 1,3,4, 1,3,3, 1,2,4, 1,2,3, 1,2,2, 1,1,4, 1,1,3, 1,1,2, 1,1,1,
いい感じに生成できてるっぽいな！万歳！
詳細
書き出す順番が『逆』になっているのはこれから説明していくのでとりあえずプログラムの動きを考えていく。
一般的にスタックから取り出した配列に対してどういう処理をすればいいかまとめる
- 長さが $N$ の場合、書き出す。
if(current.size()==N)の処理 - 長さが $N$ より短い場合、繋げられる数字を後ろにつけてあげてスタックに放り込む。
elseの処理
2の処理はつまり、例えば $(1,2)$ を取り出した時、その最後尾は $2$ だから（int last = current.back();）
その後ろに来ることができるのは、取り出した数列の最後尾〜使える最大の数字すなわち $2 or 3 or 4$ なので、（for(int i=last; i<=M; i++){）
$(1,2,2), (1,2,3), (1,2,4)$という配列をつくって（vi next = current; next.push_back(i);）
スタックに放り込めば良い。（uncalced.push_back(next);）
この時スタックの状態の遷移は下図のようになる
ということで、スタックを「積み上げ」方向に見るとすると、下の方に小さい数字が、上の方に大きい数字が来ている（ざっくり）。
その結果、初めて「取り出した配列の長さが $N=3$」となるのは $(4, 4, 4)$ を取り出すときだ、というのがなんとなくわかる（もちろんそれを取り出したあとは、何もスタックには入れず、書き出し処理が行われる）。
そういうわけでこのプログラムは「逆順」で数列を吐き出す。
for(int i=last; i<=M; i++){の部分をfor(int i=M; i>=last; i--){に書き換えれば、スタックには数字が大きい方が下になるように積まれるので、取り出して書き出すのは「数字の小さい」数列からになる。
初期状態
初期状態に何を放り込むかが重要。
何も入れない、というわけにはいかない。（while(!uncalced.empty()){なのでuncalcedが空の状態から始めれば何も起こらない。）
最初のステップでは、$M=4$とすると、『何か』をスタックから取り出して、$(1), (2), (3), (4)$ をスタックに積む必要がある。
取り出す『何か』が、要素を持つ配列$(n)$だとすると、上記のプログラムは $(n)$を取り出して$(n, n), (n, n+1), \cdots$をスタックに積むだろう。それでは明らかに都合が悪い。
ということで、初期状態ではスタックに『空の数列』を入れておく（uncalced.push_back({});）。
『空の数列』の最後尾は定義不能だが、『空の数列』に繋げられる数字の最小値は当然 $1$ なので、int lastを求める文が三項演算子を用いて
int last = (current.empty() ? 1 : current.back());
となる。
スタックについて
今回スタックとしてvectorを使っている。
vector<vi> uncalced;
//「発見したけど処理してない配列」を入れる配列。
としている。「発見したけど処理してない」というのが肝要。この考え方でスタックに入れていき、取り出したものは必ず何らかの処理をする。
また、読み込んだらすぐ捨てるのが大事。
vi current = uncalced.back();//積んである最後尾の配列を読む
uncalced.pop_back();//すぐ捨てる
積んだままにしておくと、上から別のものが積まれてしまうかもしれない→無限ループに陥る。
stackそのものを使う場合
stack<vi> s_uncalced;
s_uncalced.push({});
...
vi current = s_uncalced.top();
s_uncalced.pop();
のようにすれば良い（内部では同義）
ABC165-Cの条件に合わせる
ABC165-Cでは、それぞれの数列に対して「得点」を計算し、最大のものを求める必要があった。
↑で作ったプログラムに手を加えてABC165-Cに提出できるようにする。
得点計算
今までは長さ $N$ の数列に対して、書き出し処理をやっていたが、今度は代わりに得点計算をし、ついでに得点の最大値の更新を行う。
得点計算は、数列 $A$ と $Q$ 個の条件 $a, b, c, d$ に対して
$$ A_b - A_a が c なら d 点を得る $$
という条件を実装すれば良い。読み込みの時点でグローバル変数の
using vi = vector<int>; vi a(50), b(50), c(50), d(50)
に $a, b, c, d$ を保存しておけば、得点計算の関数は次のように実装できる。
int score(vi &A){ //配列Aの得点を返す int ans = 0; for(int i=0; i<Q; i++){ if( A[b[i]]-A[a[i]] == c[i] )ans += d[i]; } return ans; }
（読み込み時にa[i]--; b[i]--;を忘れないこと。入力は1~Nだけど添字で使うときは0~N-1なので）
提出コード
ということで、提出するコードの全体像は以下のようになる
#include <bits/stdc++.h> using namespace std; using vi = vector<int>; int N, M, Q;//Qを追加 vi a(50), b(50), c(50), d(50);//a,b,c,dを保存しておく配列 int score(vi &A){ int ans = 0; for(int i=0; i<Q; i++){ if(A[b[i]]-A[a[i]]==c[i])ans+=d[i]; } return ans; } int dfs(){ //深さ優先探索して得点の最大値を返す int ans = 0;//得点の最大値を入れる変数 vector<vi> uncalced; uncalced.push_back({}); while(!uncalced.empty()){ vi current = uncalced.back();//積んである最後尾の配列を読む uncalced.pop_back(); if(current.size()==N){ //N桁になってたら得点求めて最大値更新 ans = max(ans, score(current)); }else{ //短かったら伸ばしたのを積む int last = (current.empty()? 1: current.back()); for(int i=last; i<=M; i++){ vi next = current; next.push_back(i); uncalced.push_back(next); } } } return ans; } int main(){ //入力 cin>>N>>M>>Q; for(int i=0; i<Q; i++){ cin>>a[i]>>b[i]>>c[i]>>d[i]; a[i]--; b[i]--; //aとbはデクリメント忘れずに } int ans = dfs(); cout<<ans<<endl; }
このコードはABC165-CにC++ (GCC 9.2.1)で提出すればACになる。
一応おしまい
BFSのコードの形を元にDFSを作れて大満足。
ただ、この問題は普通に参考サイトにあるような再帰関数を用いた方法のほうがわかりやすいとは思う。
以降は、これを組んでる時に陥ったミスとその分析なので、時間がある人だけ見てもらえば良いです。なんかの参考になるかもしれないしならないかもしれない。
失敗
lastを求める式とその後のfor文を最初
//一応AC
int last = (uncalced.empty()? 1: current.back());
for(int i=last; i<=M; i++){...}
としていた。これは一応正しい数列を出すがマズい点がある。
lastについて、処理の一番最初は当然last = 1になる。だが、uncalcedの底にある数字を抜いた時（長さ1の配列の残り物をとるとき）もuncalced.empty()==trueによってlast = 1になる。for文がi++の方向なら、uncalcedの底にあるのは$(1)$なので矛盾は生じないが、for文をi--の方向にする、すなわち
//WA
int last = (uncalced.empty()? 1: current.back());
for(int i=M; i>=last; i--){...}
とするとおかしくなる。具体的には
... 2,4,4, 3,3,3, 3,3,4, 3,4,4, <-ここまでは昇順で正常 4,1,1, <-ここからおかしい 4,1,2, 4,1,3, 4,1,4, 4,2,2, 4,2,3, 4,2,4, 4,3,3, 4,3,4, 4,4,1, 4,4,2, 4,4,3, 4,4,4,
こうなる。原因は
- for文がi--の方向なので、uncalcedの底には$(4)$があるから、
last=4になるはず - しかし、それを引っこ抜いた時、
uncalced.empty()==trueよりlast=1になる
この状態で書き換えてもWAになる。https://atcoder.jp/contests/abc165/submissions/13240081
なぜなら4始まりで$(4,4,4)$以外の数列は不正な数列だけど得点が加算される可能性があるから（左端の4を除けば広義単調増加しているので得点の条件に引っかかる可能性がある）。
初めは、
となっていたが原因がはっきりしたのでよかった。
おしまい。
