Codeforces practice

いちいち一個ずつ記事つくるの面倒なのでまとめる。

一問目
http://codeforces.com/problemset/problem/253/E

仕事がたくさん来て、優先度があって残ってる仕事の中で優先度が一番高いのから処理していく。で、一つ優先度が分からないのがあるから、それを求めなさいとかいう問題。

じつは優先度が高くなると終わる時間は早くなるのでシュミレーション+二分探索で解ける。二分探索がこんなにうまく隠されてる問題なかなか見ない。

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define mt(A,B,C) make_pair(A,make_pair(B,C))
#define mq(A,B,C,D) make_pair(mt(A,B,C),D)
typedef long long ll;
typedef pair<ll,ll>pii;
typedef pair<ll,pii>pi3;
typedef pair<pi3,int>pi4;
ll ret[50000];
ll calc(vector<pi4>inp,int iden)
{
    priority_queue<pi4>que;
    int quesize=inp.size();
    inp.push_back(mq(-1000000000000000000LL,0,0,-1));
    ll now=0;
    ll retu=-1;
    for(int p=0;p<quesize;p++)
    {
        que.push(mq(inp[p].first.second.second,inp[p].first.first,inp[p].first.second.first,inp[p].second));
        pi4 zan=que.top();
        now=max(now,zan.first.second.first);
		for(;;)
		{
			if(que.empty())
			{
				break;
			}
			zan=que.top();
            if(now+zan.first.second.second<=inp[p+1].first.first)
	        {
    		    que.pop();
                now+=zan.first.second.second;
                ret[zan.second]=now;
                if(iden==zan.second)
                {
                    retu=now;
                }
            }
            else
            {
                if(now<inp[p+1].first.first)
                {
                    que.pop();
                    que.push(mq(zan.first.first,zan.first.second.first,zan.first.second.second-(inp[p+1].first.first-now),zan.second));
                    now=inp[p+1].first.first;
                }
				break;
            }
		}
    }
    for(;;)
    {
        if(que.empty())
        {
            break;
        }
        pi4 zan=que.top();
        que.pop();
        now+=zan.first.second.second;
        ret[zan.second]=now;
        if(iden==zan.second)
        {
            retu=now;
        }
    }
    return retu;
}
int main()
{
	FILE *fr=fopen("input.txt","r");
	FILE *fw=fopen("output.txt","w");
    int num;
    fscanf(fr,"%d",&num);
    ll xtim,xsiz,xnum;
    priority_queue<pi4>que;
    map<ll,ll>ma;
    for(int i=0;i<num;i++)
    {
        int za,zb,zc;
        fscanf(fr,"%d%d%d",&za,&zb,&zc);
        if(zc!=-1)
        {
            que.push(mq(-za,zb,zc,i));
            ma[zc]++;
        }
        else
        {
            xtim=za;
            xsiz=zb;
            xnum=i;
        }
    }
    ll ans;
    fscanf(fr,"%I64d",&ans);
    ll beg=1,end=1000000000;
    for(;;)
    {
        ll med=(beg+end)/2;
        vector<pi4>vec;
        priority_queue<pi4>zan=que;
        zan.push(mq(-xtim,xsiz,med,xnum));
        for(;;)
        {
            if(zan.empty())
            {
                break;
            }
            vec.push_back(zan.top());
            vec[vec.size()-1].first.first=-vec[vec.size()-1].first.first;
            zan.pop();
        }
        if(calc(vec,xnum)>ans)
        {
            beg=med+1;
        }
        else
        {
            end=med;
        }
        if(beg==end)
        {
            for(;;)
            {
                if(ma[beg]==0)
                {
                    fprintf(fw,"%I64d\n",beg);
                    priority_queue<pi4>zan=que;
                    zan.push(mq(-xtim,xsiz,beg,xnum));
                    vec.clear();
                    for(;;)
                    {
                        if(zan.empty())
                        {
                            break;
                        }
                        vec.push_back(zan.top());
                        vec[vec.size()-1].first.first=-vec[vec.size()-1].first.first;
                        zan.pop();
                    }
                    calc(vec,xnum);
                    for(int i=0;i<num;i++)
                    {
                        if(i!=0)
                        {
                            fprintf(fw," ");
                        }
                        fprintf(fw,"%I64d",ret[i]);
                    }
                    fprintf(fw,"\n");
                    return 0;
                }
                else
                {
                    beg++;
                }
            }
        }
    }
}

二問目

