Codeforces Round #371 (Div. 1)

ク　ソ　コ　ン　テ　ス　ト

A	B	C	D	E	Place
00:04	00:37	00:20	01:36	-	7th

A:
もちろんmultisetなぞ必要なく、偶奇の組み合わせごとに何個あるか持っておけばよい。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[20];
int c[1<<18];
int main(){
	int a;scanf("%d",&a);
	while(a--){
		scanf("%s",in);
		long long b;
		scanf("%I64d",&b);
		if(in[0]=='+'){
			int now=0;
			for(int i=0;i<18;i++){
				if(b%2)now+=(1<<i);
				b/=10;
			}
			c[now]++;
		}else if(in[0]=='-'){
			int now=0;
			for(int i=0;i<18;i++){
				if(b%2)now+=(1<<i);
				b/=10;
			}
			c[now]--;
		}else{
			int now=0;
			for(int i=0;i<18;i++){
				if(b%2)now+=(1<<i);
				b/=10;
			}
			printf("%d\n",c[now]);
		}
	}
}

B:
二分探索でどこに上下左右の辺があるかがわかる。あとはどの辺がどの長方形に対応しているのかを全部試せばよい。結構実装がトリッキー。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int chk(int a,int b,int c,int d){
	if(a>c||b>d)return 0;
	printf("? %d %d %d %d\n",a,b,c,d);
	fflush(stdout);
	int ret;scanf("%d",&ret);
	return ret;
}
int val[4][2];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<4;i++){
		for(int j=0;j<2;j++){
			int left=0;
			int right=a+1;
			while(left+1<right){
				int M=(left+right)/2;
				int T,B,L,R;
				if(i==0){
					T=1;B=M;L=1;R=a;
				}else if(i==1){
					T=M;B=a;L=1;R=a;
				}else if(i==2){
					T=1;B=a;L=1;R=M;
				}else{
					T=1;B=a;L=M;R=a;
				}
				int val=chk(T,L,B,R);
				if(val>j){
					if(i%2==0){
						right=M;
					}else{
						left=M;
					}
				}else{
					if(i%2==0){
						left=M;
					}else right=M;
				}
			}
			if(i%2==0){
				val[i][j]=right;
			}else val[i][j]=left;
		}
	}
	for(int i=0;i<8;i++){
		if(chk(val[1][0],val[3][i/4],val[0][i%4/2],val[2][i%2])&&chk(val[1][1],val[3][!(i/4)],val[0][!(i%4/2)],val[2][!(i%2)])){
			printf("! %d %d %d %d %d %d %d %d\n",val[1][0],val[3][i/4],val[0][i%4/2],val[2][i%2],val[1][1],val[3][!(i/4)],val[0][!(i%4/2)],val[2][!(i%2)]);fflush(stdout);
			return 0;
		}
	}
}

C:
何度同じ問題が出れば気が済むんだ...

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int b[3100];
long long dp[3100][3100];
int z[3100];
long long ABS(long long a){
	return max(a,-a);
}
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",b+i);
	for(int i=0;i<a;i++)b[i]-=i;
	for(int i=0;i<a;i++)z[i]=b[i];
		std::sort(z,z+a);
	for(int i=0;i<3100;i++)for(int j=0;j<3100;j++)dp[i][j]=inf;
	dp[0][0]=0;
	for(int i=1;i<=a;i++){
		long long tmp=inf;
		for(int j=0;j<a;j++){
			tmp=min(tmp,dp[i-1][j]);
			dp[i][j]=tmp+ABS(b[i-1]-z[j]);
		}
	}
	long long ret=inf;
	for(int i=0;i<a;i++)ret=min(ret,dp[a][i]);
	printf("%I64d\n",ret);
}

D:
そういや最大長方形忘れてたなと思ってググった。
クエリの中で二分探索をすると、答えがk以上かどうか判断するのは、長方形内の値の最大値がわかれば容易。
計算量が中途半端にきつく、そのままsegtreeとかにしてしまうと落ちる。1Dでも2Dでもいいのでsparse tableにしておけば、オーダーがわずかに落ちて間に合う。(いかにも強引に通してしまった別解のような解法だが、実際解説にはこれが書かれています......)

スパソを貼ったらポインタの代入がわからないので適当に配列に書き換えた。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;

int segtree[2048][11000];
void buildRMQ(int *a, int n,int to) {
  int logn = 1;
  for (int k = 1; k < n; k *= 2) ++logn;
  int *r = new int[n * logn];
  int *b = r; copy(a, a+n, b);
  for (int k = 1; k < n; k *= 2) {
    copy(b, b+n, b+n); b += n;
    for(int i=0;i< n-k;i++) b[i] = min(b[i], b[i+k]);
  }
for(int j=0;j<n*logn;j++)segtree[to][j]=r[j];
}
int minimum(int x, int y, int *rmq, int n) {
  int z = y - x, k = 0, e = 1, s; // y - x >= e = 2^k なる最大 k
  s = ( (z & 0xffff0000) != 0 ) << 4; z >>= s; e <<= s; k |= s;
  s = ( (z & 0x0000ff00) != 0 ) << 3; z >>= s; e <<= s; k |= s;
  s = ( (z & 0x000000f0) != 0 ) << 2; z >>= s; e <<= s; k |= s;
  s = ( (z & 0x0000000c) != 0 ) << 1; z >>= s; e <<= s; k |= s;
  s = ( (z & 0x00000002) != 0 ) << 0; z >>= s; e <<= s; k |= s;
  return min( rmq[x+n*k], rmq[y+n*k-e+1] );
}
int dp[1010][1010];
int f[2048][1100];
int c[1010][1010];
int L,R;
int m;
int query(int a,int b,int c,int d,int e){
	if(d<a||b<c)return 0;
	if(c<=a&&b<=d){
	//	printf("%d %d %d %d\n",a,b,L,R);fflush(stdout);
		int ret=minimum(L,R,segtree[e],m);
		return ret;
	}
	return min(query(a,(a+b)/2,c,d,e*2),query((a+b)/2+1,b,c,d,e*2+1));
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	m=b;
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++)scanf("%d",&c[i][j]);
	}
	for(int i=0;i<a;i++)for(int j=0;j<b;j++){
		if(!c[i][j])continue;
		int tmp=mod;
		if(i==0||j==0)tmp=0;
		else tmp=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]);
		dp[i][j]=tmp+1;
	}

	for(int i=0;i<a;i++)for(int j=0;j<b;j++)
		f[i+1024][j]=-dp[i][j];
	for(int i=2047;i>0;i--){
		for(int j=0;j<b;j++){
			f[i/2][j]=min(f[i/2][j],f[i][j]);
		}
		buildRMQ(f[i],b,i);
	//	segtree[i]=buildRMQ(f[i],b);
	}
	int T;scanf("%d",&T);
	while(T--){
		int p,q,r,s;
		scanf("%d%d%d%d",&p,&q,&r,&s);
		p--;q--;r--;s--;
		int left=0;
		int right=min(r-p+1,s-q+1)+1;
		while(left+1<right){
			int M=(left+right)/2;
			int t1=p+M-1;
			int t2=q+M-1;
			R=s;L=t2;
			//printf("%d %d\n",l,r);
			if(query(0,1023,t1,r,1)<=-M){
				left=M;
			}else{
				right=M;
			}
		}
		printf("%d\n",left);
	}
}