問題 n個のブロックが一列に並んでおり、左からi番目のブロックの重さはa[i]である これらのブロックに対して「まだ取り除かれていないブロックを1つ取り除き、そのブロックと連結なブロックの重さの総和をスコアに加える」という操作をn回行う 操作の列n!通…

問題 各頂点にAかBと書かれた無向グラフが与えられる 好きな頂点から始めて辺を辿って移動し、通った頂点に書かれた文字を順に並べて文字列を作る このとき文字A、Bのみからなる任意の文字列が作れるかどうかを判定2 1 解法 グラフが条件を満たすとき、ある…

問題 数直線上にn個のゴミがあり、左からi番目は位置a[i]にある これらを全て位置0にあるゴミ箱に入れたい ロボットが最初位置0にいて、ゴミをk個持っている状態で距離1だけ移動するには(k+1)^2だけエネルギーを使う またゴミを1個拾うのと持っているゴミを…

問題 頂点数がnで全てのi=1,2,...,nについて頂点iと最も遠い頂点の距離がa[i]となるような木が作れるか判定 解法 ↓木が作れる場合の作り方 まずk = max(a,a+n)とし、直径kの一直線な木を作る(写真の青色部分) それで余った頂点iは、最も遠い頂点との距離がa[…

問題 長さnの数列が与えられる これを以下の操作を繰り返して単調増加に並べたい 操作1) 連続する2要素を選び反転する 操作2) 連続する3要素を選び反転する 後者は何度でもしていいとき、前者を最小で何回行う必要があるか求める1 解法 まず操作2だけでソー…

問題 n頂点の木が与えられる この木の直径をk以下にするために削除する必要のある頂点数の最小値を求める2 解法 木の直径をDとすると、 Dが偶数のとき) ある頂点vが存在し、vから他の頂点への距離がD/2以下となる Dが奇数のとき) ある辺eが存在し、eから他の…

問題 長さ2Nの文字列Sを「赤色で塗った文字列を左から右に読んだもの と 青色で塗った文字列を右から左に読んだもの が同じになる」ように塗る方法は何通りあるか求める 解法 半分全列挙 前半N文字の塗り方を決め、赤/青で塗った文字列をx/yとすると、条件を…