2018-01-24から1日間の記事一覧

みんなのプロコン (2017) 本選 C - 倍数クエリ

問題概要 整数MとN要素の数列Aが与えられるので、以下の形のQ個のクエリを順に処理せよ。 クエリ: Aの区間[l, r]の全要素にxを加算する。その後、同じ区間内にMの倍数が何個あるかを出力する。 N, M, Q <= 105 A_i <= 109 解法 平方分割をする。 平方分割に…

みんなのプロコン (2017) 本選 B - チーム決め

問題概要 N要素の数列AとM要素の数列Bが与えられる。数列からK個の要素を選んで任意の順序で並べる、という操作を両方の数列に対して行ってできる数列をX, Yとする。好きな選び方ができるとき、max(|X_1-Y_1|, ..., |X_K - Y_K|)の最小値を求めよ。 N, M <= …

みんなのプロコン (2017) 本選 A - YahooYahooYahoo

問題概要 与えられた文字列Sに対して以下の3種類の操作をひとつ選んで適用する、ということを繰り返し、Sを"yahoo"という文字列が0回以上繰り返された形にしたい。最小何回の操作でこれを達成できるか求めよ。 操作1: Sの任意の1文字を別の文字に置き換える …