問題 atcoder.jp 考えたこと おそらく貪欲で構築していくんだろうと思ったが、深さ であり、何も考えずに葉の数を最大化はできない。 また、根から適当に貪欲していくのも良くない。なぜなら、増やしすぎると、それ以降の葉の数と辻褄が合わなくなる。 解法 …

題名のまんまです。 1,3,3,7 から (1 + 7 / 3) * 3 みたいなパターンを導き出して計算します。 解法 再帰をぶん回す。全探索です。 括弧さえつかなければ、適当に演算子を全探索してevalすればいいが、問題は括弧の場所がめんどくさい。 全探索する手法も考…

問題 個の頂点の頂点を持つグラフが与えられる。このグラフには、とをコスト1で結ぶ辺と、個のをコストで結ぶ辺がある。 からまでの最短距離を求めよ。 解法 であるから、グラフを陽に持つことはできない。 したがって、一部の頂点のみを利用して問題を解く…

問題 頂点の木が与えられる。木上の頂点に2つコマを置き、これらについて、次のゲームを行う. ・各ターンごとに、をこの順序に従って隣接する頂点に移動させる.ただし、一つの頂点に2つ以上のコマが存在するとき、ゲームを終了する ・はできるだけゲームを長…

問題 atcoder.jp整数が与えられる。総和がとなる数列の個数を求めよ. ただし、すべての項は3以上の整数である. 解法 ・であるから、数え上げる数列の最大の長さはを超えない. ・また、ある項を使うとすると、までの長さが求まっていれば良い. ・動的計画法. …