問題 長さの数列に、以下の合計個のクエリを実行した結果を求める。 とをスワップ を昇順に並び替える atcoder.jp 考察 1つ目のクエリはで実行可能なので、2つ目のクエリを高速に行う方法を考える。 数列の転倒数は、1つ目のクエリでは1増減し、2つ目のクエ…

問題 長さの数列[A_1, \cdots, A__N]から個の要素を選んで部分数列を作る。 要素を選ぶときは、要素ごとに以上開ける必要がある。 辞書順で最小の数列を求める。 考察 のとき、部分列を作ることはできない。 以下、を仮定する。 同じ数字が複数あり、どちら…

問題 ある食堂では日目、日目、日目に料理が提供される。 社員それぞれについて、以下の条件で食堂に通うとき、回目に利用するまでに料理を食べる回数を求める。 初めて食堂を利用する日は日目である。 初めて食堂を利用して以降、料理が提供される日は必ず…

問題 個の敷地（番目の敷地の範囲は、コストは）がある。 座標にあるビルのコストは、その座標を含む敷地のコストの和。 軒のビルのコストを求める。 atcoder.jp 考察 考える平面が広いので、座標圧縮を行う。 以降、圧縮後の座標で考える。 あるビルのコス…

問題 体の所持モンスターから4匹以上、体のお助けモンスターから0匹以上選んでモンスターを合成する。 合成されたモンスターの強さは、(使用したモンスターの魔力の和)/(使用したモンスターの質量の和)で定義される。 合成できるモンスターの最大の強さを求…

問題 頂点辺の重みつき単純連結無向グラフが与えられる。 辺は頂点とを結び、重みはである。 辺からそれぞれについて、その辺を含む最小の重みの全域木を求める。 atcoder.jp 考察 与えられた連結グラフの最小の重みの全域木とその重みを求める。 この全域木…

問題 偏りのない個の6面サイコロがあり、番目のサイコロの番目の面には[A_{i,j}]が書かれている。 はじめ、好きなサイコロを1つ選んで出た目をとする。以降、次の操作を可能な限り繰り返す。 好きなサイコロを1つ選んで出た目をとする。ならとし、そうでない…