「AOJ1011～1020」の編集履歴（バックアップ）一覧に戻る
AOJ1011～1020 - (2012/03/14 (水) 17:33:22) のソース
----
*1011 Finding the Largest Carbon Compound Given Its Long
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1011
CとHで出来た炭素鎖からHを省き、できた鎖のCの両端を持った時両端が最も長くなる距離をｎとする。
長さがｎを超えないでCを最大までくっつけた時数字上何個までCを接続できるか答えよという問題。
解法
この問題は英語読解が出来なかったためYahoo知恵袋で問題の題意を質問して解きました。
題意が分かれば対称性を利用して解ける簡単な問題です。
#include<stdio.h>
void calc(int perm[31]){
perm[0]=0;
perm[1]=1;
perm[2]=2;
perm[3]=5;
for(int i=4;i<31;i++){
if(i&1==1){
perm[i]=4*(((perm[i-2]-1)/4)*3+1)+1;
}else{
perm[i]=6*(((perm[i-3]-1)/4)*3+1)+2;
}
}
}
int main(){
int perm[31],n;
calc(perm);
while(scanf("%d",&n)!=EOF){
printf("%d\n",perm[n]);
}
}
*1012
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1012
Operations with Finite Sets
集合操作の演算を行う問題。
集合操作を行う部分にポカミスがないか、再帰下降構文解析の部分にポカミスがないか2重のポカミスが怖いので中々コードを投稿する気に慣れなかった問題。
とりあえず3流高卒なので、再帰下降構文解析なんて習ったこともなく我流再帰下降構文解析で解いた。
コードサイズは11/38位なのでまあまあのコードをかけたと思う。
このレベルの問題でようやく大学一年レベル、大学生レベルのプログラムは難しいなあと思うばかり。
これ左から優先だからコードが簡単なのであって、uとかiに優先順位があったら少し難しくなるな。
#include<stdio.h>
#include<set>
#include<map>
#include<iostream>
#include<string>
#define cset const std::set<int>
#define sset std::set<int>
#define sit sset::iterator
//グローバル変数まとめ
std::map<char,sset > symbols;//各記号のシンボル
sset all;//全要素
//グローバル変数まとめ終わり
sset u(sset s1,cset s2){
//和集合
s1.insert(s2.begin(),s2.end());
return s1;
}
sset i(sset s1,sset s2){
//共通集合
sset s3;
sit it=s1.begin();
while(it!=s1.end()){
if(s2.find(*it)!=s2.end())s3.insert(*it);
it++;
}
return s3;
}
sset d(sset s1,sset s2){
//差集合
sset s3;
sit it=s1.begin();
while(it!=s1.end()){
if(s2.find(*it)==s2.end())s3.insert(*it);
it++;
}
return s3;
}
sset s(sset s1,sset s2){
//?集合
sset s3,s4,s5;
s3=d(s1,s2);
s4=d(s2,s1);
s5=u(s3,s4);
return s5;
}
sset c(sset s1){
//補集合
sset s3;
sit it=all.begin();
while(it!=all.end()){
if(s1.find(*it)==s1.end())s3.insert(*it);
it++;
}
return s3;
}
sset saiki(const std::string& text,int& p,bool typeRe,int deep){
sset nowSet;
char t;
p++;
while(text.size()>p){
t=text[p];
if(symbols.find(t)!=symbols.end()){
nowSet=symbols[t];
}else if(t=='u'){
nowSet=u(nowSet,saiki(text,p,true,deep+1));
}else if(t=='i'){
nowSet=i(nowSet,saiki(text,p,true,deep+1));
}else if(t=='d'){
nowSet=d(nowSet,saiki(text,p,true,deep+1));
}else if(t=='s'){
nowSet=s(nowSet,saiki(text,p,true,deep+1));
}else if(t=='c'){
nowSet=c(saiki(text,p,true,deep+1));
}else if(t=='('){
nowSet=saiki(text,p,false,deep+1);
}else if(t==')'){
return nowSet;
}
if(typeRe==true) return nowSet;
p++;
}
return nowSet;
}
bool setData(){
all.clear();
symbols.clear();
char symbol=' ';
int n,num;
std::string text;
sset tempSet;
symbols['A']=symbols['B']=symbols['C']=symbols['D']=symbols['E']=tempSet;
while(1){
if(scanf("%c",&symbol)==EOF) return false;
if(scanf("%d",&n)==EOF) return false;
if(symbol=='R')break;
for(int i=0;i<n;i++){
scanf("%d",&num);
all.insert(num);
symbols[symbol].insert(num);
}
}
std::cin>>text;
int p=-1;
sset ans=saiki(text,p,false,0);
int temp=0;
for(sit it=ans.begin();it!=ans.end();it++){
printf("%s%d",temp==0?"":" ",(*it));
temp++;
}
if(ans.size()==0)printf("NULL");
printf("\n");
return true;
}
int main(){
while(setData()){
}
}
----
*1014 Computation of Minimum Length of Pipeline
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1014
源泉から都市へパイプラインを引く問題。
都市間の距離、源泉から都市への距離が与えれるので最小の距離でパイプを接続せよという問題。
解法
どの源泉も供給能力は同じで区別がつきません。
源泉を全て丸で囲んで１点とみなし、源泉から都市への最小距離を最初に更新します。
後は都市と源泉を点とみなしグラフの上でプリム法で接続していくだけです。
#include<stdio.h>
#include<queue>
#include<string.h>
#include <algorithm>
int map[102][102];//0が源泉ひとまとめ、1以降が都市
struct Edge{
int to,len;//エッジの接続先と繋げるパイプの長さ
bool operator<(const Edge& e)const{
return e.len<len;
}
};
const int stop=0;
int prim(int d){
//プリム法でパイプラインの配置を解く。
//まず源泉は全て長さ0の辺でつながっているという過程で始める
std::priority_queue<Edge> qu;
bool conOKs[101];
memset(conOKs,true,sizeof(conOKs));
Edge edge;
edge.len=0;
edge.to=0;
qu.push(edge);//最初長さ0で源泉に接続する
int nextP,sumLen=0,count=0;//
while(!qu.empty()){
edge=qu.top();//一番短いパイプラインを選んでいく
qu.pop();
nextP=edge.to;
if(conOKs[nextP]==false) continue;//接続済みの都市にパイプラインをつなげようとした
conOKs[nextP]=false;
count++;//つなげた都市の数
sumLen+=edge.len;//答えの集計
if(count==d+1) break;//全ての都市と源泉をつないだら終了
for(int i=0;i<=d;i++){
if(conOKs[i]==false||map[nextP][i]==stop)continue;//もうパイプを通した都市もしくは接続不能の都市への接続は無視する
edge.to =i;
edge.len=map[nextP][i];
qu.push(edge);
}
}
return sumLen;
}
void setData(int s,int d){
int temp;
memset(map,stop,sizeof(map));
for(int i=0;i<s;i++){
for(int j=1;j<=d;j++){
scanf("%d",&temp);
if(map[0][j]==0 || (map[0][j]>temp&&temp!=stop)){
map[0][j]=temp;//全ての源泉を丸で囲んで１点とみなす
}
map[j][0]=map[0][j];
}
}
for(int i=1;i<d;i++){
for(int j=i+1;j<=d;j++){
scanf("%d",&map[i][j]);//都市間の距離のセット
map[j][i]=map[i][j];
}
}
printf("%d\n",prim(d));
}
int main(){
int s,d;
while(1){
scanf("%d %d",&s,&d);
if(s==0 && d==0) break;
setData(s,d);
}
}
----
*1015 Dominating Set
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1015
最小の頂点支配集合を求める問題。
解法
初めはBitSetで解こうかと考えたのですが、最大頂点数が分からなかった(多分書いてない？)のでvectorに頂点支配されるかの状態を保存することにしました。
コードは深さ優先探索である点を頂点支配集合に入れる入れないを２分探索しているだけです。
素朴な方法で速度が出なかったので小手先のテクニックを入れたらコードが膨らみました。
深さ優先探索するまえに辺の多い点を優先して調べるよう並べ替えること。
もう一つはある点で支配できる領域が他の点で支配できる領域のサブセットをなすならその点は探索で無視する。
残りは探索の途中で残りの点をすべて使っても頂点支配出来ない点が判明した時探索を枝刈すること。
ということをしています。
小手先すぎて駄目ですね、20倍程度しか速くなりませんでした。
頂点支配集合についてきちんと勉強することにしようと考えた問題でした。
#include<stdio.h>
#include<vector>
#include <algorithm>
#include <map>
#include <set>
struct vecSizeSorter
{
bool operator()( const std::vector<int>& lhs, const std::vector<int>& rhs ) const
{
return lhs.size() > rhs.size();//点に入る辺の本数が多い方を優先
}
};
//グローバル変数まとめ
int ans,x;
std::vector<std::vector<int> > map;//グラフのつながり
std::vector<bool> subSet;//ある点で支配される領域が別の点のサブセットでないかのチェック
std::vector<std::set<int> > cut;
//グローバル変数終わり
void saiki(std::vector<bool> state,int p,int count,int vCount){
if(ans<=vCount) return;
//支配集合に入ってる数が全体になった
if(count==x){
ans=ans>vCount?vCount:ans;
return;
}
if(p>=x)return;
if(subSet[p]==true){
saiki(state,p+1,count,vCount);//この点Pは他の点のサブセットなので無視する
return ;
}
for(int i=0;i<x;i++){
if(state[i]==false && cut[p].find(i)==cut[p].end()){
//残りの点では被覆できないことが判明したのでリターン
return ;
}
}
int backCount=count;
std::vector<bool> back=state;
//この点ｐを支配集合とする
for(int i=0;i<map[p].size();i++){
if(state[map[p][i]]==false){
count++;
state[map[p][i]]=true;
}
}
if(backCount!=count){
saiki(state,p+1,count,vCount+1);//支配集合とする
state=back;//変化があったので元に戻す
count=backCount;
}
saiki(state,p+1,count,vCount);//この点を支配集合としない
}
bool isSubSet(std::vector<int>& vec1,std::vector<int>& vec2){
//ソート済みを渡すので必ずvec1>=vec2
//vec2がvec1のサブセットでないかをチェックする
std::set<int> sets;
sets.insert(vec1.begin(),vec1.end());
int count=sets.size();
sets.insert(vec2.begin(),vec2.end());
if(count==sets.size()){
return true;
}else{
return false;
}
}
void search(int x,int y){
std::vector<bool> state;
ans=x+1;
map.clear();
map.resize(x);
state.resize(x);
int from,to;
for(int i=0;i<y;i++){
scanf("%d %d",&from,&to);
map[from].push_back(to);
map[to].push_back(from);
}
for(int i=0;i<x;i++){
map[i].insert(map[i].begin(),i);//支配集合の中心となる点を先頭に挿入
state[i]=false;
}
std::sort(map.begin(),map.end(),vecSizeSorter());//小手先テク頂点集合をソートして辺の多い点から検証する
int p;
std::map<int,int> temp;
for(int i=0;i<x;i++){
temp[map[i][0]]=i;//点の位置が入れ替わったので修正
}
for(int i=0;i<x;i++){
for(int j=0;j<map[i].size();j++){
map[i][j]=temp[map[i][j]];
}
std::sort(map[i].begin(),map[i].end());
}
subSet.clear();
subSet.resize(x);//ある点で頂点支配できる点が他の点の頂点支配のサブセットなら無視する
for(int i=0;i<x;i++)subSet[i]=false;
for(int i=0;i<x-1;i++){
for(int j=i+1;j<x;j++){
if(isSubSet(map[i],map[j])==true){
subSet[j]=true;
}
}
}
//深さ優先探索の途中残りの点で被覆が出来ないことが判明させるためのSet
cut.clear();
cut.resize(x);
cut[x-1].insert(map[x-1].begin(),map[x-1].end());
for(int i=x-2;i>=0;i--){
cut[i].insert(cut[i+1].begin(),cut[i+1].end());
cut[i].insert(map[i].begin(),map[i].end());
}
//深さ優先探索で一つずつ点を頂点集合に含める含めないを試して最小値を求める
saiki(state,0,0,0);
printf("%d\n",ans);
}
int main(){
int y;
while(1){
scanf("%d %d",&x,&y);
if(x==0 && y==0) break;
search(x,y);
}
}
----
*1016 Fibonacci Sets
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1016
フィナボッチ数を題材にしたグラフの問題。
解法
同じ番号になった点は区別がつきません。
それを利用しt記録します。
後は小さい数から大きい方へ線を引いていって引ける長さｄまで線を引いてその範囲に別の数字があればそこを出発点にまた線を引いていきます。
この方法で線が全体で幾つに分かれるかをカウントして終了です。
#include<string.h>
#include<stdio.h>
void setData(int v,int d){
bool hit[1002];
memset(hit,false,sizeof(hit));
int fibo[3];
fibo[0]=1,fibo[1]=1;
for(int i=0;i<v;i++){
fibo[(i+2)%3]=(fibo[(i+1)%3]+fibo[i%3])%1001;
hit[fibo[(i+2)%3]]=true;
}
int moveCount=0,allCount=0,add=0;//下から上へ順番にクロールしていく
for(int i=0;i<1002;i++){
if(d==1 && hit[i]==true){
allCount++;//ｄ＝1のときだけ特別処理
continue;
}else if(d==1){
continue;
}
if(hit[i]==true && moveCount+1<d){
moveCount=0;//番号の割り振られた点が見つかったのでここから線を引きなおす
add=1;
}else{
moveCount+=add;
}
if(moveCount+1==d){
allCount++;//線を引いても届かない範囲があることが判明したので範囲をカウントする
moveCount=0;
add=hit[i]?1:0;//今の番号iが数字ならこれから再出発、0なら数字が見つかるまでiをインクリメントする
}
}
allCount+=add;
printf("%d\n",allCount);
}
int main(){
int v,d;
while(scanf("%d %d",&v,&d)!=EOF){
setData(v,d);
}
}
----
*1017 Riffle Shuffle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1017
リフルシャッフルをシミュレートしシャッフル後一番上にあるカードを答える問題。
解法
りフルシャッフルをそのまま実装します。
#include<stdio.h>
#include<vector>
void shuffle(std::vector<int>& cards,int d,int n){
std::vector<int> deckA,deckB;
for(int i=0;i<n/2;i++)deckB.push_back(cards[i]);
for(int i=n/2;i<n;i++)deckA.push_back(cards[i]);//二つの山を作る
int nowP=0,up,pA=0,pB=0;
while(nowP<n){
up=pA+d>deckA.size()?deckA.size():pA+d;
for(int i=pA;i<up;i++){
cards[nowP]=deckA[i];//Aの山からCardへ戻す
nowP++;
pA++;
}
up=pB+d>deckB.size()?deckB.size():pB+d;//次に挿入するカードが山Bを超えるなら山Bの上限で切ってカードを入れる
for(int i=pB;i<up;i++){
cards[nowP]=deckB[i];//Bの山からCardへ戻す
nowP++;//山Cのポインタをインクリメント
pB++;
}
}
}
void setData(int n,int r){
std::vector<int> cards;
int d;
for(int i=0;i<n;i++)cards.push_back(i);//カードのセット
for(int i=0;i<r;i++){
scanf("%d",&d);//シャッフル間隔
shuffle(cards,d,n);
}
printf("%d\n",cards[n-1]);
}
int main(){
int n,r;
while(scanf("%d %d",&n,&r)!=EOF){
setData(n,r);
}
}
----
*1018 Cheating on ICPC
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1018
プログラムコンテストの問題を解くのにかかる時間とペナルティ時間から最小タイムを答える問題。
ここまでの問題を解くのにかかった時間分が、それ以後の問題を解くたびにペナルティとして加算される。
解法
ペナルティ分の加算をそのまま足しこむだけで解決います。
#include<stdio.h>
#include <algorithm>
void calc(int n){
unsigned long long int scores[102],ans=0;
for(int i=0;i<n;i++){
scanf("%llu",&scores[i]);
}
std::sort(scores,scores+n);
for(int i=0;i<n;i++){
ans+=scores[i]*(n-i);
}
printf("%llu\n",ans);
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
calc(n);
}
}
----
*1019 Vampirish Night
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1019
グルメなバンパイアの一家が要求する血液の種類と量をきちんと提供できるかを計算する問題。
解法
冷蔵庫にある送料から要求分を順次引いていき供給できなくなればNoを返します。
#include<stdio.h>
void setData(int n,int k){
int bloods[101],b;
for(int x=0;x<k;x++){
scanf("%d",&bloods[x]);//全血液量を配列に保存
}
bool allOK=true;
for(int y=0;y<n;y++){
for(int x=0;x<k;x++){
scanf("%d",&b);
bloods[x]-=b;//血液を引く
if(bloods[x]<0){
allOK=false;//足らない血液が判明
}
}
}
printf("%s\n",allOK?"Yes":"No");
}
int main(){
int n,k;
while(1){
scanf("%d %d",&n,&k);
if(n==0 && k==0)break;
setData(n,k);
}
}
----
*1020 Cleaning Robot
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1020
升目で区切られた部屋部屋をランダム移動で掃除するロボットが充電器のある部屋でバッテリー切れになる確率を求める問題。
解法
あるターンである部屋にいるときいままでどの経路を通ってきたにせよ、バッテリー残量は同じです。
こうなると今いる部屋を基準に経路をまとめてメモ化探索で片がつきます。
#include<stdio.h>
#include<string.h>
int dxs[]={1,0,-1,0};
int dys[]={0,1,0,-1};
void calc(int n){
double memo[2][3][3];//
double sum;
memset(memo,0,sizeof(memo));
char sp,ep,outP;//スタート地点、ゴール地点、物置
scanf(" %c %c %c",&sp,&ep,&outP);
sp =sp-'A';//部屋番号を数字に戻す
ep =ep-'A';
outP=outP-'A';
int butX=outP%3;
int butY=outP/3;
memo[0][sp/3][sp%3]=1;
int x,y,nx,ny;//今の部屋のｘ、ｙ座標、次の部屋のnｘ、nｙ座標
int now,next;
for(int turn=0;turn<n;turn++){
now=(turn)%2;
next=(turn+1)%2;
memset(memo[next],0,sizeof(memo[next]));
sum=0;//メモ化探索で１ターンずつ移動をシミュレートする。
for(int p=0;p<9;p++){
x=p%3;
y=p/3;
for(int i=0;i<4;i++){
nx=x+dxs[i];
ny=y+dys[i];
if(nx<0 || 2<nx ||ny<0 || 2<ny||(butX==nx && butY==ny)){
memo[next][y][x]+=memo[now][y][x];//物置か外に出そうならとどまる
}else{
memo[next][ny][nx]+=memo[now][y][x];//物置でないので移動
}
sum+=memo[now][y][x];
}
}
}
printf("%.8lf\n",memo[n%2][ep/3][ep%3]/sum);
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0) break;
calc(n);
}
}
