問題 ‘A'と'B'からなる文字列に対して ‘A’ -> ‘BB'、'B’ -> ‘AA'と変換 ‘AAA'か'BBB'という部分文字列を削除 のいずれかの操作が可能である。 文字列S, TとQ個のクエリ(ai,bi,ci,di)が与えられる。各クエリは部分文字列S[ai]…S[bi]、T[ci]…T[di]に対応してお…

問題 x軸に水平な直線がm本、y軸に水平な直線がn本引いてある。この中に存在している全ての長方形の面積を求める。 方針 x軸、y軸をそれぞれ別々に考える。x軸y軸それぞれについて、すべてのx[i] - x[j] (i >j)（y軸の場合(y[i]-y[j])の値を計算し、その結果…

方針 昇順にソートして、それぞれの累積和を計算しておく。すると、i番目の生き物が他のすべての生き物と合体するためには、0<=i<=n-2について(0から始まるインデックス基準）、(i番目の累積和)*2 >= (i+1番目の生物の大きさ）を満たしている必要がある。逆…

方針 やるだけなのにやけに時間がかかった。自分はアルゴリズム云々の前に、こういう基本的なプログラムの挙動に対する直感がかけているのかも？ #include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long ll; int main() { ll n, c, k; cin ></algorithm></vector></iostream>…

概要 N個の整数列が与えられる。連続するK(<=N)個を選び、全てを白で塗るか全てを黒で塗る（この操作は何回でもおこなうことができる）。色は上書きされる。 黒く塗られた整数の総和の最大値をもとめよ 方針 操作順を逆に考える。 そのまま）何回かK個を塗る…