問題概要 長さNの01文字列Sが与えられる。M個の数字ペア(Li, Ri)が与えられ、Sの区間[Li, Ri]の文字を自由に並び替える、という操作を順に行ったあとのSとしてありうるものが何通りあるか求めよ。ただしLiは必ず昇順になっているものとする。 N, M <= 3000 …

https://atcoder.jp/contests/tenka1-2016-final/tasks/tenka1_2016_final_c 問題概要 文字列SとM要素の文字列の集合Pが与えられる。SからPの要素を取り除くと、取り除いた要素に対応する点数Wが与えられる。任意の回数この操作を行ったときの、得られる点数…

https://atcoder.jp/contests/yahoo-procon2017-final-open/tasks/yahoo_procon2017_final_c 問題概要 整数MとN要素の数列Aが与えられるので、以下の形のQ個のクエリを順に処理せよ。 クエリ: Aの区間[l, r]の全要素にxを加算する。その後、同じ区間内にMの…

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

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

問題概要 AチームとBチームにわかれて対戦するゲームがある。このゲームでは試合終了後に各プレイヤーのリザルトとしてkill数とdeath数が表示される。リザルトは各チームごとにkill数の多いプレイヤーから順に表示される。kill数が同数の場合はdeath数の少な…

問題概要 K階建ての棟がN個あり、棟a_iのある階と棟(a_i+1)のある階を結ぶ渡り廊下がM個ある。「コスト0で渡り廊下を渡る」「コスト1で同じ棟の1つ上または1つ下の階に移動する」の2種類の移動が行えるとき、棟1のS階から棟NのT階へ移動するために必要なコス…