ABC115-Dと再帰
ABC115の結果はひどかった。
Cは解けない問題ではないのに提出後にACを確認しないでDを開始して沼にハマっていたため、Cの提出結果の確認と再提出がとても遅くなり低い点になったのだろう。多分。
Dは「再帰使うんだろうな(*)」と感じていたしそれは間違っていなかったのだが 、再帰的に呼び出される処理内容が大変よろしくなかった。よろしくないとわかっていながら他にあんまりしっかりした実装が思いつかなかったため、それを実装するほかなかった。（PとBからなる文字列を再帰的に生成してcount。やっぱ遅かった）
公式の解説がとても丁寧なので根気よく読めばたいていの人がだいたいわかる気がする。
図1みたいな感じか。
1+a (n-1)の前後で条件分岐してやればいい。あとはn==0のとき書いて終わり。もちろん愚直に解説文通り5つくらい書いてもいいんだろう。条件文を少なくするなら、xが負になる可能性を忘れてはいけない。
再帰のようなことは特に苦手だ。
今回は以下のような関数で再帰した。解説見た後なのでほぼそのまま。
template<class C>
auto f(sll n, sll x,const C&apn)->sll {
// std::cout << n <<" "<< x << "\n";
if (n == 0)return 1 <= x ? 1 : 0;
auto u_index = static_cast<ui>(n) - 1;
if (x <= apn[u_index].first + 1 )
return f(n - 1, x - 1,apn);
else
return apn[u_index].second + 1
+ f(n - 1, x - 2 - apn[u_index].first, apn);
}
2つの数列(anとpn)がつっこんであるapnを参照しないといけない。
でもapnは関数 f を実装した時にはまだソースコード上になかった。
ラムダならキャプチャすればいいけど、ラムダ再帰は読みにくく書きにくいので辛い、と考えてどっちで実装するか迷った。
そして競技中はそれに加えて、
- anやpnはどこで生成するか
- 再帰は lv =０と lv = n どっちから始めるか
- lv = 0 なら n を比較に使うので関数内に入れないといけない
- lv = n ならanとpnも生成するのか？
と思考がパンクしてましたね。とてもよくない。
普通に考えにとどめないでとりあえず紙に書くほうがいいかもしれない。
こういう再帰は面倒なので関数オブジェクト作ればいいのでは、とラムダ再帰ググって思った。メンバに持てばいいし、読みやすく書きやすいのでは。
* 線形再帰ではない？というのだろうか？
で置き換えるのが難しそうなものっぽいな、と感じるもの等。
