結果 Hardが運良く(1.994sかかるケースがあった)通って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)で答えることができて便利。これは木を辿るだ…