AOJ571～580 - c21coterie @ ウィキ

堀江伸一

0575　Festivals in JOI Kingdom

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0575
今のところ考えてる解法。
まず祭りの行われている街を距離0の架空の都市で結び、この架空の都市からの全ての都市への最短距離を計算する。
次にクエリの都市s,tとt,sで構造体の形で全部保管する。
次に全ての都市の道路を一度切断。
祭りから遠い都市から順番に選びユニオン木の根としどんどんユニオン木を拡張していく。
大きな値から接続しているからユニオン木の中身は今選択中の都市より必ず祭りから遠い、よって同じユニオン木の中ではどの都市と接続してもよい？。
すると結果は多分木になるはずである。
この木を全探索しながら、クエリを的確に処理していく方法らしきものをぼんやりと思いついている段階なのだけど。
うーん、詳細を詰めるのが難しいし、実装がかなり面倒。
狭い机の上でトランプタワーを３つ立てるようなめんどくささがある。

例えば適当な木を考えてみる。

黒字が祭りからの距離で、赤字が番号。
木の8番までを探索した場合、8番の向こう側と8番側にある点の関係は？
番号1は番号２に制限されるし、番号4,5,6は番号7で値が低くなる。
番号0は7の影響を受ける？
この制限の関係を木を探索しながら適切に記述するにはどうすれば良いか？
とてもフラクタルな構造をした問題に見えるので、処理手順はかなり再帰的になるはず？

実装がめんどくさそうなので少し楽する方法を考えてみる。
速度よりとりあえず正答することを考えてみる。
色々考えた結果次のような図を考えた。

木を探索する過程で点を訪れる順番である。
この順番で点の祭りまでの距離と点の都市番号のセットをリニアに並べてみる。
この直列になおしたデータを分析したほうが楽そうにみえる？

571　JJOOII

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0571
百万文字の文字列を読み込んで文字列の中から　Jがn個Oがn個Iがｎ個と連続して並んでいるという条件を満たす部分のうち最大長の文字列を探してその長さを返す問題。
各ＪOIの連続出現回数をjoiCountsに保存して後は一文字ずつ読み込みながらmodeを変化させていく状態遷移マシンで実装。
手前から読んでJJJ,,,OOO,,,III,,が条件を満たすなら数えるのを継続し満たさないならＪがでるまで数えるのをやめるだけである。

競技プログラムの問題は2種類に分けられる。
手前からリニアにデータを読んで一つのデータにつき一回の処理で終わりリニアに解を決定できる問題となんども複数のデータを照合して突き合わせないと終わらない問題に大別できる。
リニアな問題は簡単なのが多いけどこの問題は典型的なリニアな問題だった。

これ25分くらいで実装できたけど世間様だったらもっと早く実装するのかな。
俺４流プログラマだしよくわかんね。

#include<stdio.h>
int main(){
int joiCounts[3],mode=0,ans=0;
int c;	
while(c=getchar()){
	if(c==-1||c=='\n')break;
	if(mode==0){
		if(c=='J'){
			joiCounts[0]=1;
			mode=1;
		}
	}else if(mode==1){
		if(c=='J'){
			joiCounts[0]++;
		}else if(c=='O'){
			joiCounts[1]=1;
			mode=2;
		}else if(c=='I'){
			mode=0;
			joiCounts[0]=0;
		}
	}else if(mode==2){
		if(c=='O'){
			joiCounts[1]++;
			if(joiCounts[1]>joiCounts[0]){
				mode=0;
			}
		}else if(c=='J'){
			mode=1;
			joiCounts[0]=1;
		}else if(c=='I'){
			joiCounts[2]=1;
			mode=3;
			if(joiCounts[1]==1)ans=ans>1?ans:1;
		}
	}else if(mode==3){
		if(c=='I'){
			joiCounts[2]++;
			if(joiCounts[2]==joiCounts[1]){
				ans=ans>joiCounts[2]?ans:joiCounts[2];
			}else if(joiCounts[2]>joiCounts[1]){
				mode=0;
			}
		}else if(c=='J'){
			mode=1;
			joiCounts[0]=1;
		}else if(c=='O'){
			mode=0;
		}
	}
}
printf("%d\n",ans);
}

572　Card Game is Fun

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0572
単調増加数列の概念を応用して解く。
自由にカードを抜けるＡさんのカードをＢさんのカードと照合しながら動的計画法で解けばよい。
特に賢く解く部分もないが油断して2回も不合格を食らった問題。
私の場合油断してというパタンが多い。

#include<stdio.h>
#include<string.h>
#include <algorithm>
int main(){
int cardsA[5001],cardsB[5001];
int a,b;
int memo[5001];
memset(memo,0,sizeof(memo));
scanf("%d %d",&a,&b);
for(int i=0;i<a;i++){
	scanf("%d",&cardsA[i]);
}
for(int i=0;i<b;i++){
	scanf("%d",&cardsB[i]);
}
for(int i=0;i<a;i++){
	for(int j=b-1;j>0;j--){
		if(cardsA[i]==cardsB[j]){
			memo[j]=std::max(memo[j-1]+1,memo[j]);
		}
	}
	for(int j=0;j<b;j++){
		if(cardsA[i]==cardsB[j]){
			memo[j]=std::max(1,memo[j]);
		}
	}
}
int ans=0;
for(int i=0;i<b;i++)ans=std::max(ans,memo[i]);
printf("%d\n",ans);
}

