ARC071_E TrBBnsformBBtion

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

ARC071_D 井井井 / ###

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

AGC012 B - Splatter Painting

問題 N個の頂点とM個の辺のグラフが与えられる。最初、頂点は全て色0で塗られている。 それぞれの辺の長さは1である。 さらに、Q個の操作が与えられる。各操作は vi, di, ciという形式で与えられる。この意味は、頂点viから距離di以内にある頂点を色ciで上書…

codeforces #406 B. Not Afraid

方針 各グループについて、絶対値が等しい正負の値のペアが存在するか探索。 ペアが存在するグループは少なくとも全員がtraitorというわけではない。 ペアが存在しない場合は、グループ全員がtraitorの可能性がある。 一つのグループでも、グループ全員がtra…

codeforces #406 A. The Monster

方針 法則性とか考えないで総当りでいけるっぽい #include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long ll; int main() { int a, b, c, d; cin >> a >> b >> c >> d; int ans = -1; for(int i=0;i<1000;i++) { bool flag = false; for(int</algorithm></vector></iostream>…

ABC D - Maximum Average Sets

#include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <iomanip> typedef long long ll; using namespace std; int main() { int n, a, b; cin >> n >> a >> b; vector<ll> v(n); for(int i=0;i<n;i++) { cin >> v[i]; } sort(v.begin(), v.end(), greater<ll>()); int max_cnt = 0; int…</ll></n;i++)></ll></iomanip></algorithm></cmath></vector></iostream>

Codeforces #405 C. Bear and Different Names

方針 まず、n個の異なる名前を用意。 i番目が"NO"なら、ans[i+k-1] = ans[i]とするとi番目以外のk個のグループには影響がない。 ここで、ans[i] = ans[i+k-1]とすると、ans[i+k-1]が後から更新された場合にこまる。 自分の回答 #include <iostream> #include <vector> #include <algorithm></algorithm></vector></iostream>…

Codeforces #405 B. Bear and Friendship Condition

方針 グラフ中の全ての部分グラフ?で (辺の数)= (頂点の数)*(頂点の数-1) / 2 を満たしていれば “YES"、そうでなければ "NO"と出力。 全探索するために配列 vis[頂点の数] を用意。 dfsでは一つの辺に対して二回ずつカウントしている。 つまり、cnt_e…

Codeforces #403 C. Andryusha and Colored Balloons

方針 解けなかったので他の人の解答をみた。 #include <iostream> #include <vector> #include <set> using namespace std; set<int> c[200010]; vector<int> g[200010], p(200010, 0), a(200010, 0); void dfs(int cur, int pre) { if(pre != -1) { while(c[pre].count(p[pre])) p[pre]++; a[</int></int></set></vector></iostream>…

AGC011_B Colorful Creatures

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

AGC011_A Airport Bus

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

Codeforces #401 C. Alyona and Spreadsheet

概要 n ✕ mの整数テーブルが与えられる。加えて整数kとk個のl[i],r[i]が与えられる。 テーブルのうち、l[i]からr[i]が単調増加(a[i][j] <= a[i][j+1])ならYes, そうでなければNoを出力する。 方針 a[i][j] <= a[i+1][j] かつi

AGC008B Contiguous Repainting

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

2017年の目標

競技プログラミングを始めたので、2017年前半期(〜6月)の目標を記しておく。 競技プログラミング AC数 : 500 AtCoder : 青 topcoder : 青 全般 contribution数 : 500 goとか 論文 論文 : 50本