問題概要 東西に一列に並ぶN個の島と、それをつなぐN-1個の橋がある。 a_iとb_iの間を行き来できないようにしろ、という要望がM個寄せられた。 取り除かなければならない橋の本数の最小値を求めよ。 制約 2 <= N <= 105 1 <= M <= 105 1 <= a_i < b_i <= N …

問題概要 https://beta.atcoder.jp/contests/summerfes2018-div2/tasks/summerfes2018_e 制約 2 <= N <= 105 考察 2次元のやつを眺めてたら三角数の並びしてたから、n次元に拡張されたものあるやろっておもったらほんとにあった n次元三角数の式をこねくり回…

問題概要 それぞれX_i両目の車両にいるM人の整備士が、N両編成の電車をすべて点検し終えるのに最短で何分かかるか求めよ。但し、点検には時間はかからないが、隣の車両に移動するのには1分かかるものとする。 制約 1 <= N <= 109 1 <= M <= 105 M <= N 1 <= …

問題概要 文字列sの中に、過半数が同じ文字となる2文字以上の部分文字列t(アンバランスな部分文字列)は存在するか判定せよ。tが存在するならその区間を、しないなら-1 -1を出力せよ。 制約 2<=|s|<=105 sは小文字のアルファベットのみからなる。 考察 tは2文…