0573　Night Market

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0573
aとｂの書き間違いに気づかず不正回を2連続で食らった問題。
問題自体は制限付きの動的計画法で楽々である。
条件の説明がめんどくさい数式で書かれていて読みづらいので入力の解説だけを読んだ方がいい問題。

#include<stdio.h>
#include<string.h>
#include <algorithm>
int main(){
int n,t,s,a,b;
int memo[3001],ans=0;
memset(memo,0,sizeof(memo));
scanf("%d %d %d",&n,&t,&s);
for(int i=0;i<n;i++){
	scanf("%d %d",&a,&b);
	for(int j=t;j>=0;j--){
		int L=j+b;
		if(j<s  && s<L) continue;
		if(L>t)continue;
		memo[L]=std::max(memo[L],memo[j]+a);
		ans=std::max(ans,memo[L]);
	}
}
printf("%d\n",ans);
}

0574

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0574
釘の打ちつけられた板に輪ゴムが張られているので何個の釘が輪ゴムに囲まれているかを答える問題。
２列ずつにわけての動的計画法でアセプト。
実装をシンプルにした分速度は出てない。

#include<stdio.h>
#include<map>
#include<algorithm>
#include<string.h>
struct P{
int a,b;
bool operator<(const P& p)const{
	if(b!=p.b)return b<p.b;//より左側にあり
	return a<p.a;//より上にあり
}
bool operator==(const P& p)const{
	return a==p.a&&b==p.b;
}
};
int memo[2][5004];
std::map<P,int> points;
std::map<P,int>::iterator it;
int main(){
int n,m,x;
scanf("%d %d",&n,&m);
P p;

for(int i=0;i<m;i++){
	scanf("%d %d %d",&p.a,&p.b,&x);
	if(points.find(p)==points.end()||points[p]<x+1){
		points[p]=x+1;
	}
}
memset(memo,0,sizeof(memo));
int c,ans=0;
it=points.begin();
for(int i=1;i<=n;i++){
	int now=(i+1)&1;
	int old=i&1;
	p.b=i;
	memo[now][i-1]=0;
	for(int j=i;j<=n;j++){
		//0段目としてダミーデータ0を入れてある
		p.a=j;
		if(it!=points.end()&&(*it).first==p){
			c=(*it).second;
			it++;
		}else{
			c=0;
		}
		memo[now][j]=std::max(std::max(c,memo[old][j-1]-1),memo[now][j-1]-1);//斜め左上か斜め右上からの三角形の連続、もしくはこのマスで始まる新しい三角形のどれかで一番大きいのを選ぶ
		if(memo[now][j]!=0)ans++;
	}
}
printf("%d\n",ans);
}

576　Homework

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0576
宿題の日数を計算する問題。

解法
一番簡単な部類の問題なので何も考えません。

#include<stdio.h>
#include<iostream>
int main(){
	int L,a,b,c,d;
	std::cin>>L>>a>>b>>c>>d;
	a--;
	b--;
	std::cout<<(L-1-(a/c>b/d?a/c:b/d))<<"\n";
}

577　Unique number

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0577
簡単なゲームのスコアを求める問題。

解法
簡単な問題なので何も考えません。

#include<stdio.h>
#include<string.h>
int main(){
	int n;
	int scores[201][3];
	int memo[3][101];
	memset(memo,0,sizeof(memo));
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		for(int j=0;j<3;j++){
			scanf("%d",&scores[i][j]);
			memo[j][scores[i][j]]++;
		}
	}
	for(int i=0;i<n;i++){
		int ans=0;
		for(int j=0;j<3;j++){
			if(memo[j][scores[i][j]]==1)ans+=scores[i][j];
		}
		printf("%d\n",ans);
	}
}

0578　Signboard

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0578
看板の文字を上塗りして看板を再利用する問題。

解法
何も思いつかなかったので全探索しました。
賢い方法というのもあるかもしれません。
等間隔というのが結構難題です。

#include<stdio.h>
#include<string.h>
int main(){
	int n,baseLen,ans=0;
	char name[30],old[110];
	scanf("%d %s",&n,name);
	baseLen=strlen(name);
	for(int i=0;i<n;i++){
		scanf("%s",old);
 		int len=strlen(old);
		int add=0;
		for(int j=0;old[j]!='\0';j++){
			if(add==1)break;
			for(int k=1;k<len;k++){
				int count=0;
				for(int L=0;L*k+j<len;L++){
					int p=L*k+j;
					if(name[count]!=old[p])break;
					count++;
					if(count>=baseLen)break;
				}
				if(count==baseLen)add=1;
			}
		}
		ans+=add;
	}
	printf("%d\n",ans);
}

0579 Hot days

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0579
毎日の服を選ぶ問題。

