F - LCS 概要 英小文字からなる文字列がある。 の最長共通部分列(Longest Common Subsequence)を求めよ。 制約 方針 次のステップで求める。 のLCSの長さをDPで求める。 上記のDP配列よりLCSを復元する。復元方法としてはDP配列が更新されたタイミングの文字…

概要 枚のコインがあり、コインの表が出る確率はである。 枚のコインをすべて投げるとき、表の枚数が裏の枚数を超える確率を求めよ。 制約 は奇数 方針 dp[i][j] : コインをi枚使い、表がj枚である確率 としてDPする。 解答 #include <bits/stdc++.h> #define FOR(i,a,b) fo</bits/stdc++.h>…

H - Grid 1 概要 のグリッドがある。このグリッドは空マス.か壁#のいずれかで構成される。 左上のマスから、右・下への移動のみを繰り返し、かつ空マスのみを通りながら右下のマスに移動する。 このとき、移動方法の場合の数を求めよ。（mod で出力する） 制…

E - Knapsack 2 概要 個の品物があり、品物の重さが、価値がであるとする。 それぞれの品物高々1つナップサックに詰める。ナップサックに入れる品物の重さの総和を以下とするとき、 ナップサックに詰める品物の価値の総和の最大値を求めよ。 制約 方針 dp[i]…

D - Knapsack 1 概要 個の品物があり、品物の重さが、価値がであるとする。 それぞれの品物高々1つナップサックに詰める。ナップサックに入れる品物の重さの総和を以下とするとき、 ナップサックに詰める品物の価値の総和の最大値を求めよ。 制約 方針 dp[i]…

概要 数列が与えられる。 1以上N以下の各整数iについて、から1つ選び、総和を最大にしたい。 ただし、連続するiで同じ種類の数列の数値をとれないものとする。総和の最大値を出力せよ。 制約 方針 dp[i][j] : i日目に行動j(0:a, 1:b, 2:c)を行った時の幸福度…

B - Frog 2 概要 数列がある。この数列を0とばし、1とばし、… 、とばしのいずれかで進む。 からに進むとき、コストがかかる。 からに進むときのコストの総和の最小値を求めよ。 制約 方針 A問題同様、コストを配列にする。 A問題は1個前からの移動、2個前か…

A - Frog 1 概要 数列がある。この数列を0つとばし、1つとばしのどちらかで進む。 からに進むとき、コストがかかる。 からに進むときのコストの総和の最小値を求めよ。 制約 方針 コストを配列にする。 まで進むときの最小コストをとすると、は下記の通り遷…