D - Restore the Tree 概要 頂点の有向根付き木がある。 この木に本の辺を追加する。ただし追加する辺をとすると、はの祖先でなければならない。 追加された辺を含む全ての辺が与えられたとき、各頂点について元の根付き木における親を出力せよ。 制約 方針 …

概要 項の数列とが与えられ、二人でゲームを行う。 先手が数字iを選ぶと全体の得点に加算され、後手が数字iを選ぶと全体の得点から減算される。 先手は全体の得点を最大化、後手は全体の得点を最小化させたい。 二人が最適に行動するとき、全体の得点の最大…

D - 浮気予防 概要 頂点辺の無向グラフと項の数列が与えられる。はからまでの整数からなり、相異なる。グラフの頂点は0-indexed。 グラフのうちいくつかの辺を通行止めにし、その状態で頂点から各頂点にいくつ行けるかを考える。 このとき、「通行止めにする…

ABC085 B - Kagami Mochi (200) B - Kagami Mochi 概要 項の数列のうち、相異なる項は最大いくつあるか。 制約 方針 数字をsetに入れてsetのサイズを出力する。 感想 set初使用。setがないと100までのbool配列に数字の出現の有無を記録して解いたと思う。 se…

CODE THANKS FESTIVAL 2017 C - Factory (300) C: Factory - CODE THANKS FESTIVAL 2017(Parallel) | AtCoder 概要 項の数列が与えられる。から数を回選んでその合計を求めることを考える。ただし、各は一度選ばれるごとにが加算されるものとする。 数を回選…

ABC032 D - ナップサック問題 D - ナップサック問題 概要 0/1ナップサック 制約が3種類 制約 ① ② ③ 方針 実質３問。 ① いわゆる半分全列挙。 荷物を前半分、後半分の２つに分け、それぞれですべての荷物の入れ方で重さの合計、価値の合計のペアをベクトルに…

概要 項の数列が与えられる。この数列の隣接2項を足し合わせて1つの項にまとめることを繰り返し、最終的に1つの項からなる数列に変換することを考える。 項と項をまとめる際、のコストがかかるとする。最終的に1つの項にするための必要なコストの最小値を求…

D - Various Sushi 概要 項の数列とが与えられる。この中から項を選び（とで添字共通）、「の項の和(の項に現れる数値の種類数の2乗) 」(と呼ぶ)を最大化せよ。 制約 方針 ①先にを降順ソートし、先頭から項を使用してを計算する。 ②その後、それ以降の数列を…

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

B - 大吉数列 (Array of Fortune) 概要 整数が与えられる。次の条件を満たす数列が存在すればその数列を1つ出力し、存在しなければNo Luckと出力せよ。 数列にはからまでの各数字がちょうど1回現れる を満たすの組（）がちょうど個存在する 制約 方針 極端な…

D - Double Landscape 概要 項の数列と、項の数列が与えられる。 マスにからまでの数字を1つずつ入力することを考える。 各について、行目に入力された数字の最大値が、行目に入力された数字の最大値がであることを満たすような数字の入力方法は何通りあるか…

概要 与えられた数列に対して、数列を下記のように構成したい。 すべてのに対し、 との総和が等しい はなるの数が最小になるように構成したい。この最小値を出力せよ。 また、が構成できないときは-1を出力せよ。 制約 方針 の総和がの総和より小さいとき、…

C - Alternating Path 概要 のマスがあり、各マス目は黒または白に塗られている。 黒のマスと白のマスの組で、からまで下記の移動方法により到達可能な組の個数を求めよ。 上下左右の隣接マスへの移動を繰り返す 黒、白、黒、白…と色マスを交互に通るように…

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

概要 数列が各山の石の数を表す山ニムを行う。 後手があらかじめ各山から多くとも1つの石を除いてよいとするとき、後手必勝となるために除く最小の石の個数を出力せよ。 また、どのように石を除いても後手必勝とならないときは、-1を出力せよ。 制約 方針 山…

E - Union (400) E - Union 概要 数列が与えられる。からまでの整数について、下記操作を考える。 整数を個以下の個数書き出す。 書き出した整数について、整数が2つあれば、その2つを消し、かわりにを1つ書き出す。 この操作を繰り返し、最終的に書き出され…

AOJ DPL1_C ナップザック問題 概要 重さ、価値の荷物が個ある。 重さの合計が以内になるように荷物を選んだ時、荷物の価値の合計の最大値を求めよ。 ただし、同じ荷物を何度選んでもよい。 制約 方針 番目までの荷物を使い、重さが以内であるときの価値の最…

B - Removing Blocks (600) B - Removing Blocks 概要 個のブロックが横に並べてあり、左から番目のブロックにはコストが対応している。 これらのブロックを１つずつ全て壊していくことを考える。また、ブロックを壊すとき、と連結なすべてのブロック(ブロッ…

B - Inscribed Bicycle (500) B - Inscribed Bicycle 概要 ３頂点からなる三角形について、 三角形の内部に半径が同じ２つの円を重ならないように配置するとき、 配置できる円の半径の最大値を求めよ。 制約 方針 半径が最大となるとき、２円は接している。 …