「AOJ1011～1020」の編集履歴（バックアップ）一覧に戻る
AOJ1011～1020 - (2011/11/13 (日) 15:44:09) のソース
----
*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);
}
}
