問題文 提出コード 解法 解説の通りこちらを参考にして通しました。 再帰でDFSをしながらナップサックを解き、戻り値として、今いる頂点を使用した際の最適解配列と、使用しなかった際の最適解配列を返します。 今いる頂点をとします。子をとします。 1つめ…

問題 提出コード 解法 小さい順に数字を当てはめていくとき、上段の右端に配置するか、下段の右端に配置するかの二択になることを利用します。 番目までの数字を入れ終えて、上段に配置した個数が個かつ、直近手の上下の配置情報がのときの配置の通り数 とし…

問題 提出コード の文字列を一つの年として見た時の、の組み合わせの個数 とします。 の文字列を使用した、と言うことは、次に選ぶがより真に大きい値になる必要があります。 条件は以下の二つで、どちらか片方を満たせばよいです。 これは、桁がそもそも大…

リンク 問題文 解法 1段ずつ下からブロックを積んでいくことを考えます。 ある段のある区間にブロックを積んだら、それ以降はその積んだ区間に対してのみ積んでいくかどうかを考えます。 今区間の幅が残りで、ブロックの残り個数が個の際の、そこからの構築…

リンク 問題文 解法 これの類題です。 文字目までの文字列を完成させるのに最小となる連続部分列の個数 とします。すると、この配列は広義単調増加になっているはずなので、 は、文字目を右端とするようなの部分文字列の中で最長の長さをとしたとき、となり…

問題文 解法 区間DPをします。 の区間に対する最小コスト とすると、 になります。 ただし、の文字列を複数回連結するとになる場合のみ、 になります。 この複数回連結、という判定はKMPの周期判定を用いると上手くできます(下のブログ参考)。 ただし、ぴっ…