読者です 読者をやめる 読者になる 読者になる

ARC 17 A~D

A
素因数分解をしましょう。脳みそが常人の1%にも満たないから2回WAを出す。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <queue>
#include <stack>
#include <tuple>

using namespace std;


typedef long long ll;

int main(int argc, char *argv[]) {
	int N;
	cin >> N;
	for (int i = 2; i*i <= N; i++) {
		if (N % i == 0) {
			printf("NO\n");
			return 0;
		}
	}
	printf("YES\n");
    return 0;
}

B
一瞬詰まるよね。
今何個連続で上昇しているか、と、一個前の値
だけを持っていればよいです。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <queue>
#include <stack>
#include <tuple>

using namespace std;

const int INT_INF = (1 << 29);
typedef long long ll;

int main(int argc, char *argv[]) {
	int N, K;
	cin >> N >> K;
	int d1 = INT_INF, d2;
	int c = 0, r = 0;
	for (int i = 0; i < N; i++) {
		scanf("%d", &d2);
		if (d1 < d2) {
			c++;
		} else {
			c = 0;
		}
		d1 = d2;
		if (K <= c+1) r++;
	}
	printf("%d\n", r);
    return 0;
}

C
半分全列挙?というやつですね
最初の16個が作れる値、65536個を全列挙。
次に後半16個が作れる値を全列挙します。
後半16個が作れる値それぞれについて(Dとする)、前半16個の作れる値のうちX-Dの個数を足していけばいいですね。
X-Dの個数を探すところでは二部探索をしましょう

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <queue>
#include <stack>
#include <tuple>

using namespace std;

const int MAX_N = 33;
typedef long long ll;
ll d[MAX_N];
vector<int> ch;
int main(int argc, char *argv[]) {
	int N;
	ll X;
	cin >> N >> X;
	for (int i = 0; i < N; i++) {
		cin >> d[i];
	}
	if (N <= 16) {
		for (int i = 0; i < (1<<N); i++) {
			int i2 = i;
			ll d2 = 0;
			for (int j = 0; j < N; j++) {
				if (i2 & (1 << j)) {
					d2 += d[j];
				}
			}
			ch.push_back(d2);
		}
		sort(ch.begin(), ch.end());
		printf("%ld\n", upper_bound(ch.begin(), ch.end(), X) - lower_bound(ch.begin(), ch.end(), X));
	} else {
		ll r = 0;
		for (int i = 0; i < (1<<16); i++) {
			int i2 = i;
			ll d2 = 0;
			for (int j = 0; j < 16; j++) {
				if (i2 & (1 << j)) {
					d2 += d[j];
				}
			}
			ch.push_back(d2);
		}
		sort(ch.begin(), ch.end());
		N -= 16;
		for (int i = 0; i < (1<<N); i++) {
			int i2 = i;
			ll d2 = 0;
			for (int j = 0; j < N; j++) {
				if (i2 & (1 << j)) {
					d2 += d[j+16];
				}
			}
			r += upper_bound(ch.begin(), ch.end(), X - d2) - lower_bound(ch.begin(), ch.end(), X - d2);
		}
		printf("%lld\n", r);
	}
    return 0;
}

D

部分点解法

値の更新は1個のみ。
これは普通にセグメントツリーを使いましょう。
それぞれ、自分の子のgcdを持つようにすれば更新、取得ともにO(logn)で出来ます。

満点解法

値の更新が区間になります。
これは部分点解法だと、更新がO(nlogn)になり、間に合いません。
区間更新でも、a[i]-a[i-1]が変わるiはたかだか2つしか無い事に注目しましょう。
差に注目すると、
gcd(a1, a2, a3, ..., an) = gcd(a1, a2-a1, a3-a2, a4-a3, ..., an-a(n-1))
に気づきます。これが等しい証明はユーグリッドの互除法の原理から明らかです。

あとはa2-a1, a3-a2, ..., an-a(n-1)のn-1要素を持つセグメントツリーを考えれば、
更新、取得ともにO(logn)で出来ます。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <queue>
#include <stack>
#include <tuple>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) {
	a = abs(a); b = abs(b);
    if (b==0) return a;
    return gcd(b, a%b);
}

const int SEG_SIZE = 1<<18;
int seg[SEG_SIZE];

void seg_init() {
    for (int i = 0; i < SEG_SIZE; i++) {
        seg[i] = 0;
    }
}

void seg_set(int *seg, int i, int x) {
    i += SEG_SIZE/2 - 1;
    seg[i] = x;
    while (i) {
        i = (i - 1) / 2;
        int s1 = seg[i*2+1], s2 = seg[i*2+2];
        seg[i] = gcd(s1, s2);
    }
}

int seg_get(int *seg, int a, int b, int k = 0, int l = 0, int r = SEG_SIZE/2) {
    if (a <= l && r <= b) return seg[k];
    if (r <= a || b <= l) return 0;
    int vl = seg_get(seg, a, b, k*2+1, l, (l+r)/2);
    int vr = seg_get(seg, a, b, k*2+2, (l+r)/2, r);
    return gcd(vl, vr);
}

ll bit[SEG_SIZE] = {};
int bit_sum(ll *d, int add) {
    add++;
    ll s = 0;
    while (add > 0) {
        s += d[add-1];
        add -= add & -add;
    }
    return s;
}

void bit_add(ll *d, int add, ll x) {
    add++;
    while (add <= SEG_SIZE) {
        d[add-1] += x;
        add += add & -add;
    }
}
int d[SEG_SIZE];
int getd(int i) {
	return bit_sum(bit, i) + d[i];
}
int main(int argc, char *argv[]) {
	int N;
	cin >> N;
	seg_init();
	for (int i = 0; i < N; i++) {
		scanf("%d", &d[i]);
	}
	for (int i = 0; i < N-1; i++) {
		seg_set(seg, i, d[i+1]-d[i]);
	}
	int M;
	cin >> M;
	for (int i = 0; i < M; i++) {
		int t, l, r;
		scanf("%d %d %d", &t, &l, &r);
		l--;
		if (t) {
			bit_add(bit, l, t);
			bit_add(bit, r, -t);
			if (l) {
				seg_set(seg, l-1, getd(l)-getd(l-1));
			}
			if (r) {
				seg_set(seg, r-1, getd(r)-getd(r-1));
			}
		} else {
			printf("%lld\n", gcd(getd(l), seg_get(seg, l, r-1)));
		}
	}
    return 0;
}