M - Candies 概要 項の数列と、整数が与えられる。下記の条件を満たす数列の個数を求めよ。 （出力はmod ） （個の飴を人の子供に配る） 制約 方針 dp[i][j] : i-1番目の子供で飴がj個余るときの分け合う方法数 とし、DPする。 基本的な遷移式は下記の通り。…

L - Deque 概要 数列が与えられ、二人のプレイヤーが交互に数列から数を取り除いてゆき、取り除いた数の得点を得るゲームを行う。 先手の得点を、後手の得点をとするとき、先手はを最大化、後手はを最小化しようとする。 二人のプレイヤーが最適に行動したと…

K - Stones 概要 数列を用いて、二人が次のようなゲームを行う。 最初は石が個ある 自分の手番には、数列の中から1つの数を選び、その数だけ石を減らす。ただし、残りの石の個数より多いような数列の数を選んではいけない 最初に操作できなくなった方を負け…

J - Sushi 概要 数列がある（各皿に乗っている寿司の個数）。「からを等確率で選び（サイコロを振る）、選んだ数字をとするときならから1を引く」という操作（寿司を食べる）を繰り返す。このとき、がすべて0になるまでの操作回数の期待値を求めよ。 制約 方…

G - Longest Path 概要 頂点辺のDAGの最長パスの長さを出力せよ。 制約 方針① まず、トポロジカルソートを行い、頂点の移動順を求める。 トポロジカルソートは帰りがけ順DFSの出力の逆順とする。次に、 : トポロジカルソートで頂点より後ろのパスの最大長 と…

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つとばしのどちらかで進む。 からに進むとき、コストがかかる。 からに進むときのコストの総和の最小値を求めよ。 制約 方針 コストを配列にする。 まで進むときの最小コストをとすると、は下記の通り遷…