解法
条件を満たす服だけで動的計画法を適用すれば解けます。

#include<stdio.h>
#include<string.h>

int main(){
	int d,n,ts[201],as[201],bs[201],cs[201];
	int memo[201][201];
	scanf("%d %d",&d,&n);
	for(int i=0;i<d;i++){
		scanf("%d",&ts[i]);
	}
	memset(memo,-1,sizeof(memo));
	int t=ts[0];
	for(int i=0;i<n;i++){
		scanf("%d %d %d",&as[i],&bs[i],&cs[i]);
		if(as[i]<=t&&t<=bs[i]){
			memo[0][i]=0;
		}
	}
 	int ans=0;
	for(int i=1;i<d;i++){
		int t=ts[i];
		for(int j=0;j<n;j++){
			//今日の服j
			if(t<as[j]||bs[j]<t)continue;
			int c1=cs[j];
			for(int k=0;k<n;k++){
				//前日の服k
				int base=memo[i-1][k];
				if(base==-1)continue;
				int c2=cs[k];
				int c3=base+(c2>c1?c2-c1:c1-c2);
				if(memo[i][j]<c3)memo[i][j]=c3;
				if(ans<c3)ans=c3;
			}
		}
	}
	printf("%d\n",ans);
}

0580　Fish

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0580
魚の生息区域の重なりの体積を調べる問題。

解法
浅い層から水平に区切ってその範囲内で順番に計算していきます。
3次元なので結構苦労しました。
この問題ｎ次元になったらどう解けばよいのか？
けっこう悩みます。

#include<stdio.h>
#include<map>
#include<set>
#include<iostream>
struct QP{
 	long long int x,y,z,no,add;
	bool operator<(const QP& s)const{
		if(z!=s.z)return z<s.z;
		if(x!=s.x)return x<s.x;
		if(y!=s.y)return y<s.y;
		if(add!=s.add)return add<s.add;
		return no<s.no;
	}
	void set(long long int x1,long long int y1,long long int z1,int a){
		x=x1;
		y=y1;
		z=z1;
		add=a;
	}
};
struct FP{
	long long int x,y;
	int add;
	bool operator<(const FP& fp)const{
		if(x!=fp.x)return x<fp.x;
		if(y!=fp.y)return  y<fp.y;
		return add<fp.add;
	}
};

int main(){
	int n,k;
	long long int ans=0;
	scanf("%d %d",&n,&k);
	std::map<FP,int> memo;
	std::map<FP,int>::iterator mIt;
	std::set<QP> allPs;
	std::set<QP>::iterator it;
	
	QP qp;
	FP fp;
	long long int x1,y1,z1,x2,y2,z2;
	for(int i=0;i<n;i++){
		//qp.set(x,y,z,isIn,isDell)
		std::cin>>x1>>y1>>z1>>x2>>y2>>z2;
		qp.no=i;
		
		//上面
		qp.set(x1,y1,z1,1);
		allPs.insert(qp);
 		
		qp.set(x2,y1,z1,-1);
		allPs.insert(qp);
		
		qp.set(x1,y2,z1,-1);
		allPs.insert(qp);
		
		qp.set(x2,y2,z1,1);
		allPs.insert(qp);
		
		
		//下面
		qp.set(x1,y1,z2,-1);
		allPs.insert(qp);
		
		qp.set(x2,y1,z2,1);
		allPs.insert(qp);
		
		qp.set(x1,y2,z2,1);
		allPs.insert(qp);
		
		qp.set(x2,y2,z2,-1);
		allPs.insert(qp);
	}
	long long int oldZ=(*allPs.begin()).z ,S=0;
	it=allPs.begin();
	
	while(it!=allPs.end()){
		qp=(*it);
		if(qp.z==oldZ){
			fp.x=qp.x;
			fp.y=qp.y;
			fp.add=qp.add;
			long long int add=qp.add;
			if(memo.find(fp)==memo.end())memo[fp]=0;
			memo[fp]+=add;
			it++;
		}else
		{
			mIt=memo.begin();
			long long int oldX=(*mIt).first.x,lenY=0;
			std::map<long long int,int> lineMemo;
			std::map<long long int,int>::iterator lIt;
			while(mIt!=memo.end()){
				fp=(*mIt).first;
				int add=(*mIt).second;
				if(fp.x==oldX){
					if(lineMemo.find(fp.y)==lineMemo.end())lineMemo[fp.y]=0;
					lineMemo[fp.y]+=add;
					mIt++;
				}else{
					long long int oldY=(*lineMemo.begin()).first;
					int inOut=0;
					for(lIt=lineMemo.begin();lIt!=lineMemo.end();lIt++){
						if(k<=inOut){
							lenY+=((*lIt).first-oldY);
						}
						oldY=(*lIt).first;
						inOut+=(*lIt).second;
					}
					S+=lenY*(fp.x-oldX);
					oldX=fp.x;
					lenY=0;
				}
			}
			ans+=S*(qp.z-oldZ);
			oldZ=qp.z;
			S=0;
		}
	}
	std::cout<<ans<<"\n";
}