問題ページ 解法 dp[i][j] = (頂点i以下の部分木で使用したパスにおいて頂点iの次数がjのときの最大値) としてdpする。(頂点vの部分木において)頂点vを端点とする辺を使用しない場合、子の部分木はどのような選び方をしていたとしても問題ないため遷移は dp[…

問題ページ 解法 dp[i]=(i個分スペースを埋める方法が何通りあるか)としたDPを考える。i個スペースを埋めるためにはmagic gemを一つ置くパターンとmagic gemを分割しnormal gemをM個置くパターンがある。したがってこのDPの遷移は dp[i] = dp[i-m] + dp[i-1]…

問題ページ 解法 i日目に到達可能な場所がどのようになっているのか考える。(x1,y1)=(0,0)、s="UDRL"のときの例を以下に示す。 風が吹く方向と逆方向に移動すればi日目で到達したマスはi+1日目以降でも到達可能なことがわかる。したがってi日目にはi以下の地…

問題ページ 解法 立方体の上の面と底面を決めると残りの側面に来る面の色配置は一意に定まる。色の配置がvのタイルが何枚あるか？という情報を計算しておけば何通りあるかは求めることができる。C(N,2)通りを全通り試すことで答えが求まる。 ただし、回転等…

問題ページ 解法 まずKが偶数ならば(K/2, K, …, K)となる数列が答えになることがわかる。よってKが奇数のものについてのみ考える。 ナイーブな解法として答えの数列でi番目で数列のa番目をつくるにはi番目の数字が一意に定まるとして前から決めていくような…

問題ページ 解法 まずマンハッタン距離なので45度回転しチェビジェフ距離に変換しておく。 コンパスの移動で穴2つの距離が変わることはない。したがって穴aと穴bの距離Dと等しい穴の組が何個あるのかを考えればよい。穴の組O(N^2)個について全て考えるのは不…

問題ページ 解法 dp[i][j] = (結果の列のi+j番目まで見たときに赤をi個、青をj個使っているとき何通りあるか) でDPをする。DPの遷移は dp[i+1][j] += dp[i][j] 次に赤を置くことが可能 dp[i][j+1] += dp[i][j] 次に青を置くことが可能 の2通りになる。次に赤…

問題ページ 解法 とりあえず散歩によって作れる列がどのようなものであるのか実験する。ある区間を往復するときに大きく往復するのではなく一つずつ独立に往復していくと考えられるので各要素は独立に値を決められる。いろいろ実験していると数列の取りうる…

問題ページ 解法 辞書順最小を求めるときは前から貪欲に決めていくのが典型。まずv[1]=1と決めてみたときに残りの木の状態と操作回数とコイン枚数について条件を満たせるのであればv[1]=1と決定してしまってよい。条件を満たさないのであればv[1]=2として同…

問題ページ 解法 boruvka法を使って最小全域木問題を解く。各連結成分から他の連結成分へつなぐ最もコストが小さい辺をO(N)やO(NlogN)程度で求められるときに有効な方法になる。ある区間が他の区間と交差するのは4パターンに分類できる。 その区間の右側と他…