問題概要 横M、縦Nの二次元フィールドに辺がx軸y軸とそれぞれ平行な長方形の障害物がP個ある。i個目の障害物はCiの金で撤去可能であり、与えられた予算はBである。このフィールド上にできるだけ広い正方形の土地を確保せよ。 1 1 1 次の3つのテストグループ…

問題概要 数直線上にいくつかの点のペアが存在し、その片方に乗るともう片方に飛ばされるように(テレポートするように)なっている。全ての点の座標は1以上で2,000,000以下。同じ座標に複数の点は存在しない。この数直線上で0から出発し、どんどん右へ進んで…

問題概要 LとPのみからなるN文字の文字列であり、どの連続した区間をとっても一方の文字が他方の文字より3文字以上多いことがないという制約を満たす文字列がひとつ与えられる。与えられた文字列が、この制約を満たす文字列のうち辞書順で何番目かを求めよ。…

問題概要 N個の頂点とN個の辺を持ち、どの頂点も最低1つの辺で接続されているような重み付き無向グラフが与えられる。好きな頂点から出発して、次のどちらかの移動を繰り返す。ただし同じ頂点に2度訪れることはできない。 辺を辿って移動する。 どのように辺…

問題概要 スタックが1個あって、次の3つの操作が許されている。 文字を1つpush 文字を1つpop スタックの底から頂点までをなぞって文字列を印字する さて、N個の文字列が与えられるので、上の3つの操作をできるだけ少ない回数だけ使ってこれらの文字列を全て…

解法 まず木の節点の番号をpreorderで付け直す。すると、ある節点の子の節点の番号は連続する整数になるので、全ての節点についてその子の節点番号の区間を計算しておけば「節点bは節点aの子か？」という問にO(1)で答えることができて便利。これは木を辿るだ…

解法 難しすぎる。説明するよりソース見た方が早いところもあるのでとりあえず基本的な方針だけ説明する。ソースにはコメントをしっかり書いておいたのでそれなりに読めるはず。まず、順位が1の射手について考えると、何ラウンドか経った後に的1に来て、その…

解法 まず各労働者iについて、値 Si / Qiを考える。これについて以下のことがわかる。 Sa / Qa b / Qb のとき、労働者bを給料Sbで雇うと労働者aは給料(Qa / Qb) * Sb で雇える 労働者bを給料Sbで雇ったとき、法律の規定で労働者aには(Qa / Qb) * Sb以上の給…

解法 dp[r1][c1][r2][c2] := 左上(r1, c1)、右下(r2, c2)の長方形部分をカットするときの最小コストとしてDPすればよい。実装はメモ化再帰の方が楽だし部分問題全部解くから時間的にも問題はない。実行時間は O(N2M2(N+M)) と大きめだが N, M

解法 ソートしよう！！！！！！！