問題 提出コード 解法 こちらの問題とほぼ同じ考え方をすることができます。 スタックを利用します。 現在のスタックの一番上の数字をとします。最初はを格納しておきます。 そして以下のような操作を繰り返せば、答えが求まります(初期値は0としておきます)…

問題 提出コード 解法 桁DPです。というより、こちらとまったく同じ問題です。 emtubasa.hateblo.jp ただし、入力の順番だけが異なります。 感想 だいぶ前に通したコードなので、改めて書き直しました。 つい先日のABCでも桁DPが解法になりうる問題が出てい…

問題 提出コード 解法 与えられた入力をの行列とみなし、これを乗すれば、その行列の値の総和が、長さのパスの総数になります。 あとは、バイナリ法なるものを利用して高速に計算することができれば、答えとなります。 冪乗 - Wikipedia 感想 この計算をする…

問題 提出コード 解法 とりあえず、最終的に残る花は、かつを満たすので、LISっぽいことを考えてみます。 一番高さが高い(つまり右端)花の番号がになるような並べ方の中での、美しさの総和の最大値 とします。 すると、次のような操作を、が小さい方から行え…

問題 提出コード 解法 を色としたとき(1:白、0:黒)の、根とする部分木の色の決め方 とします。 全体の根はで固定します。 の子をとします。 すると、を黒で塗るには、の子はすべて白でなければならないこと、を白で塗る場合は、の色は何色でもよいことを考え…

問題 提出コード(1) 提出コード(2) 解法 bitDPです。 番目までの男子に対してペアを作成し終えた段階で、残っている女子の状態がの際の組み合わせの数 とします。 とりあえず、女子全員が残っている状態をとします。 1人目の男子に対してペアを組める女子を1…

問題 提出コード 解法 とします。 体のスライムを合体していくのではなく、体の大きさのスライムを、体に分解していく、というようにして考えていきます。 このとき、大きさのスライムを分解するときのコストはになります。 区間のスライムが1体になっている…

問題 提出コード 解法 普通にDPを考えてみます。 人目までにキャンディを配り終え、個のキャンディが残っている状態になるような場合の数 とすると、が答えとなります。 さて、人目にキャンディを配るとき、～個の中で好きな個数を選ぶことができます。つま…

問題 提出コード 解法 区間DPです。 の区間だけ数列が存在する場合についての、お互いが最善手を尽くした際のの値 とします。答えはとなります。 メモ化DPにするとやりやすいです。 初期値は、です。 が奇数ならそのまま、偶数なら-1倍します。 あとは、以下…