http://codeforces.com/problemset/problem/240/F

文字列があって、ある区間の文字列をうまいこと並び替えて回文にせよっていうクエリがたくさんくるので適当に処理してください。

回文っていっても回文っぽいことはあまりしなくて、文字ごとに遅延評価木を持っておいて各文字がどこにおいてあるかを更新していくだけ。実装バグった。こういうのが素早く実装できないとJOI合宿つらいので慣れないとなぁ。

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#define SIZE 131072
using namespace std;
class segtree
{
public:
	int seg[SIZE*2];
	bool flag[SIZE*2];
	int update(int beg,int end,int node,int lb,int ub,int num)
	{
		if(ub<beg||end<lb)
		{
			return seg[node];
		}
		if(beg<=lb&&ub<=end)
		{
			flag[node]=true;
			return seg[node]=num*(ub-lb+1);
		}
		if(flag[node])
		{
			seg[node*2]=seg[node]/2;
			flag[node*2]=true;
			seg[node*2+1]=seg[node]/2;
			flag[node*2+1]=true;
			flag[node]=false;
		}
		return seg[node]=update(beg,end,node*2,lb,(lb+ub)/2,num)+update(beg,end,node*2+1,(lb+ub)/2+1,ub,num);
	}
	int sum(int beg,int end,int node,int lb,int ub)
	{
		if(ub<beg||end<lb)
		{
			return 0;
		}
		if(beg<=lb&&ub<=end)
		{
			return seg[node];
		}
		if(flag[node])
		{
			seg[node*2]=seg[node]/2;
			flag[node*2]=true;
			seg[node*2+1]=seg[node]/2;
			flag[node*2+1]=true;
			flag[node]=false;
		}
		return sum(beg,end,node*2,lb,(lb+ub)/2)+sum(beg,end,node*2+1,(lb+ub)/2+1,ub);
	}
};
segtree tree[26];
int main()
{
	FILE *fr=fopen("input.txt","r");
	FILE *fw=fopen("output.txt","w");
	int len,query;
	fscanf(fr,"%d%d",&len,&query);
	string str;
	for(int i=0;i<len;i++)
	{
		char zan;
		fscanf(fr," %c",&zan);
		str.push_back(zan);
	}
	for(int i=0;i<26;i++)
	{
		fill(tree[i].flag,tree[i].flag+SIZE*2,false);
	}
	for(int i=0;i<str.size();i++)
	{
		tree[str[i]-'a'].update(i,i,1,0,SIZE-1,1);
	}
	for(int p=0;p<query;p++)
	{
		int za,zb;
		fscanf(fr,"%d%d",&za,&zb);
		za--;
		zb--;
		int hai[26];
		fill(hai,hai+26,0);
		int numodd=0,rr;
		for(int i=0;i<26;i++)
		{
			hai[i]=tree[i].sum(za,zb,1,0,SIZE-1);
			numodd+=hai[i]%2;
			if(hai[i]%2)
			{
				rr=i;
			}
		}
		if(numodd>=2)
		{
			continue;
		}
		for(int i=0;i<26;i++)
		{
			tree[i].update(za,zb,1,0,SIZE-1,0);
		}
		if(numodd==1)
		{
			tree[rr].update((za+zb)/2,(za+zb)/2,1,0,SIZE-1,1);
			hai[rr]--;
		}
		int now=0;
		for(int i=0;i<26;i++)
		{
			if(hai[i]!=0)
			{
				tree[i].update(za+now,za+now+hai[i]/2-1,1,0,SIZE-1,1);
				tree[i].update(zb-now-hai[i]/2+1,zb-now,1,0,SIZE-1,1);
				now+=hai[i]/2;
			}
		}
	}
	string ret;
	ret.resize(len);
	for(int i=0;i<len;i++)
	{
		for(int j=0;j<26;j++)
		{
			if(tree[j].sum(i,i,1,0,SIZE-1))
			{
				ret[i]=j+'a';
			}
		}
	}
	for(int i=0;i<len;i++)
	{
		fprintf(fw,"%c",ret[i]);
	}
	fprintf(fw,"\n");
}

三問目
http://codeforces.com/contest/11/problem/C

正方形の個数を数える問題。

