Query Sums on Strings O(K^2Q)

https://www.hackerrank.com/contests/university-codesprint-2/challenges/querying-sums-on-strings

続きを読む

Codeforces #399 ABCDE

  • A. Oath of the Night's Watch
  • B. Code For 1
  • C. Jon Snow and his Favrourite Number
  • D. Jon and Orbs
  • E. Game of Stones
続きを読む

右方向の和を求めるBIT

本当にどうでもいい内容です。

以下のように書けば sum(a[0..k]) が求められます。1-indexedのBITを0-indexedとして使うために最初にk++しています。

const int N = 1e5;
int bit[N + 1];

void bitadd(int k, int v) {
	for (k++; k <= N; k += k & -k) {
		bit[k] += v;
	}
}

int bitsum(int k) {
	int sum = 0;
	for (k++; k > 0; k -= k & -k) {
		sum += bit[k];
	}
	return sum;
}

以下のように書けば sum(a[k..n-1]) が求められます。addとsumのfor部分が逆になっただけですね。

const int N = 1e5;
int bit[N + 1];

void bitadd(int k, int v) {
	for (k++; k > 0; k -= k & -k) {
		bit[k] += v;
	}
}

int bitsum(int k) {
	int sum = 0;
	for (k++; k <= N; k += k & -k) {
		sum += bit[k];
	}
	return sum;
}

考え方は普通のBITと同じです。BITの原理をよく理解してない方は、これを練習問題だと思って考えてみると良いと思います。

実際に以下のコードを走らせてみましょう。

#include <iostream>

using namespace std;

const int N = 1e5;
int bit[N + 1];

void bitadd(int k, int v) {
	for (k++; k > 0; k -= k & -k) {
		bit[k] += v;
	}
}

int bitsum(int k) {
	int sum = 0;
	for (k++; k <= N; k += k & -k) {
		sum += bit[k];
	}
	return sum;
}

int main() {
	for (int i = 0; i < 10; i++) {
		bitadd(i, i + 1);
	}
	for (int i = 0; i < 10; i++) {
		cout << bitsum(i) << " ";
	}
	cout << endl;
}

実行結果は以下のようになります。

55 54 52 49 45 40 34 27 19 10


こんなことしなくてもk=n+1-kと変換すればいいだけの話ですし、和なら左方向だけ分かれば十分です。minBITのときに役に立つかなぁと思って書きました。

Codeforces Round #397 F. Sourvenirs

高速化できたので追記しました。

http://codeforces.com/contest/765/problem/F

続きを読む

Codeforces Round #397 ABCDE

  • A. Neverending competitions
    • 問題概要
    • 解法
  • B. Code obfuscation
    • 問題概要
    • 解法
  • C. Table Tennis Game 2
  • D. Artsem and Saunders
  • E. Tree Folding
続きを読む