91. 今日解いた問題（2022.03.28）
今日解いた問題についてまとめます。
自分で解きたい方のために、最初に問題だけ置いて、後で自分の解法を書きます。
問題一覧
- F - Endless Walk （Diff: 1451）
- B - 細長いお菓子 （Diff: 1395 ※たぶんもっと低い）
- D - Christmas （Diff: 1088）
自分の解法など
F - Endless Walk
前回の ABC-F問題です。
この問題はグラフ典型アルゴリズムさえ知っていれば少しの工夫で解ける問題で、できれば解きたかった問題でした（色々あったので本番中に解けませんでしたが）。
「いくらでも移動を繰り返すことができる」というのは、「閉路にたどり着くことができる」と言い換えることが出来ます。有向グラフで閉路を構成する頂点集合を得られるアルゴリズムとして、強連結成分分解が知られています。「大きさが 以上の強連結成分にたどり着くことができる」頂点が答えとなります。これはメモ化再帰などで求められます。
計算量は です。
B - 細長いお菓子
水diffなんですが、2014年の問題なのでおそらく今だと灰色後半～緑前半くらいの難易度だと思います。内容としては、結構基本的なしゃくとり法です。
D - Christmas
フィボナッチ数列を思い出すような問題で、あれと同じような工夫で解けます。単純な再帰で構成すると計算量が爆発します。
具体的な文字列を構成するのは不可能ですが、レベル バーガーについて「大きさはいくらか？P がいくつ含まれるか？」というのはメモ化を用いれば
で求められます。ここでは、構成要素ごとにこのカウントを持っておきましょう。レベル
バーガーを
と表現して、
と見て上記情報を保持するようなイメージです。加えて、「
全体の大きさ・P の数」も持っておきます。
あとは、順番に食べていきます。残り層数と現在見ている 全体の大きさを比較して、残り層数の方が大きければ全体を食べるので、大きさ分残り層数を引いて、答えに P の数を足します。それ以外なら、その構成要素を順番に食べていきます。
構成要素が（全体を合わせて）6 つなので、最悪でも 以下の比較回数に収まります。
