ARC071_E TrBBnsformBBtion

問題

‘A'と'B'からなる文字列に対して

  1. ‘A’ -> ‘BB'、'B’ -> ‘AA'と変換
  2. ‘AAA'か'BBB'という部分文字列を削除

のいずれかの操作が可能である。 文字列S, TとQ個のクエリ(ai,bi,ci,di)が与えられる。各クエリは部分文字列S[ai]…S[bi]、T[ci]…T[di]に対応しており、両者を同じ文字列に変換できるかを判定せよ。

方針

全部の文字列をA(もしくはB)に置き換え、文字列の長さの差が3で割り切れれば同じ文字列にすることができ、そうでなければ出来ない。

ここでは、文字列を全てAにして比較する。 クエリごとに文字列の比較をしていくと間に合わないので、事前に累積和を計算しておく。 ここでいう累積和は、文字列をすべて'A'に変換するとき、i番目までの文字数である。 文字列S,Tそれぞれについて、Aなら1、Bなら2の足していく。

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;

int main() {
    string s, t;
    cin >> s >> t;
    vector<int> s_sum(100010), t_sum(100010);
    for(int i=0;i<s.size();i++) {
        int add;
        if(s[i] == 'A') add = 1;
        else add = 2;
        s_sum[i+1] = s_sum[i] + add;
    }
    for(int i=0;i<t.size();i++) {
        int add;
        if(t[i] == 'A') add = 1;
        else add = 2;
        t_sum[i+1] = t_sum[i] + add;
    }


    int q;
    cin >> q;
    vector<string> ans;
    for(int i=0;i<q;i++) {
        int a, b, c, d, num_s, num_t;
        cin >> a >> b >> c >> d;

        num_s = s_sum[b] - s_sum[a-1];
        num_t = t_sum[d] - t_sum[c-1];
        if(abs(num_s-num_t)%3 == 0)
            ans.push_back("YES");
        else
            ans.push_back("NO");
    }
    for(int i=0;i<q;i++) 
        cout << ans[i] << endl;
}

ARC071_D 井井井 / ###

問題

x軸に水平な直線がm本、y軸に水平な直線がn本引いてある。この中に存在している全ての長方形の面積を求める。

方針

x軸、y軸をそれぞれ別々に考える。x軸y軸それぞれについて、すべてのx[i] - x[j] (i >j)(y軸の場合(y[i]-y[j])の値を計算し、その結果をかけ合わせれば良い。 愚直にやるとまにあわない。のですべての直線の座標について、何回足して、何回引けばよいか考える。(x軸、y軸を別々に) 足す回数はx[i] - x[j] でいうところの、x[i]として計算する回数。 引く回数はx[[j]として計算する回数。 ここである座標kについて考える。 x[k]を足す回数(x[i]のところがx[k]になる回数)は k-1回、x[k]を引く回数はn-k回である。 これをy軸についても計算し、それをかければ良い。

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
int main() {
    int n, m;
    cin >> n >> m;
    vector<ll> x(n), y(m);
    for(int i=0;i<n;i++) cin >> x[i];
    for(int i=0;i<m;i++) cin >> y[i];

    ll sum_x = 0, sum_y = 0;
    for(int i=0;i<n;i++) {
        sum_x += i * x[i] - (n-i-1) * x[i];
        sum_x %= mod;
    }
    for(int i=0;i<m;i++) {
        sum_y += i * y[i] - (m-i-1) * y[i];
        sum_y %= mod;
    }

    cout << sum_x * sum_y % mod << endl;
}

AGC012 B - Splatter Painting

 問題

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

方針

Q個の操作をそのままの順番で実行すると、計算量がO(N2)となり間に合わない。 Q個の操作を逆順に行う事を考える。逆順にすると、その操作によって塗られた頂点は二度と上書きされない。 dp[v][d]をつくり、同じ(v, d)について再び計算をしないようにすると(メモ化)、計算量はO(Q+(N+M)*max(di))となるらしい。

#include <iostream>
#include <vector>
#include <utility>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;

vector<int> g[100010];
vector<int> color(100010, 0);
vector< vector<bool> > dp;

void search(int d, int v, int c) {
    if(dp[v][d]) return;
    dp[v][d] = true;
    if(color[v]==0) color[v] = c;
    if(d==0) {
        //color[v] = c; 
        return;
    }
    search(d-1, v, c);
    for(int i=0;i<g[v].size();i++) {
        search(d-1, g[v][i], c);
    }

}

int main() {
    dp = vector< vector<bool> >(100010, vector<bool>(12, false));
    ll n, m;
    cin >> n >> m;
    for(int i=0;i<m;i++) {
        int ai, bi;
        cin >> ai >> bi;
        ai--; bi--;
        g[ai].push_back(bi);
        g[bi].push_back(ai);
    }
    int Q;
    cin >> Q;
    vector<int> v(Q), dv(Q), cv(Q);
    for(int i=0;i<Q;i++) {
        cin >> v[i] >> dv[i] >> cv[i];
        v[i]--;
    }

    for(int i=Q-1;i>=0;i--) {
        search(dv[i], v[i], cv[i]);
    }

    for(int i=0;i<n;i++) {
        cout << color[i] << endl;
    }

}

codeforces #406 B. Not Afraid

方針

各グループについて、絶対値が等しい正負の値のペアが存在するか探索。 ペアが存在するグループは少なくとも全員がtraitorというわけではない。 ペアが存在しない場合は、グループ全員がtraitorの可能性がある。 一つのグループでも、グループ全員がtraitorの可能性がアレば"YES",そうでなければ"NO"と出力する。

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

typedef long long ll;

int main() {
    int n, m;
    cin >> n >> m;
    string ans = "NO";
    for(int i=0;i<m;i++) {
        int k;
        cin >> k;
        set<int> st;
        for(int j=0;j<k;j++) {
            int vi;
            cin >> vi;
            st.insert(vi);
        }
        bool traitor = true;
        for(auto itr=st.begin();itr!=st.end();itr++) {
            if(st.count(-*itr)) {
                traitor = false;
                break;
            }
        }
        if(traitor) {
            ans = "YES";
        }
    }

    cout << ans << endl;
}

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 j=0;j<1000;j++) {
            if(b+a*i == d+c*j) {
                ans = b + a * i;
                flag = true;
                break;
            }
        }
        if(flag) break;
    }

    cout << ans << endl;
}