2100～2110 - c21coterie @ ウィキ

---

2100　Saizo

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2100
アスレチックのデータから最大の段差を答える問題。

解法
計算して最大値と最小値を更新するだけです。

#include<stdio.h>
void setData(){
int n,t1,t2,t3,max=0,min=0;
scanf("%d %d",&n,&t1);
n--;
while(n--){
	scanf("%d",&t2);
	t3=t2-t1;
	if(max<t3)max=t3;
	if(min>t3)min=t3;
	t1=t2;
}
printf("%d %d\n",max,-min);
}
int main(){
int t;
scanf("%d",&t);
while(t--)setData();
}

2101 Perfect Number

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2101
数字が与えられるので完全数か不足数か過剰数か答える問題。

#include<stdio.h>
int main(){
int n;
while(1){
	scanf("%d",&n);
	if(n==0)break;
	int i,sum=n!=1?1:0;
	for(i=2;i*i<n;i++){
		if(n%i==0){
			sum+=i+n/i;
		}
		if(sum>n)break;
	}
	if(i*i==n)sum+=i;
	printf("%s\n",sum<n?"deficient number":sum==n?"perfect number":"abundant number");
}
}

2102 Rummy

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2102
カードゲームの役を判定する問題。
解法
カードの枚数も少なくルールも非常にシンプルなので素直に実装します。
カードを色と数字でクロス集計して後は深さ優先探索で全探索するだけです。

#include<stdio.h>
#include<map>
#include<string.h>
int nums[9];
int cardMap[3][10];
std::map<char,int> rgbToNo;
bool setOK;
void saiki(int deep){
if(deep==3){
	setOK=true;
	return ;
}
for(int i=0;i<3;i++){
	for(int j=1;j<10;j++){
		if(j<8 && cardMap[i][j]>0&&cardMap[i][j+1]>0&&cardMap[i][j+2]>0){
			cardMap[i][j]--;
			cardMap[i][j+1]--;
			cardMap[i][j+2]--;
			saiki(deep+1);
			if(setOK==true)return;
			cardMap[i][j]++;
			cardMap[i][j+1]++;
			cardMap[i][j+2]++;
		}
		if(cardMap[i][j]>2){
			cardMap[i][j]-=3;
			saiki(deep+1);
			if(setOK==true)return;
			cardMap[i][j]+=3;
		}
	}
}
}
void setData(){
char c;
memset(cardMap,0,3*10*4);
setOK=false;
for(int i=0;i<9;i++){
	scanf("%d",&nums[i]);
}
for(int i=0;i<9;i++){
	scanf(" %c",&c);
	cardMap[rgbToNo[c]][nums[i]]++;
}
saiki(0);
printf("%d\n",setOK?1:0);
}
int main(){
rgbToNo['R']=0;
rgbToNo['G']=1;
rgbToNo['B']=2;
int n;
scanf("%d",&n);
while(n--)setData();
}

---

2104　Country Road

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2104
発電機の数と電線が与えられるので全ての家に電気を供給する問題。
家は一本の道沿いに並んでおり電線は道沿いに敷設することとし、電線の長さが最小になるように敷設するという問題です。

解法
全部の家を電線でつなげた状態から分断していくという視点で見ればこの問題は非常に簡単になります。
一番長い電線を発電機の数-1か所切断すれば答えが出てきます。

#include<stdio.h>
#include <algorithm>
#include <functional>
int house[100001];
void setData(){
int h,k,sum=0,t1,t2;
scanf("%d %d %d",&h,&k,&t1);
for(int i=1;i<h;i++){
	scanf("%d",&t2);
	house[i-1]=t2-t1;
	sum+=t2-t1;
	t1=t2;
}	
if(k>=h){
	printf("0\n");
}else{
	std::sort(house,house+h-1,std::greater<int>());
	for(int i=0;i<k-1;i++){
		sum-=house[i];
	}
	printf("%d\n",sum);
}
}
int main(){
int n;
scanf("%d",&n);
while(n--)setData();
}

2106　Enegy Transporter

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2106
エネルギー励起して左から右へエネルギーを渡していく鎖の部品を的確に励起させて一番左のパーツに最大のエネルギーを集める問題。

左端から順に動的計画法を試していくだけです。
左端２マスを見た時、一番エネルギーの高い状態に着目すればそんなに難しくありません。
iがループすると着目している左端２マスを一ます右にずらします。
memoは配列のキーが次のループではエネルギーの値に、エネルギーの値がキーに変わることに注目すれば簡単です。

#include<stdio.h>
#include<string.h>
#include<algorithm>
void setData(){
int L,e1,e2,es[81];
es[1]=0;//データが一個しかないときのための対策用ダミーデータ
scanf("%d",&L);
for(int i=0;i<L;i++)scanf("%d",&es[i]);
int ans=es[L-1];
int memo[2][321];
memset(memo,-1,sizeof(memo));
for(int i=1;i<L-1;i++){
	int now =(i+1)&1;
	int next=i&1;
	int t;
	memset(memo[next],-1,sizeof(memo[next]));
	memo[now][es[i-1]]=std::max(es[i],memo[now][es[i-1]]);
	for(int j=0;j<321;j++){
		t=memo[now][j];
		if(t>=0){
			if(t>0)memo[next][t-1]=std::max(j+es[i+1],memo[next][t-1]);
			memo[next][t]=std::max(memo[next][t],es[i+1]);
		}
	}
}
for(int j=0;j<321;j++){
	ans=std::max(ans,memo[(L-2)&1][j]);
}
printf("%d\n",ans);
}
int main(){
int n;
scanf("%d",&n);
while(n--)setData();
}