「AOJ500~510」の編集履歴(バックアップ)一覧はこちら
「AOJ500~510」(2011/10/24 (月) 16:28:42) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*0500 Card Game
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0500
カードゲームの合計点を求める問題。
順に2人が1枚つずつカードを出し大きな値のカードを出した方がカードの得点を得ます。
解法
指定されたとおりに書くだけです。
#include<stdio.h>
int main(){
int n,p1,p2,c1,c2;
while(scanf("%d",&n),n>0){
p1=p2=0;
while(n--){
scanf("%d %d",&c1,&c2);
if(c1==c2){
p1+=c1;
p2+=c2;
}else if(c1>c2){
p1+=c1+c2;
}else{
p2+=c1+c2;
}
}
printf("%d %d\n",p1,p2);
}
}
----
*0501 Data Conversion
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0501
入力された文字を変換表に従って変換して出力する問題です。
解法
定義通りに変換表mapを作ってそれと照合するだけで済みます。
#include<stdio.h>
#include<string.h>
int main(){
int n,m;
char map[255],c1,c2;
while(scanf("%d",&n),n>0){
memset(map,-1,255);
while(n--){
scanf(" %c %c",&c1,&c2);
map[c1]=c2;
}
scanf("%d",&m);
while(m--){
scanf(" %c",&c1);
printf("%c",map[c1]==-1?c1:map[c1]);
}
printf("\n");
}
}
----
*0502 Dice
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0502
さいころを転がして、転がすたびに上面にある数字を足していき合計がいくつにか答える問題。
解法
サイの目を配列で表し、回転に対応した関数を定義してシミュレートするだけです。
回転操作をマトリックス化する事でコードを簡素にしています。
#include <iostream>
#include <string>
using namespace std;
int solve(int);
void round(int,int,int,int,int *);
int main(void)
{
int n;
int sum;
std::cin>>n;
while(n!=0)
{
sum=solve(n);
std::cout<<sum<<"\n";
std::cin>>n;
}
}
int solve(int n){
int dice[6]={1,5,4,2,3,6};
int sum=1;
string command;
for(int i=0;i<n;i++)
{
std::cin>>command;
if(command=="North"){
round(0,3,5,1,dice);
}
if(command=="East"){
round(2,5,4,0,dice);
}
if(command=="South"){
round(1,5,3,0,dice);
}
if(command=="West"){
round(4,5,2,0,dice);
}
if(command=="Right"){
round(4,1,2,3,dice);
}
if(command=="Left"){
round(2,1,4,3,dice);
}
sum+=dice[0];
}
return sum;
}
void round(int a,int b,int c,int d,int *dice){
int t=dice[a];
dice[a]=dice[b];
dice[b]=dice[c];
dice[c]=dice[d];
dice[d]=t;
}
----
*0503 Cup
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0503
ハノイの塔の制限版。
何手で両端のトレイにカップをそろえられるかを求める問題。
解法
とりあえず、一番素朴な実装でといてみました。
漸化式や集合を使った解法もあるようなので後日そちらのパタンのコードも掲載する予定です。
#include<stdio.h>
#include<queue>
#include<stdlib.h>
int n,m;
struct state{
int cups[3];
int turn;
int oldMove1,oldMove2;
};
bool cupMove(int& a,int& b){
if(a==0) return false;
int t=-1;
for(int i=n-1;i>=0;i--){
t=(1<<i);
if((a&t)!=0){
break;
}
if((b&t)!=0){
return false;
}
}
if(t==-1)return false;
b|=t;
a&=(~t);
return true;
}
void setData(){
state s;
s.turn=0;
s.oldMove1=s.oldMove2=-1;
int count,t1,ans=(1<<n)-1,tt;
for(int i=0;i<3;i++){
scanf("%d",&count);
s.cups[i]=0;
for(int j=0;j<count;j++){
scanf("%d",&t1);
s.cups[i]|=(1<<(t1-1));
}
}
std::queue<state> memo;
memo.push(s);
while(s.turn<=m){
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(abs(i-j)!=1)continue;
s=memo.front();
if(s.cups[0]==ans || s.cups[2]==ans){
printf("%d\n",s.turn);
return;
}
s.turn++;
if(s.oldMove1==j && s.oldMove2==i)continue;
if(cupMove(s.cups[i],s.cups[j])){
s.oldMove1=i;
s.oldMove2=j;
memo.push(s);
}
}
}
memo.pop();
}
printf("-1\n");
}
int main(){
while(1){
scanf("%d %d",&n,&m);
if(n+m==0)break;
setData();
}
}
----
*0505 Questionnaire
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0505
旅行先の候補地を決める問題。
アンケート結果の集計データから、人気の高い候補地順に出力する。
解法
集計するだけです。
#include<stdio.h>
#include<string.h>
#include <algorithm>
struct total{
int no,sum;
bool operator<(const total t)const{
if(sum!=t.sum) return sum>t.sum;
return no<t.no;
}
};
int main(){
int n,m,t;
while(scanf("%d %d",&n,&m),n+m>0){
total sums[1001];
for(int i=0;i<m;i++){
sums[i].no=i+1;
sums[i].sum=0;
}
while(n--){
for(int i=0;i<m;i++){
scanf("%d",&t);
sums[i].sum+=t;
}
}
std::sort(sums,sums+m);
for(int i=0;i<m;i++)printf("%s%d",i==0?"":" ",sums[i]);
printf("\n");
}
}
----
*0506 String
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0506
文字列を決まった規則で変換し続けた時最終的にどのような文字列になるかを答える問題。
解法
文字列も短く変換するパイプに文字列を繰り返しとおすだけです。
速度より分かりやすさを重視して実装しました。
#include<iostream>
#include<string>
#include<stdio.h>
std::string change(std::string& text){
std::string ans="";
int size=text.size(),c=0;
char t[2],num[10];
t[0]=text[0];
t[1]='\0';
text.append("\0");
for(int i=0;i<=size;i++){
if(t[0]==text[i]){
c++;
}else{
sprintf(num,"%d",c);
ans.append(num);
ans.append(t);
c=1;
t[0]=text[i];
}
}
return ans;
}
int main(){
std::string text;
int n;
while(1){
std::cin>>n;
if(n==0) break;
std::cin>>text;
for(int i=0;i<n;i++){
text=change(text);
}
std::cout<<text<<"\n";
}
}
----
*0507 Square
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0507
解法
ひとつ左よりも小さいか同じ値にそろえて再帰するだけです。
#include<stdio.h>
#include<vector>
int memo[31];
void saiki(int deep,int n,int size){
if(n==0){
printf("%d",memo[0]);
for(int i=1;i<deep;i++){
printf(" %d",memo[i]);
}
printf("\n");
}
if(size>n) size=n;
for(int i=size;i>=1;i--){
memo[deep]=i;
saiki(deep+1,n-i,i);
}
}
int main(){
int n;
while(scanf("%d",&n),n>0){
saiki(0,n,n);
}
}
----
*0508 String With Rings
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0508
与えられたグラフの中で同じ点を1度しか通らずに出来るだけ多くの点を移動するとき何個の点を移動できるか求める問題。
解法
グラフの問題なのでグラフとして解きます。
単純にグラフを探索する深さ優先探索で解きます。
原理は分かりませんがリングが複数のリングR1,R2,,,Rnに分かれているとき、スタート地点となる点は必ずRiの中でもっとも辺の少ない点になるそうです。
これを求めるために、setData関数の中では最初にリングがいくつに分かれているかとRiの最小ノード数を求めておきます。
後は深さ優先探索で解くだけです。
#include <stdio.h>
int gPointCount[101];
void nodeSearch(int rings[101][101],int nodeSize[101],int gTypes[101],int no,int gType){
int size=nodeSize[no];
gTypes[no]=gType;
gPointCount[gType]++;
for(int i=0;i<size;i++){
if(gTypes[rings[no][i]]==-1){
nodeSearch(rings,nodeSize,gTypes,rings[no][i],gType);
}
}
}
int ringLen(int rings[101][101],int nodeSize[101],bool moveOK[101],int no,int deep){
moveOK[no]=false;
int max=-1,t;
for(int i=0;i<nodeSize[no];i++){
if(moveOK[rings[no][i]]==true){
t=ringLen(rings,nodeSize,moveOK,rings[no][i],deep+1);
max=max>t?max:t;
}
}
moveOK[no]=true;
if(max==-1) return deep;
return max;
}
void setData(int n){
int rings[101][101];
int nodeSize[101];
int gTypes[101],gNodeMins[101],gTypeCount=0;
bool moveOK[101];
int a,b;
for(int i=0;i<101;i++){
nodeSize[i]=0;
gTypes[i]=-1;
gNodeMins[i]=101;
moveOK[i]=true;
}
for(int i=0;i<n;i++){
scanf("%d %d",&a,&b);
a--;
b--;
rings[a][nodeSize[a]]=b;
rings[b][nodeSize[b]]=a;
nodeSize[a]++;
nodeSize[b]++;
}
for(int i=0;i<101;i++){
if(gTypes[i]==-1 && nodeSize[i]>0){
gPointCount[gTypeCount]=0;
nodeSearch(rings,nodeSize,gTypes,i,gTypeCount);
gTypeCount++;
}
}
for(int i=0;i<101;i++){
if(nodeSize[i]>0) gNodeMins[gTypes[i]]=gNodeMins[gTypes[i]]>nodeSize[i]?nodeSize[i]:gNodeMins[gTypes[i]];
}
int t,max=1;
for(int i=0;i<101;i++){
if(nodeSize[i]==0) continue;
if(gNodeMins[gTypes[i]]==nodeSize[i] && max<gPointCount[gTypes[i]]){
t=ringLen(rings,nodeSize,moveOK,i,1);
max=t>max?t:max;
}
}
printf("%d\n",max);
}
int main(){
int n;
scanf("%d",&n);
while(n!=0){
setData(n);
scanf("%d",&n);
}
}
----
*0509sheets
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0509
1万枚のシートを平面に広げたとき、全シートの周長と面積を出すという問題です。
解法
シートの重なりを考慮に入れないといけないためかなりの難問です。
解き方を思いつきません。
公開されているジャッジデータをそこそこの速度で解くことまで出来ましたが、まだまだ速度が遅いのでタイムリミッドを食らってしまいます。
問題の考え方まで読んで実装してみたのですが、速度を上げる実装を思いつきませんでした。
難しいです。
#include<stdio.h>
#include<map>
#include<vector>
struct col{
int y1,y2;
};
void calcR(int& ansR,int& ansS,std::vector<col>& tate,std::map<int,int>& sheetIO) {
col t;
std::map<int,int>::iterator it;
tate.clear();
it=sheetIO.begin();
t.y1=(*it).first;
int inOutCount=0;
while(it!=sheetIO.end()){
inOutCount+=(*it).second;
if(inOutCount==0){
t.y2=(*it).first;
ansR+=(t.y2-t.y1)*2+2;//楯列に短冊に切ったシートの上下左右の周長
ansS+=t.y2-t.y1;
tate.push_back(t);
it++;
if(it==sheetIO.end())break;
t.y1=(*it).first;
}else{
it++;
}
}
}
void setMap(int n,int type){
std::map<int,int> sheetIO[10002];//シートにinOut[x座標]する。Y座標は0から増えていく
std::map<int,int> tempIO;
int ioCount;
int x1,y1,x2,y2,x,y;
int maxX=0,minX=10001;
std::map<int,int>::iterator it;
for(int i=0;i<n;i++){
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
x1++;//0列目はダミーとして使うので一列シートをずらす
x2++;
if(x1<minX)minX=x1;
if(x2>maxX)maxX=x2;
for(int x=x1;x<x2;x++){
if(sheetIO[x].find(y1)==sheetIO[x].end()){
sheetIO[x][y1]=1;
}else{
sheetIO[x][y1]++;
}
if(sheetIO[x].find(y2)==sheetIO[x].end()){
sheetIO[x][y2]=-1;
}else{
sheetIO[x][y2]--;
}
}
if(i>0 && i%50==0){
for(int x=minX;x<=maxX;x++){
it=sheetIO[x].begin();
if(it==sheetIO[x].end())continue;
ioCount=0;
tempIO.clear();
tempIO[(*it).first]=1;
while(it!=sheetIO[x].end()){
ioCount+=(*it).second;
if(ioCount==0){
tempIO[(*it).first]=-1;
it++;
if(it==sheetIO[x].end())break;
tempIO[(*it).first]=1;
}else{
it++;
}
}
sheetIO[x].clear();
sheetIO[x].insert(tempIO.begin(),tempIO.end());
}
}
}
int ansR=0,ansS=0,old,now,p1,p2;//周長
std::vector<col> tate[2];
int yOld1,yOld2,yNow1,yNow2;
for(int x=minX;x<=maxX;x++){
calcR(ansR,ansS,tate[x%2],sheetIO[x]);
old=(x+1)%2;
now=x%2;
p1=p2=0;
while(p2<tate[now].size() && p1<tate[old].size()){
yOld1=tate[old][p1].y1;
yOld2=tate[old][p1].y2;
yNow1=tate[now][p2].y1;
yNow2=tate[now][p2].y2;
if(yOld1>=yNow2){
p2++;
}else if(yOld2<=yNow1){
p1++;
}else if(yOld2>=yNow2 && yOld1>=yNow1 && yOld1<=yNow2){
ansR-=2*(yNow2-yOld1);
p2++;
}else if(yOld2>=yNow2 && yOld1<=yNow1){
ansR-=2*(yNow2-yNow1);
p2++;
}else if(yOld2<=yNow2 && yOld1<=yNow1 && yOld2>=yNow1){
ansR-=2*(yOld2-yNow1);
p1++;
}else if(yOld2<=yNow2 && yOld1>=yNow1){
ansR-=2*(yOld2-yOld1);
p1++;
}
}
}
if(type==2){
printf("%d\n%d\n",ansS,ansR);
}else{
printf("%d\n",ansS);
}
}
int main()
{
int n,type;
scanf("%d %d",&n,&type);
while(n!=0 || type!=0){
setMap(n,type);
scanf("%d %d",&n,&type);
}
}
----
上記コードをBit演算で高速化できないか試してみたバージョンです。
結局速度はでずコード実行速度が遅すぎで不正解となるコードです。
下記コードはシートの数が1万枚でも10枚でもほぼ同じ数秒で答えが出正しい答えを返します。
計算量が安定しているという利点はあります。
このコード最初はうまくいきませんでした。
BitSetは何Bitでメモリ確保しようとも実際には32Bitの倍数でBitが確保されます。
なので19Bit確保すると残り13Bitには1が確保されたままになります。
このためBitSetのCount関数を使うと19Bitの中の1Bitの数と13Bitに設定された1の合計がかえってきます。
これを知らなかったため最初コードがうまくいきませんでした。
YAHOO知恵袋でそのことを教えてもらいコードがうまくいきました。
#include<stdio.h>
#include <bitset>
#include <iostream>
const int size=10016;//縦横のマップサイズとりあえずサンプルデータを試せるサイズに限定
std::bitset<size> map[size],temp,temp2,temp3;//平面をmap[y]の短冊切りにする、シートのある地点を1Bit
void setMap(int n,int type){
int x1,y1,x2,y2,ansS=0,ansR=0;
for(int i=0;i<size;i++)map[i].reset();
for(int i=0;i<n;i++){
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
y1++;
y2++;
x1++;
x2++;
temp.reset();
temp.flip();
temp>>=(size-x2+x1);
temp<<=(x1);
for(int y=y1;y<y2;y++){
map[y]|=temp;
}
}
int t;
for(int i=1;i<size;i++){
temp=map[i];
//std::cout<<temp<<" "<<temp.count();//<<"\n";計算に使うマップの表示、シートがある部分が1無い部分が0最後尾にCount関数で求めた行の1の数が出るはずなのですが?
temp2=map[i-1];
t=temp.count();
ansS+=t;
ansR+=2*t;
//上段と下段で切れ端の共通辺を取り除く
temp3=temp&temp2;
ansR-=2*temp3.count();
//切れ端の両端を計算する
temp2=map[i];
temp3=(temp<<1);
temp3^=temp2;
//std::cout<<"("<<temp3.count()<<")\n";
ansR+=temp3.count();//切れ端の片端を計算する
}
if(type==2){
printf("%d\n%d\n",ansS,ansR);
}else{
printf("%d\n",ansS);
}
}
int main()
{
int n,type;
scanf("%d %d",&n,&type);
while(n!=0 || type!=0){
setMap(n,type);
scanf("%d %d",&n,&type);
}
}
----
*0510
2人のテスト点数を比べて合計点が多い方を出力する問題。
解法
私は興味ありませんが、ショートコーディングの一番初めの入門にいい問題かもしれません。
#include<stdio.h>
int main(){
int s[2],c;
s[0]=s[1]=0;
for(int i=0;i<8;i++){
scanf("%d",&c);
s[i/4]+=c;
}
printf("%d\n",s[0]>s[1]?s[0]:s[1]);
}
*0500 Card Game
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0500
カードゲームの合計点を求める問題。
順に2人が1枚つずつカードを出し大きな値のカードを出した方がカードの得点を得ます。
解法
指定されたとおりに書くだけです。
#include<stdio.h>
int main(){
int n,p1,p2,c1,c2;
while(scanf("%d",&n),n>0){
p1=p2=0;
while(n--){
scanf("%d %d",&c1,&c2);
if(c1==c2){
p1+=c1;
p2+=c2;
}else if(c1>c2){
p1+=c1+c2;
}else{
p2+=c1+c2;
}
}
printf("%d %d\n",p1,p2);
}
}
----
*0501 Data Conversion
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0501
入力された文字を変換表に従って変換して出力する問題です。
解法
定義通りに変換表mapを作ってそれと照合するだけで済みます。
#include<stdio.h>
#include<string.h>
int main(){
int n,m;
char map[255],c1,c2;
while(scanf("%d",&n),n>0){
memset(map,-1,255);
while(n--){
scanf(" %c %c",&c1,&c2);
map[c1]=c2;
}
scanf("%d",&m);
while(m--){
scanf(" %c",&c1);
printf("%c",map[c1]==-1?c1:map[c1]);
}
printf("\n");
}
}
----
*0502 Dice
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0502
さいころを転がして、転がすたびに上面にある数字を足していき合計がいくつにか答える問題。
解法
サイの目を配列で表し、回転に対応した関数を定義してシミュレートするだけです。
回転操作をマトリックス化する事でコードを簡素にしています。
#include <iostream>
#include <string>
using namespace std;
int solve(int);
void round(int,int,int,int,int *);
int main(void)
{
int n;
int sum;
std::cin>>n;
while(n!=0)
{
sum=solve(n);
std::cout<<sum<<"\n";
std::cin>>n;
}
}
int solve(int n){
int dice[6]={1,5,4,2,3,6};
int sum=1;
string command;
for(int i=0;i<n;i++)
{
std::cin>>command;
if(command=="North"){
round(0,3,5,1,dice);
}
if(command=="East"){
round(2,5,4,0,dice);
}
if(command=="South"){
round(1,5,3,0,dice);
}
if(command=="West"){
round(4,5,2,0,dice);
}
if(command=="Right"){
round(4,1,2,3,dice);
}
if(command=="Left"){
round(2,1,4,3,dice);
}
sum+=dice[0];
}
return sum;
}
void round(int a,int b,int c,int d,int *dice){
int t=dice[a];
dice[a]=dice[b];
dice[b]=dice[c];
dice[c]=dice[d];
dice[d]=t;
}
----
*0503 Cup
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0503
ハノイの塔の制限版。
何手で両端のトレイにカップをそろえられるかを求める問題。
解法
とりあえず、一番素朴な実装でといてみました。
漸化式や集合を使った解法もあるようなので後日そちらのパタンのコードも掲載する予定です。
#include<stdio.h>
#include<queue>
#include<stdlib.h>
int n,m;
struct state{
int cups[3];
int turn;
int oldMove1,oldMove2;
};
bool cupMove(int& a,int& b){
if(a==0) return false;
int t=-1;
for(int i=n-1;i>=0;i--){
t=(1<<i);
if((a&t)!=0){
break;
}
if((b&t)!=0){
return false;
}
}
if(t==-1)return false;
b|=t;
a&=(~t);
return true;
}
void setData(){
state s;
s.turn=0;
s.oldMove1=s.oldMove2=-1;
int count,t1,ans=(1<<n)-1,tt;
for(int i=0;i<3;i++){
scanf("%d",&count);
s.cups[i]=0;
for(int j=0;j<count;j++){
scanf("%d",&t1);
s.cups[i]|=(1<<(t1-1));
}
}
std::queue<state> memo;
memo.push(s);
while(s.turn<=m){
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(abs(i-j)!=1)continue;
s=memo.front();
if(s.cups[0]==ans || s.cups[2]==ans){
printf("%d\n",s.turn);
return;
}
s.turn++;
if(s.oldMove1==j && s.oldMove2==i)continue;
if(cupMove(s.cups[i],s.cups[j])){
s.oldMove1=i;
s.oldMove2=j;
memo.push(s);
}
}
}
memo.pop();
}
printf("-1\n");
}
int main(){
while(1){
scanf("%d %d",&n,&m);
if(n+m==0)break;
setData();
}
}
----
*0505 Questionnaire
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0505
旅行先の候補地を決める問題。
アンケート結果の集計データから、人気の高い候補地順に出力する。
解法
集計するだけです。
#include<stdio.h>
#include<string.h>
#include <algorithm>
struct total{
int no,sum;
bool operator<(const total t)const{
if(sum!=t.sum) return sum>t.sum;
return no<t.no;
}
};
int main(){
int n,m,t;
while(scanf("%d %d",&n,&m),n+m>0){
total sums[1001];
for(int i=0;i<m;i++){
sums[i].no=i+1;
sums[i].sum=0;
}
while(n--){
for(int i=0;i<m;i++){
scanf("%d",&t);
sums[i].sum+=t;
}
}
std::sort(sums,sums+m);
for(int i=0;i<m;i++)printf("%s%d",i==0?"":" ",sums[i]);
printf("\n");
}
}
----
*0506 String
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0506
文字列を決まった規則で変換し続けた時最終的にどのような文字列になるかを答える問題。
解法
文字列も短く変換するパイプに文字列を繰り返しとおすだけです。
速度より分かりやすさを重視して実装しました。
#include<iostream>
#include<string>
#include<stdio.h>
std::string change(std::string& text){
std::string ans="";
int size=text.size(),c=0;
char t[2],num[10];
t[0]=text[0];
t[1]='\0';
text.append("\0");
for(int i=0;i<=size;i++){
if(t[0]==text[i]){
c++;
}else{
sprintf(num,"%d",c);
ans.append(num);
ans.append(t);
c=1;
t[0]=text[i];
}
}
return ans;
}
int main(){
std::string text;
int n;
while(1){
std::cin>>n;
if(n==0) break;
std::cin>>text;
for(int i=0;i<n;i++){
text=change(text);
}
std::cout<<text<<"\n";
}
}
----
*0507 Square
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0507
解法
ひとつ左よりも小さいか同じ値にそろえて再帰するだけです。
#include<stdio.h>
#include<vector>
int memo[31];
void saiki(int deep,int n,int size){
if(n==0){
printf("%d",memo[0]);
for(int i=1;i<deep;i++){
printf(" %d",memo[i]);
}
printf("\n");
}
if(size>n) size=n;
for(int i=size;i>=1;i--){
memo[deep]=i;
saiki(deep+1,n-i,i);
}
}
int main(){
int n;
while(scanf("%d",&n),n>0){
saiki(0,n,n);
}
}
----
*0508 String With Rings
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0508
与えられたグラフの中で同じ点を1度しか通らずに出来るだけ多くの点を移動するとき何個の点を移動できるか求める問題。
解法
グラフの問題なのでグラフとして解きます。
単純にグラフを探索する深さ優先探索で解きます。
原理は分かりませんがリングが複数のリングR1,R2,,,Rnに分かれているとき、スタート地点となる点は必ずRiの中でもっとも辺の少ない点になるそうです。
これを求めるために、setData関数の中では最初にリングがいくつに分かれているかとRiの最小ノード数を求めておきます。
後は深さ優先探索で解くだけです。
#include <stdio.h>
int gPointCount[101];
void nodeSearch(int rings[101][101],int nodeSize[101],int gTypes[101],int no,int gType){
int size=nodeSize[no];
gTypes[no]=gType;
gPointCount[gType]++;
for(int i=0;i<size;i++){
if(gTypes[rings[no][i]]==-1){
nodeSearch(rings,nodeSize,gTypes,rings[no][i],gType);
}
}
}
int ringLen(int rings[101][101],int nodeSize[101],bool moveOK[101],int no,int deep){
moveOK[no]=false;
int max=-1,t;
for(int i=0;i<nodeSize[no];i++){
if(moveOK[rings[no][i]]==true){
t=ringLen(rings,nodeSize,moveOK,rings[no][i],deep+1);
max=max>t?max:t;
}
}
moveOK[no]=true;
if(max==-1) return deep;
return max;
}
void setData(int n){
int rings[101][101];
int nodeSize[101];
int gTypes[101],gNodeMins[101],gTypeCount=0;
bool moveOK[101];
int a,b;
for(int i=0;i<101;i++){
nodeSize[i]=0;
gTypes[i]=-1;
gNodeMins[i]=101;
moveOK[i]=true;
}
for(int i=0;i<n;i++){
scanf("%d %d",&a,&b);
a--;
b--;
rings[a][nodeSize[a]]=b;
rings[b][nodeSize[b]]=a;
nodeSize[a]++;
nodeSize[b]++;
}
for(int i=0;i<101;i++){
if(gTypes[i]==-1 && nodeSize[i]>0){
gPointCount[gTypeCount]=0;
nodeSearch(rings,nodeSize,gTypes,i,gTypeCount);
gTypeCount++;
}
}
for(int i=0;i<101;i++){
if(nodeSize[i]>0) gNodeMins[gTypes[i]]=gNodeMins[gTypes[i]]>nodeSize[i]?nodeSize[i]:gNodeMins[gTypes[i]];
}
int t,max=1;
for(int i=0;i<101;i++){
if(nodeSize[i]==0) continue;
if(gNodeMins[gTypes[i]]==nodeSize[i] && max<gPointCount[gTypes[i]]){
t=ringLen(rings,nodeSize,moveOK,i,1);
max=t>max?t:max;
}
}
printf("%d\n",max);
}
int main(){
int n;
scanf("%d",&n);
while(n!=0){
setData(n);
scanf("%d",&n);
}
}
----
*0509sheets
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0509
1万枚のシートを平面に広げたとき、全シートの周長と面積を出すという問題です。
解法
シートの重なりを考慮に入れないといけないためかなりの難問です。
解き方を思いつかず答えの考え方を読んでしまいました。
http://www.ioi-jp.org/joi/2005/2006-ho-prob_and_sol/2006-ho-t5-review.html
集合を使うかなり難しいものですが何とかコード実行速度1位(2011/10/24時点)で正答しました。
一列ずつに区切って計算するというコロンブスの卵的発想の問題です。
#include<stdio.h>
#include<vector>
#include <algorithm>
#include <string.h>
const int typeIn=1,typeOut=-1,mapSize=10003;
struct point{
int x1,x2,y,inOut;
bool operator<(const point p)const{
if(y!=p.y)return y<p.y;
return inOut>p.inOut;
}
};
void setMap(int n,int type){
std::vector<int> sheetIO[mapSize];//シートにinOut[x座標]する。Y座標は0から増えていく
std::vector<point> points;
point p1,p2;
int x1,y1,x2,y2,x,y,ioCount[mapSize];
memset(ioCount,0,mapSize*4);
p1.inOut=typeIn;
p2.inOut=typeOut;
for(int i=0;i<n;i++){
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
x1++;//0列目はダミーとして使うので一列シートをずらす
x2++;
p1.x1=p2.x1=x1;
p1.x2=p2.x2=x2;
p1.y=y1;
p2.y=y2;
points.push_back(p1);
points.push_back(p2);
}
std::sort(points.begin(),points.end());
int ansR=0,ansS=0,old,now,pSize=points.size();//周長,面積、一列手前、今計算中の列、
for(int i=0;i<pSize;i++){
p1=points[i];
//printf("(%d %d %d %d)",p1.y,p1.inOut,p1.x1-1,p1.x2-1);
for(int x=p1.x1;x<p1.x2;x++){
if(sheetIO[x].empty() || ioCount[x]==0){
sheetIO[x].push_back(p1.y);
ioCount[x]=1;
}else{
ioCount[x]+=p1.inOut;
if(ioCount[x]==0){
sheetIO[x].push_back(p1.y);
}
}
}
}
int yOld1,yOld2,yNow1,yNow2,pSize2;
unsigned int pointer1,pointer2;
for(int x=1;x<mapSize;x++){
pSize2=sheetIO[x].size();
for(int i=0;i<pSize2;i+=2){
ansS+=sheetIO[x][i+1]-sheetIO[x][i];
ansR+=2*(sheetIO[x][i+1]-sheetIO[x][i])+2;
if(i!=pSize2-2 && sheetIO[x][i+2]==sheetIO[x][i+1]){
ansR--;
}
}
pointer1=pointer2=0;
while(pointer1<sheetIO[x-1].size() && pointer2<sheetIO[x].size()){
yOld1=sheetIO[x-1][pointer1];
yOld2=sheetIO[x-1][pointer1+1];
yNow1=sheetIO[x][pointer2];
yNow2=sheetIO[x][pointer2+1];
if(yOld1>=yNow2){
pointer2+=2;
}else if(yOld2<=yNow1){
pointer1+=2;
}else if(yOld2>=yNow2 && yOld1>=yNow1 && yOld1<=yNow2){
ansR-=2*(yNow2-yOld1);
pointer2+=2;
}else if(yOld2>=yNow2 && yOld1<=yNow1){
ansR-=2*(yNow2-yNow1);
pointer2+=2;
}else if(yOld2<=yNow2 && yOld1<=yNow1 && yOld2>=yNow1){
ansR-=2*(yOld2-yNow1);
pointer1+=2;
}else if(yOld2<=yNow2 && yOld1>=yNow1){
ansR-=2*(yOld2-yOld1);
pointer1+=2;
}
}
}
if(type==2){
printf("%d\n%d\n",ansS,ansR);
}else{
printf("%d\n",ansS);
}
}
int main()
{
int n,type;
scanf("%d %d",&n,&type);
while(n!=0 || type!=0){
setMap(n,type);
scanf("%d %d",&n,&type);
}
}
----
上記コードをBit演算で高速化できないか試してみたバージョンです。
結局速度はでずコード実行速度が遅すぎで不正解となるコードです。
下記コードはシートの数が1万枚でも10枚でもほぼ同じ数秒で答えが出正しい答えを返します。
計算量が安定しているという利点はあります。
このコード最初はうまくいきませんでした。
BitSetは何Bitでメモリ確保しようとも実際には32Bitの倍数でBitが確保されます。
なので19Bit確保すると残り13Bitには1が確保されたままになります。
このためBitSetのCount関数を使うと19Bitの中の1Bitの数と13Bitに設定された1の合計がかえってきます。
これを知らなかったため最初コードがうまくいきませんでした。
YAHOO知恵袋でそのことを教えてもらいコードがうまくいきました。
#include<stdio.h>
#include <bitset>
#include <iostream>
const int size=10016;//縦横のマップサイズとりあえずサンプルデータを試せるサイズに限定
std::bitset<size> map[size],temp,temp2,temp3;//平面をmap[y]の短冊切りにする、シートのある地点を1Bit
void setMap(int n,int type){
int x1,y1,x2,y2,ansS=0,ansR=0;
for(int i=0;i<size;i++)map[i].reset();
for(int i=0;i<n;i++){
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
y1++;
y2++;
x1++;
x2++;
temp.reset();
temp.flip();
temp>>=(size-x2+x1);
temp<<=(x1);
for(int y=y1;y<y2;y++){
map[y]|=temp;
}
}
int t;
for(int i=1;i<size;i++){
temp=map[i];
//std::cout<<temp<<" "<<temp.count();//<<"\n";計算に使うマップの表示、シートがある部分が1無い部分が0最後尾にCount関数で求めた行の1の数が出るはずなのですが?
temp2=map[i-1];
t=temp.count();
ansS+=t;
ansR+=2*t;
//上段と下段で切れ端の共通辺を取り除く
temp3=temp&temp2;
ansR-=2*temp3.count();
//切れ端の両端を計算する
temp2=map[i];
temp3=(temp<<1);
temp3^=temp2;
//std::cout<<"("<<temp3.count()<<")\n";
ansR+=temp3.count();//切れ端の片端を計算する
}
if(type==2){
printf("%d\n%d\n",ansS,ansR);
}else{
printf("%d\n",ansS);
}
}
int main()
{
int n,type;
scanf("%d %d",&n,&type);
while(n!=0 || type!=0){
setMap(n,type);
scanf("%d %d",&n,&type);
}
}
----
*0510
2人のテスト点数を比べて合計点が多い方を出力する問題。
解法
私は興味ありませんが、ショートコーディングの一番初めの入門にいい問題かもしれません。
#include<stdio.h>
int main(){
int s[2],c;
s[0]=s[1]=0;
for(int i=0;i<8;i++){
scanf("%d",&c);
s[i/4]+=c;
}
printf("%d\n",s[0]>s[1]?s[0]:s[1]);
}