11.4二分特別テーマの問題解

POJ 2018
タイトルリンク
http://poj.org/problem?id=2018
に言及
n個の数を与えて、1つの長さがLより小さくない連続サブシーケンスを求めて、この連続サブシーケンスの平均数ができるだけ大きいことを要求します.一番大きいのはいくらですか.
問題解
試合の時、私の考えは二分子配列の長さlで、それから条件に合っているかどうかを検証します.しかし、これは単調ではないので、このように二分することはできません.試合後の補題では,直接平均値ansを二分し,長さ>=Lの最大連続サブストリング和を求め,これとl*ansを減算し,>=0で条件を満たすことを説明し,そうでなければ平均値の大きさを小さくすることが分かった.
コード#コード#

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define INIT(x) memset(x,0,sizeof(x))
#define eps 1e-8
#define next next_
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x7fffffff;
const int inf = 0x3f3f3f3f;
const int maxn = 200005;
const int N = 105;

inline void read(ll &x) {
    ll f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}

ll n,f;
double b[maxn],s[maxn],a[maxn];

int main() {
	read(n), read(f);
	for(int i=1;i<=n;i++) {
		scanf("%lf",&a[i]);
	} 
	double l = 0, r = 1e6;
	while(r-l>eps) {
		double mid = (l+r) / 2;
		for(int i=1;i<=n;i++) b[i] = a[i] - mid;
		for(int i=1;i<=n;i++) s[i] = s[i-1] + b[i];
		double ans = -1e10;
		double mini = 1e10;
		for(int i=f;i<=n;i++) {
			mini = min(mini,s[i-f]);
			ans = max(ans,s[i]-mini);
		}
		if(ans>=0) l = mid;
		else r = mid;
	}
	cout<<int(r*1000)<<endl;
}

CodeForces - 1073C
タイトルリンク
http://codeforces.com/problemset/problem/1073/C
に言及
長さnのシーケンスが与えられ、シーケンスにはULDRの4つの方向が含まれ、上下左右を表す.次に座標(x,y)を与えて、最小修正シーケンスの長さをどのくらい聞いて、点を(0,0)から出発して、最終的に目標点に到達させることができます.≪ルールの変更|Modify Rule|emdw≫:方向のみを変更できます.追加または減算はできません.修正の最初の位置をl、最後の位置をrと定義すると、修正の長さはr-l+1となり、この長さはできるだけ小さくする必要があります.
問題解
まず、到着できるかどうかを判断し、(x,y)のマンハッタン距離がnより大きいと、到着できないに違いない.次いで、修正された長さdを2分割列挙し、dが条件を満たす場合、r=midとする.二分で条件を満たすか否かを判断するには,これまでのx方向の変位をベクトルdxで表し,dy同理である.列挙区間の場合,ベクトル重畳の原則により,三段ベクトルを加算=(x,y)とすることができる.
コード#コード#

#include 
using namespace std;

const int maxn = 200005;
int n,x,y,dx[maxn],dy[maxn];
string s;

bool check(int f) {
    for(int i=1;i+f-1<=n;i++) {
        int ddx = dx[i+f-1] - dx[i];
        int ddy = dy[i+f-1] - dy[i];
        int sx = dx[i-1], sy = dy[i-1];
        int fx = dx[n] - dx[i+f-1], fy = dy[n] - dy[i+f-1];
        int newx = x-sx-fx, newy = y-sy-fy;
        int dis = abs(newx) + abs(newy);
//		cout<
		if(dis <= f && (f%2 == dis%2)) return true;
    }
    return false;
}

int main() {
    cin>>n>>s>>x>>y;
    for(int i=1;i<=n;i++) {
        if(s[i-1] == 'U') dy[i] = dy[i-1] + 1, dx[i] = dx[i-1];
        else if(s[i-1] == 'D') dy[i] = dy[i-1] - 1, dx[i] = dx[i-1];
        else if(s[i-1] == 'L') dx[i] = dx[i-1] - 1, dy[i] = dy[i-1];
        else dx[i] = dx[i-1] + 1, dy[i] = dy[i-1];
    }
    int l = 0, r = n+1;
    while(l<r) {
        int mid = (l+r) / 2;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    if(check(r)) cout<<r<<endl;
    else cout<<-1<<endl;
    return 0;
}