[伯俊]9600バイナリ三振探査游戏2
白駿19600バイナリ三振探索ゲーム2 https://www.acmicpc.net/problem/19600 エラーの回答
白準19599バイナリ三振探索ゲーム1題の解題を利用して,B[i]とT[i]の部分和を算出すると,タイムアウトが発生する.
2つのクエリの実行回数:N^2
BとTの関数を計算する時間複雑度:約O
->総時間複雑度:約O(N^3∧*☓lgn)
白駿19599バイナリ三振探索ゲーム1題の高速解を用いて,B[i]とT[i]の部分と を算出した.
白準19599バイナリ三振探索ゲーム1題の解題を利用して,B[i]とT[i]の部分和を算出すると,タイムアウトが発生する.
2つのクエリの実行回数:N^2
BとTの関数を計算する時間複雑度:約O
->総時間複雑度:約O(N^3∧*☓lgn)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
vector<int> A;
//Bsum[i][j]: 배열 A의 크기가 i일 때 B[0] ~ B[j]까지의 부분합
ll Bsum[5001][5001] = { 0 };
//Tsum[i][j]: 배열 A의 크기가 i일 때 T[0] ~ T[j]까지의 부분합
ll Tsum[5001][5001] = { 0 };
//A에서 이분 탐색으로 val값을 찾기 위해 필요한 비교 횟수 반환
ll binary_search(int value, int left, int right) {
int mid = (left + right) / 2;
if (A[mid] == value)
return 0;
else if (value < A[mid])
return 1LL + binary_search(value, left, mid - 1);
else
return 1LL + binary_search(value, mid + 1, right);
}
//A에서 삼분 탐색으로 val값을 찾기 위해 필요한 비교 횟수 반환
ll ternary_search(int value, int left, int right) {
int left_third = left + ((right - left) / 3);
int right_third = right - ((right - left) / 3);
if (A[left_third] == value)
return 0;
else if (A[right_third] == value)
return 1LL;
else if (value < A[left_third])
return 2LL + ternary_search(value, left, left_third - 1);
else if (value < A[right_third])
return 2LL + ternary_search(value, left_third + 1, right_third - 1);
else
return 2LL + ternary_search(value, right_third + 1, right);
}
void getPrefixSum() {
//배열 A의 크기 1 ~ 5000일 때 B와 T의 부분합 계산
for (int n = 1; n <= 5000; ++n) {
Bsum[n][0] = binary_search(A[0], 0, n - 1);
Tsum[n][0] = ternary_search(A[0], 0, n - 1);
for (int i = 1; i < n; ++i) {
Bsum[n][i] = Bsum[n][i - 1] + binary_search(A[i], 0, n - 1);
Tsum[n][i] = Tsum[n][i - 1] + ternary_search(A[i], 0, n - 1);
}
}
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
for (int i = 0; i < 5000; ++i)
A.push_back(i);
getPrefixSum();
int Q;
cin >> Q;
while (Q--) {
int N, S, E;
cin >> N >> S >> E;
if (S == 0) cout << Tsum[N][E] - Bsum[N][E] << "\n";
else cout << (Tsum[N][E] - Tsum[N][S - 1]) - (Bsum[N][E] - Bsum[N][S - 1]) << "\n";
}
return 0;
}
に答える#include <algorithm>
#include <iostream>
using namespace std;
//cnt[n][i]: 배열 A의 크기가 n일 때 B[i] - T[i]
int cnt[5001][5001] = { 0 };
//psum[n][i]: 배열 A의 크기가 n일 때 cnt[0] ~ cnt[i]까지의 부분합
int psum[5001][5001] = { 0 };
void binAdd(int n, int s, int e, int add) {
if (s > e) return;
int mid = (s + e) / 2;
cnt[n][mid] += add++;
binAdd(n, s, mid - 1, add);
binAdd(n, mid + 1, e, add);
}
void terSub(int n, int s, int e, int sub) {
if (s > e) return;
if (s == e) {
cnt[n][s] -= sub;
return;
}
int t1 = s + (e - s) / 3;
int t2 = e - (e - s) / 3;
cnt[n][t1] -= sub++;
cnt[n][t2] -= sub++;
terSub(n, s, t1 - 1, sub);
terSub(n, t1 + 1, t2 - 1, sub);
terSub(n, t2 + 1, e, sub);
}
void getPrefixSum() {
//배열 A의 크기 1 ~ 5000일 때 cnt의 부분합 계산
for (int n = 1; n <= 5000; ++n) {
binAdd(n, 0, n - 1, 0);
terSub(n, 0, n - 1, 0);
psum[n][0] = cnt[n][0];
for (int i = 1; i <= n; ++i)
psum[n][i] = psum[n][i - 1] + cnt[n][i];
}
return;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
getPrefixSum();
int Q;
cin >> Q;
while (Q--) {
int N, S, E;
cin >> N >> S >> E;
if (S == 0) cout << -psum[N][E] << "\n";
else cout << -(psum[N][E] - psum[N][S-1]) << "\n";
}
return 0;
}
Reference
この問題について([伯俊]9600バイナリ三振探査游戏2), 我々は、より多くの情報をここで見つけました https://velog.io/@sunjoo9912/백준-19600-이진-삼진-탐색-놀이-2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol