JOI 春合宿 2010 Day 1

JOI

5時間ちゃんと時間測ってやってみた。

JOI ポスター

なんか昔解いた気がするけどまぁやるだけ。
適当に再帰で書きました。
時間かけすぎた気がする。

string rec(int N,int K)
{
	string ret;
	if(!N)return "J";
	if(K>=(1<<(N-1)))
	{
		rep(i,1<<(N-1))ret+='I';
		return ret+rec(N-1,K-(1<<(N-1)));
	}
	else
	{
		rep(i,(1<<(N-1)))ret+='J';
		rep(i,(1<<(N-1)))ret+='O';
		return ret;
	}
}
int main()
{
	int N,K;
	scanf("%d %d",&N,&K);
	cout << rec(N,K-1) << endl;
	return 0;
}
戦国時代

各武将は角の動ける範囲を守れる。
↗方向と↘方向に分けて考える。
それぞれ(x,y)->(x+y,x-y)みたいな変換をしてやると数えられる。
後は重複を引く。重複は各↗方向に対して、かぶりうる↘の範囲を求めて、にぶたんする。
この時偶奇にわけないといけないことに注意。
LとN間違えてて、デバッグでハマった。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
int L,N;
ll ans = 0ll;
vector<int> xy,yx;
vector<int> odd,even;
int x[100100],y[100100];
int main()
{
	scanf("%d %d",&L,&N);
	rep(i,N)scanf("%d %d",&x[i],&y[i]);
	rep(i,N)
	{
		xy.pb(x[i]+y[i]);
		yx.pb(y[i]-x[i]);
		if((y[i]-x[i])%2)odd.pb(y[i]-x[i]);
		else even.pb(y[i]-x[i]);
	}
	sort(all(xy));
	sort(all(yx));
	sort(all(odd));
	sort(all(even));
	xy.erase(unique(all(xy)),xy.end());
	yx.erase(unique(all(yx)),yx.end());
	odd.erase(unique(all(odd)),odd.end());
	even.erase(unique(all(even)),even.end());
	rep(i,xy.size())ans += L-abs(xy[i]-(L-1));
	rep(i,yx.size())ans += L-abs(yx[i]);
	rep(i,xy.size())
	{
		int beg,end,k;
		end = (xy[i]>L-1)?2*L-2-xy[i]:xy[i];
		beg = -end;
		if(xy[i]%2)k = upper_bound(all(odd),end)-lower_bound(all(odd),beg);
		else k = upper_bound(all(even),end)-lower_bound(all(even),beg);
		ans -= k;
	}
	printf("%lld\n",ans);
	return 0;
}
階段

なんの変哲もない普通のDP。segtreeで加速してやるだけ。

#define MOD 1234567
const int SIZE = 1<<19;
struct segtree
{
	int seg[SIZE*2];
	void update(int k,int x)
	{
		k += SIZE-1;
		seg[k]=x;
		while(k)
		{
			k = (k-1)/2;
			seg[k]=(seg[k*2+1]+seg[k*2+2])%MOD;
		}
	}
	int query(int a,int b,int k,int l,int r)
	{
		if(r<=a||b<=l)return 0;
		if(a<=l&&r<=b)return seg[k];
		return (query(a,b,k*2+1,l,(l+r)/2)+query(a,b,k*2+2,(l+r)/2,r))%MOD;
	}
}seg;
int dp[500100];
int h[500100];
int N,P;
int main()
{
	scanf("%d %d",&N,&P);
	for(int i=1;i<=N;i++)scanf("%d",&h[i]);
	rep(i,N+1)h[i+1]+=h[i];
	dp[0]=1;
	seg.update(0,1);
	for(int i=1;i<=N;i++)
	{
		int k = lower_bound(h,h+N+1,h[i]-P)-h;
		if(k<i)dp[i]=seg.query(k,i,0,0,SIZE);
		seg.update(i,dp[i]);
	}
	printf("%d\n",dp[N]);
	return 0;
}

100+100+100=300 (2:03)

終わってからDEGwerさんにこの日はクソ簡単な日だと教えていただいた。
実際簡単でほぼ3時間余らせて全完できたので良かった