いつしかのARCの問題にちょっと似てる。連結成分の大きさとか持っておいてさぼる。Union-findその連結成分の中で一番上にあるやつとかも求められて最強。
複数ケースなのに初期化を定数でやったせいでTLEかなり危なかった(1986ms)。というかなんでこれTLE間に合うんや(5000*252*252*配列6個とかを初期化に使っててどう見ても10^9オーダー)。通ったからいいけど本番でこれやらないようにしないと(危ないのはPCK?)

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define LIMIT 252
typedef pair<int,int>pii;
pii par[LIMIT][LIMIT];
int ran[LIMIT][LIMIT];
int ren[LIMIT][LIMIT];
pii upm[LIMIT][LIMIT];
void init()
{
	for(int i=0;i<LIMIT;i++)
	{
		for(int j=0;j<LIMIT;j++)
		{
			par[i][j]=make_pair(i,j);
			ran[i][j]=0;
			ren[i][j]=1;
			upm[i][j]=make_pair(i,j);
		}
	}
}
pii find(pii a)
{
	if(par[a.first][a.second]==a)
	{
		return a;
	}
	else
	{
		return par[a.first][a.second]=find(par[a.first][a.second]);
	}
}
void unite(pii a,pii b)
{
	a=find(a);
	b=find(b);
	if(a==b)
	{
		return;
	}
	if(ran[a.first][a.second]>ran[b.first][b.second])
	{
		par[b.first][b.second]=a;
		ren[a.first][a.second]+=ren[b.first][b.second];
		upm[a.first][a.second]=min(upm[a.first][a.second],upm[b.first][b.second]);
	}
	else
	{
		par[a.first][a.second]=b;
		ren[b.first][b.second]+=ren[a.first][a.second];
		upm[b.first][b.second]=min(upm[a.first][a.second],upm[b.first][b.second]);
	}
	if(ran[a.first][a.second]==ran[b.first][b.second])
	{
		ran[b.first][b.second]++;
	}
}
int map[252][252];
bool ismin[252][252];
int main()
{
	int data;
	scanf("%d",&data);
	for(int p=0;p<data;p++)
	{
		init();
		int mx,my;
		scanf("%d%d",&mx,&my);
		for(int i=0;i<252;i++)
		{
			for(int j=0;j<252;j++)
			{
				map[i][j]=0;
				ismin[i][j]=false;
			}
		}
		for(int i=0;i<mx;i++)
		{
			for(int j=0;j<my;j++)
			{
				char zan;
				scanf(" %c",&zan);
				if(zan=='1')
				{
					if(map[i][j]==1)
					{
						unite(make_pair(i,j),make_pair(i+1,j+1));
					}
					if(map[i][j+1]==1)
					{
						unite(make_pair(i,j+1),make_pair(i+1,j+1));
					}
					if(map[i][j+2]==1)
					{
						unite(make_pair(i,j+2),make_pair(i+1,j+1));
					}
					if(map[i+1][j]==1)
					{
						unite(make_pair(i+1,j),make_pair(i+1,j+1));
					}
					map[i+1][j+1]=1;
				}
			}
		}
		int ret=0;
		for(int i=1;i<=mx;i++)
		{
			for(int j=1;j<=my;j++)
			{
				if(find(make_pair(i,j))==make_pair(i,j))
				{
					ismin[upm[i][j].first][upm[i][j].second]=true;
				}
			}
		}
		for(int i=1;i<=mx;i++)
		{
			for(int j=1;j<=my;j++)
			{
				if(ismin[i][j]&&ren[find(make_pair(i,j)).first][find(make_pair(i,j)).second]%4==0)
				{
					int hen=ren[find(make_pair(i,j)).first][find(make_pair(i,j)).second]/4+1;
					if(i+hen-1+hen-1<=mx&&j+hen-1<=my&&j-hen+1>=1)
					{
						bool han=true;
						for(int k=0;k<hen;k++)
						{
							if(map[i+k][j-k]==0||map[i+k][j+k]==0||map[i+hen-1+k][j-hen+1+k]==0||map[i+hen-1+k][j+hen-1-k]==0)
							{
								han=false;
								break;
							}
						}
						if(han)
						{
							ret++;
						}
					}
					if(i+hen-1<=mx&&j+hen-1<=my)
					{
						bool han=true;
						for(int k=0;k<hen;k++)
						{
							if(map[i+k][j]==0||map[i][j+k]==0||map[i+hen-1][j+k]==0||map[i+k][j+hen-1]==0)
							{
								han=false;
								break;
							}
						}
						if(han)
						{
							ret++;
						}
					}
				}
			}
		}
		printf("%d\n",ret);
	}
}

ほかにもたくさん解いたけど特に話すべきことがないのでここにはのせません。