「AOJ1000～1010」の編集履歴（バックアップ）一覧に戻る
AOJ1000～1010 - (2011/11/11 (金) 18:53:06) のソース
----
*1001 Binary Tree Intersection And Union
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1001
バイナリツリーを表す２つの符号からバイナリツリーを作り、両方のツリーの共通集合か和集合を計算して符号で返すという問題。
解法。
この問題は正答者数が多いので情報系の正式なカリキュラムの一部としてこの問題が出てる可能性が高そうです。
学がないので私は四苦八苦でした。
調べたらたぶん正式な方法が出てくるとは思うのですが一つ腕試しと思い自力で暗中模索してみました。
手探りで作った結果木構造を作る部分に無駄な処理がありスパゲッティ化しています。
いつか綺麗になおすかもしれません。
木構造が実は苦手なのを差し引いても、スパゲッティ化で自分の実力を思い知った問題でした。
#include<stdio.h>
#include<malloc.h>
#include<string>
#include<iostream>
struct Node{
Node* right;
Node* left;
int count;
};
void treeFree(Node* node){
if(node->left!=NULL){
treeFree(node->left);
}
if(node->right!=NULL){
treeFree(node->right);
}
free(node);
node=NULL;
}
Node* talloc(void){
Node* n=(Node *)malloc(sizeof(Node));
n->right=n->left=NULL;
(*n).count=1;
return n;
}
Node* gentree(Node* node,int& p,std::string& text,int add){
Node* left;
Node* right;
left=right=NULL;
if(node==NULL){
node=talloc();
}else{
(*node).count++;
}
p+=add;
if(text[p]=='('){
p++;
left=gentree(node->left,p,text,0);//左側を作る
if(text[p]==','){
p++;
if(text[p]=='('){
right=gentree(node->right,p,text,1);//枝先の全体を囲む（を無視するためaddに1を足す
p++;
}else if(text[p]==')'){
p++;//閉じかっこでこの部分の枝が終わるなら
right=talloc();
if(node->right!=NULL) (*node->right).count++;//作った枝先が重なるなら+1
}
}else if(text[p]==')'){
right=NULL;
p++;
}
}else if(text[p]==','){
//左が決定されるが右隣の文字が'('の可能性を探る
left =talloc();
if(node->left!=NULL) (*node->left).count++; //枝先が重なるのでカウンタに足しこむ
p++;
if(text[p]=='('){
right=gentree(node->right,p,text,1);//右隣が(だったので一文字無視するためにaddに1を足す
p++;
}else if(text[p]==')'){
p++;//閉じかっこなので右の枝先をたしておく
right=talloc();
if(node->right!=NULL) (*node->right).count++;//
}
}else if(text[p]==')'){
p++;//閉じかっこなので1足して次へ
}
if(node->left==NULL) node->left=left;
else if(node->left!=left) free(left);
if(node->right==NULL) node->right=right;
else if(node->right!=right) free(right);
return node;
}
Node* top=NULL;
void treeToCode(Node* node,int type){
if(node->left!=NULL && (*node->left).count>=type){
//木を符号にして返す、typeは1か２
printf("(");
treeToCode(node->left,type);
if(node->right!=NULL && (*node->right).count>=type){
printf(",");
treeToCode(node->right,type);
}
printf(")");
}
}
int main(){
std::string type,text1,text2;
int p;
while(1){
top=NULL;
p=0;
std::cin>>type>>text1>>text2;//uかiか、バイナリツリーの符号二つ
if(std::cin.eof()==true)break;
top=gentree(top,p,text1,1);//最初に木を作る
p=0;
top=gentree(top,p,text2,1);//同じ関数を使って木を辿りながらつけたせる部分を調べる、共通部分はNodeのcountをインクリメントする
treeToCode(top,type=="i"?2:1);
printf("\n");
treeFree(top);
}
}
----
*1002 Extraordinary Grid I
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1002
横道が３本で縦道がｒ本ある格子上に本棚が配置された図書館で最短経路で本を返していく問題。
2
2
YNNNNYYY
4
NYNNYYNNNYNYYNNN
というのは１行目がデータセットがｎ個(サンプルでは２個)あり
２行目では本棚が２列並んでおり
YNNN
NYYY
という配列で本棚に返す本があるというのを表しています。
解法
動的計画法で一列ずつその時点での最短ルートを調べていき更新していくだけです。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void setData(){
const int rowSize=3,colSize=10002,shelfSize=2;
int up,down,now,next,shelfs[colSize][shelfSize],memos[colSize][rowSize],tUp,tDown,n,y,x,perm;
char t;
scanf("%d",&n);
memset(memos,0,colSize*rowSize*4);
memset(shelfs,0,shelfSize*colSize*4);
scanf("%c",&t);
for(int i=0;i<n*4;i++){
y=i/(2*n);
x=i%(2*n);
scanf("%c",&t);
shelfs[(x+1)/2][y]+=(t=='Y'?1:0);
}
//0.5を１単位
for(int i=0;i<rowSize;i++)memos[0][i]=i*2;
for(int col=0;col<n+1;col++){
up=down=-1;
//なんとなく道がｎ行になっても対応できるように
for(int i=0;i<rowSize-1;i++){
if(shelfs[col][i]>0){
up=i*2+1;//その列で本を返す本棚の行の一番上の本棚の位置
break;
}
}
for(int i=rowSize-2;i>=0;i--){
if(shelfs[col][i]>0){
down=i*2+1;//その列で本を返す本棚の一番下の位置
break;
}
}
for(int i=0;i<rowSize;i++){
now=i*2;
if(up==-1)tUp=tDown=now;
else tUp=up,tDown=down;
for(int j=0;j<rowSize;j++){
next=j*2;
perm=memos[col][i]+abs(now-tUp)+abs(tUp-tDown)+abs(tDown-next)+2;//今いる位置から本を図で一番上の本棚に返して一番下の本棚に返して次の横道をnextにした場合
if(perm<memos[col+1][j] || memos[col+1][j]==0)memos[col+1][j]=perm;
perm=memos[col][i]+abs(now-tDown)+abs(tDown-tUp)+abs(tUp-next)+2;//今いる位置から本を図で一番下の本棚に返して一番上の本棚に返して次の横道をnextにした場合
if(perm<memos[col+1][j])memos[col+1][j]=perm;
}
}
}
//単位を元に戻して表示
printf("%d\n",(memos[n+1][0]-2)/2);
}
int main(){
int n;
scanf("%d",&n);
while(n--)setData();
}
----
*1003 Extraordinary Grid II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1003
携帯電話の簡易文字入力シミュレーションをする問題。
解法
文字列マトリックスと照合して変換する状態遷移マシーンをパイプとして用意して文字列を流し込むだけで解決します。
#include<stdio.h>
bool setData(){
char now='0',old='0',point=0;
int roops[]={5,6,6,6,6,6,8,6,8};
char cPuts[10][10]={"',.!?","abcABC","defDEF","ghiGHI","jklJKL","mnoMNO","pqrsPQRS","tuvTUV","wxyzWXYZ"};
while(now!='\n'){
if(scanf("%c",&now)==EOF)return false;
if(now=='0' && old=='0'){
printf(" ");
}else if(old=='0' && now!='0'){
point=0;
}else if(old==now){
point=(point+1)%roops[now-'1'];
}else if(old!=now){
printf("%c",cPuts[old-'1'][point]);
point=0;
}
old=now;
}
printf("\n");
return true;
}
int main(){
while(setData()){
}
}
----
*1004 Pair of Primes
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1004
自然数を２つの素数の和で表した時何通りの表し方があるかを調べる問題。
解法
定義域が10000と小さいので素数を篩にかけて下からチェックするだけです。
#include<stdio.h>
#include<string.h>
const int max=10002;
bool so[max];
void setSo(){
for(int i=1;i<max;i++)so[i]=(i&1);
so[1]=false;
so[2]=true;
for(int i=3;i<=100;i+=2){
if(so[i]==false)continue;
for(int j=i*3;j<max;j+=i*2){
so[j]=false;
}
}
}
int main(){
setSo();
int n,count;
while(scanf("%d",&n)!=EOF){
count=0;
for(int i=1;i<=n;i++){
if(so[i]&&so[n-i+1])count++;
}
printf("%d\n",count);
}
}
----
*1006 Boring Commercials
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1006
サンプルデータの説明をします。
一行目はチャンネルの数nとTvを見る予定の時刻p,q。
次の行からは各Tv番組のコマーシャル番組の数、その次の行にはコマーシャル番組の放送時間のセットがｎ行与えられています。
予定の時刻の間はずっとTvをつけつづけます。
チャンネルをかえることでコマーシャルを見ずに住む時間を求めます。
連続して通常番組を見られる時間のうち最も長い時間を答えよという問題。
解法
時刻という狭い範囲の数値を扱う問題であるため富豪プログラムで片をつけます。
時刻を分表示に直しTv番組の時刻を一分ごとに区切り、どの時刻にいくつのチャンネルでコマーシャルがあるかをカウントしていきます。
後は連続してコマーシャルを見ずに済む領域をカウントして計測していけば答えが出ます。
#include<stdio.h>
#include<map>
int timeToVal(int hhmm){
return (hhmm/100)*60+hhmm%100;
}
void setData(int n,int p,int q){
std::map<int,int> Tvs;//tvの時刻を保存する
int m,s,e;
for(int i=0;i<n;i++){
scanf("%d",&m);
while(m--){
scanf("%d %d",&s,&e);
s=timeToVal(s);
e=timeToVal(e);
for(int t=s;t<e;t++){
if(Tvs.find(t)==Tvs.end()){
Tvs[t]=1;
}else{
Tvs[t]++;
}
}
}
}
int count=0;
int ans=0;
int sTime=timeToVal(p);
int eTime=timeToVal(q);
for(int t=sTime;t<eTime;t++){
if(Tvs.find(t)==Tvs.end() || Tvs[t]<n){
count++;
}else{
ans=count>ans?count:ans;
count=0;
}
}
ans=count>ans?count:ans;
printf("%d\n",ans);
}
int main(){
int n,p,q;
while(1){
scanf("%d %d %d",&n,&p,&q);
if(n==0 && p==0 && q==0)break;
setData(n,p,q);
}
}
----
*1007 JPEG Compression
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1007
JPEGの画像走査を計算する問題。
解法
図にあるとおり走査すると下記のようなコードとなります。
i=x+yとなる直線式の概念を使って斜めのラインを確定し、i%2==0か1かで斜め上に走査するか斜め下に走査するかを決定して計算します。
#include<stdio.h>
void setData(int n,int p){
int map[11][11];
int sp,ep,x,y,count=1;
for(int i=0;i<=2*n;i++){
sp=i>n?i-n:0;
ep=i<n?i:n;
for(int j=sp;j<ep;j++){
x=i%2==0?j:i-j;
y=i%2==0?i-j:j;
map[y][x]=count;
count++;
}
}
}
int main(){
int n,p=1;
while(1){
scanf("%d",&n);
if(n==0)break;
setData(n,p)
}
}
----
*1008 What Color Is The Universe?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1008
宇宙の色を調べる問題。
宇宙を定点観測したときの色が数字で与えられる。
半分以上を同じ色が占めるならそれを宇宙の色とする。
ないならno colorとする。
解法
マップに各色の数を保存してカウントするだけです。
#include <stdio.h>
#include <map>
void setMap(int);
int main(){
int n;
scanf("%d",&n);
while(n!=0){
setMap(n);
scanf("%d",&n);
}
}
void setMap(int n)
{
std::map<int,int>datas;
int max=0,t;
int ans;
for(int i=0;i<n;i++){
scanf("%d",&t);
if(datas.find(t)!=datas.end()){
datas[t]++;
}else{
datas[t]=1;
}
if(max<datas[t]){
max=datas[t];
ans=t;
}
}
if(max>n/2){
printf("%d\n",ans);
}else{
printf("NO COLOR\n");
}
}
----
*1009 Greatest Common Divisor
GCDを求める問題
解法
アルゴリズムの教科書通りに実装するだけです。
#include <stdio.h>
int main(){
int n,m,k;
while(scanf("%d",&n)!=EOF){
scanf("%d",&m);
do{
k=m%n;
m=n;
n=k;
}while(k!=0);
printf("%d\n",m);
}
}
----
*1010 Dominoes Arrangement
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1010
ドミノを繋げて役を作れるかを問う問題。
入力データが
5
(1,3）(1,4) (7,4) (3,1) (7,8)なら
(1,3)(3,1)(1,4)(4,7)(7,3)のように繋げることができるのでYesを返す。
3
(0,3)(3.6)(1,5)の場合全てを繋げることができないのでNoを返す。
#include<stdio.h>
#include<string.h>
//グローバル変数まとめ
const int max=7;
int con[max][max];
int n;
bool allMoveOK;
//グローバル変数終わり
void saiki(int now,int deep){
if(deep==n){
allMoveOK=true;//グラフが全て森でつながっていた
return;
}
for(int i=0;i<max;i++){
if(con[now][i]>0){
con[now][i]--;
con[i][now]--;
saiki(i,deep+1);
if(allMoveOK==true) return;
con[now][i]++;
con[i][now]++;
}
}
}
void setData(){
char in[3];
memset(con,0,sizeof(con));
allMoveOK=false;
for(int i=0;i<n;i++){
scanf("%s",in);
in[0]-='0';
in[1]-='0';
con[in[0]][in[1]]++;
con[in[1]][in[0]]++;
}
for(int i=0;i<max;i++){
saiki(i,0);
if(allMoveOK==true)break;
}
printf("%s\n",allMoveOK?"Yes":"No");
}
int main(){
while(scanf("%d",&n)!=EOF){
setData();
}
}
