2117 Connect Line Segments
解法
さてこの問題自分なりに考えた解法は2種類で以下の通りです。
コード実行速度が悪いコードとコード実行速度2位のコードです。
単純に深さ優先探索を行うと線分が10本を超えたあたりで10！*2^10となり計算量が限界を超えます。
13や14などは枝刈で挑むのは論外です。
分岐が不可能なのでプリム法も使えません。
よって動的計画法を使わなくてはいけません。
動的計画法は、memo[次に両端のどちらの点から新しい線分を伸ばすか][これから新しく線分を伸ばす場所はどの線か][今までつなげた線分のリスト]=ここまでの折れ線の最小の長さ。
で動的計画法を適用していくだけの簡単な問題です。
この問題私はあまりいい解法ではなかったようでコード実行速度が出ませんでした。
私の場合スタート時全ての線分を折れ線の開始候補としていますがもしかしたらどこか一本の線分からスタートしていくだけでいいのかもしれません。
コード実行速度2位の方は1つの線分を結んだ、2つの線分を結んだ、、、ｎ個の線分を結んだまでが綺麗な順序で無駄なく実行されるようにソートしてから動的計画法を適用して解いています。
毎回思うが一位の壁は厚い、ランキング上位に入れても一位を抜けることはめったにない、一位手ごわすぎ。
2位のコード実は動的計画法のｎ/２本目まで線分を結んだところで残り半分は実は計算する必要はありません。
結んでない線分の補集合を取ってその折れ線との結びつきを試せば真中で計算が終わります。
しかしこれでコード実行速度1位を取れますがコードが少し膨らみますし2倍しか早くならないのでたかが練習問題でそこまでして一位を取る必要もないかなと考えます。
この問題を解いた時点でカンニングして解いたプロコンの過去問題は480問中31問この比率をこれからどんどん下げていくのが楽しみです。
個人的な雑記
プログラミングコンテストの過去問を1000問解いたって学歴、職歴、実績が三無い人間の私では世間から何の評価もされません。
プロコンの問題を解くことは私にとって単なる趣味でしかないのです。
使い捨て労働で仕事を探しながらこの趣味を完遂するのだけが楽しみです。
何かアプリでも作って売れたら世間からの評価も変わるかもしれないのでその可能性にかけるくらいです。
どうでもい話だが金儲けといえば小説もいい。
昔このサイトは小説サイトでした。
最初のころは小学生よりひどい設定集を書きこれはサイトの表の方にあり探しやすいところにある。
ある程度慣れてきてそこそこのものを作って
いた時期もあったのだが、これらはサイトの奥の方見つかりにくい位置に配置してしまっていた。
それでもそこそこのアクセス数がありアップするたびに1ページ頭4日で1000～3000アクセス、その後ぷっつりアクセス数が激減というそれなりに私の作品を楽しみにしている固定客がついたサイトでした。
これがご近所さんに盗作されてたらしいんだよね。
夏だから窓全開隣近所の会話が入ってくることもあるわけですよ。
「盗作がばれたなら偽物の堀江に謝らせればいいんですよ」
「編集担当なんて言ったと思います？ネットからの盗みは盗みになりません。盗みがばれたんならミックスすればいいんですよ」
録音し損ねたので証拠能力は無いけどこんな会話が隣家から飛び込んできた日もあったわけです。
まあ聞きに行ってもしらばくれられただけですけど。
堀江って私か私の家族でもう一人創作してるのがいるので我が家のことだと思うんだけどね。
私か私の家族の偽物がやってもない罪で謝罪していると思うと何とも悔しい話です。
創作で稼いでみたいなあとは思いますが、盗作されるが全部は書ききってない中途半端な設定や作りかけの残骸が多いので小説や設定で金儲けしたことは無いんだよね。
お隣さんはどうもクラッキングの手口にたけてるみたいなんだけど証拠がないんだよな。
堀江伸一
住所 兵庫県加古川市加古川町南備後79-16
以下コード
#include<stdio.h>
#include<queue>
#include<math.h>
#include<string.h>
struct State{
int nowNo,perm,r;//今いる地点と結んだ線分のリストのビット表現と次の向き
double len;//今まで引いた長さ
bool operator<(const State& s)const{
return len>s.len;
}
};
double memo[2][14][2<<14];//[次の線分の出発点][最後に結んだ線分][結んだ線のビット表現]
bool first[2][14][2<<14];//最初
void setData(int n,int i){
double xs[2][15],ys[2][15];
memset(first,true,sizeof(first));
for(int i=0;i<n;i++){
scanf("%lf %lf %lf %lf",&xs[0][i],&ys[0][i],&xs[1][i],&ys[1][i]);
}
//printf("scanOK");
double lensMemo[2][2][15][15],len1;//線分で結ぶ時の距離のメモ
for(int l1=0;l1<n;l1++){
for(int l2=0;l2<n;l2++){
if(l1==l2)continue;//同じ線分は結ばない
for(int r1=0;r1<2;r1++){
for(int r2=0;r2<2;r2++){
len1=sqrt(pow(xs[r1][l1]-xs[r2][l2],2)+pow(ys[r1][l1]-ys[r2][l2],2));
lensMemo[r1][r2][l1][l2]=len1;
}
}
}
}
//スタート地点となる線分のリストを作る
std::priority_queue<State> pQ;
State s,nextS;
int ansPerm=0;
s.len=0;//長さ0
for(int i=0;i<n;i++){
s.r=0;//どちらの両端から出発するか
s.perm=(1<<i);//スタートの線分を使用禁止にする
s.nowNo=i;//今いる線分
pQ.push(s);
s.r=1;//逆の端から出発する
pQ.push(s);
ansPerm|=(1<<i);//答えの組み合わせを立てておく
}
double ansLen=0;
for(int i=0;i<n;i++){
ansLen+=sqrt(pow(xs[0][i]-xs[1][i],2)+pow(ys[0][i]-ys[1][i],2));
}
while(!pQ.empty()){
s=pQ.top();
pQ.pop();
if(s.perm==ansPerm)break;//答え到達
len1=memo[s.r][s.nowNo][s.perm];
if(first[s.r][s.nowNo][s.perm]==false&&len1<s.len)continue;//これより短い折れ線があった
memo[s.r][s.nowNo][s.perm]=s.len;
first[s.r][s.nowNo][s.perm]=false;
for(int i=0;i<n;i++){
if((s.perm&(1<<i))!=0)continue;//この線分は接続済み
nextS.perm=(s.perm|(1<<i));
nextS.nowNo=i;
nextS.len=s.len+lensMemo[s.r][0][s.nowNo][i];//端点0と線分でつなげる
nextS.r=1;//次は端点1からスタート
len1=memo[nextS.r][nextS.nowNo][nextS.perm];
if(first[nextS.r][nextS.nowNo][nextS.perm]==true||len1>nextS.len){//より短いルートか初めて
memo[nextS.r][nextS.nowNo][nextS.perm]=nextS.len;
first[nextS.r][nextS.nowNo][nextS.perm]=false;
pQ.push(nextS);
}
nextS.len=s.len+lensMemo[s.r][1][s.nowNo][i];//端点1と線分でつなげる
nextS.r=0;//次は端点0から出発
len1=memo[nextS.r][nextS.nowNo][nextS.perm];
if(first[nextS.r][nextS.nowNo][nextS.perm]==true||(len1>nextS.len)){//より短いルートか初めてだった
memo[nextS.r][nextS.nowNo][nextS.perm]=nextS.len;
first[nextS.r][nextS.nowNo][nextS.perm]=false;
pQ.push(nextS);
}
}
}
printf("Case %d: %.5lf\n",i,s.len+ansLen);
}
int main(){
int n,i=1;
while(1){
scanf("%d",&n);
if(n==0)break;
setData(n,i);
i++;
}
}
タイムが遅かったので高速化してみました。
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#include<bitset>
double memo[2][14][2<<14];//[次の線分の出発点][最後に結んだ線分][結んだ線のビット表現]
bool first[2][14][2<<14];//最初
void setData(int n,int i){
double xs[2][15],ys[2][15];
memset(first,true,sizeof(first));
for(int i=0;i<n;i++){
scanf("%lf %lf %lf %lf",&xs[0][i],&ys[0][i],&xs[1][i],&ys[1][i]);
}
//printf("scanOK");
double lensMemo[2][2][15][15],len1;//線分で結ぶ時の距離のメモ
for(int l1=0;l1<n;l1++){
for(int l2=0;l2<n;l2++){
if(l1==l2)continue;//同じ線分は結ばない
for(int r1=0;r1<2;r1++){
for(int r2=0;r2<2;r2++){
len1=sqrt(pow(xs[r1][l1]-xs[r2][l2],2)+pow(ys[r1][l1]-ys[r2][l2],2));
lensMemo[r1][r2][l1][l2]=len1;
}
}
}
}
//引かれてる線分の長さを集計しておく
double ansLen=0;
int ansPerm=0;//全部の線分を繋げた後の組み合わせ
for(int i=0;i<n;i++){
ansLen+=sqrt(pow(xs[0][i]-xs[1][i],2)+pow(ys[0][i]-ys[1][i],2));
ansPerm|=(1<<i);
memo[0][i][1<<i]=memo[1][i][1<<i]=0;//スタート地点の線分を設定
}
int perm1,nextPerm;
std::vector<int> perm[16];//結んだ線分の組み合わせ
std::bitset<16> b;
for(int i=1;i<(1<<n);i++){
b=i;
perm[b.count()].push_back(i);
}
double nextLen,ans2=1000000000;;
for(int i=1;i<n;i++){
for(int j=0;j<perm[i].size();j++){
perm1=perm[i][j];//
for(int p1=0;p1<n;p1++){
if((perm1&(1<<p1))==0)continue;//この組み合わせは駄目
for(int p2=0;p2<n;p2++){
//線分ｐ１からｐ２へと繋げる
if((perm1&(1<<p2))!=0)continue;//これはもう繋げている
if(p1==p2)continue;//あり得ないが念のため
nextPerm=(perm1|(1<<p2));
for(int r1=0;r1<2;r1++){
for(int r2=0;r2<2;r2++){
nextLen=lensMemo[(r1+1)&1][r2][p1][p2]+memo[r1][p1][perm1];
//printf("%lf>",nextLen);
if(first[r2][p2][nextPerm]==true){
first[r2][p2][nextPerm]=false;
memo[r2][p2][nextPerm]=nextLen;
}else if(memo[r2][p2][nextPerm]>nextLen){
memo[r2][p2][nextPerm]=nextLen;
}
if(nextPerm==ansPerm&&ans2>nextLen)ans2=nextLen;
}
}
}
}
}
}
printf("Case %d: %.5lf\n",i,ansLen+ans2);
}
int main(){
int n,i=1;
while(1){
scanf("%d",&n);
if(n==0)break;
setData(n,i);
i++;
}
}
2118 Oil Company
解法
この問題は普通に一段ずつ動的計画法で対処しようとすると組み合わせ爆発に巻き込まれて最後は計算量の泥沼に落ち込みます。
2行目に設置するしないを01であらわし例えば一つの組み合わせとして01001010と決まった場合、1行目は1011010の1の部分に掘削機を設置できます。
２行目が決まった場合、１行目は２行目のビット反転かつそれのサブセットかつ１行目の有効な設置方法この条件を満たすサブセットのうち最も高い掘削量を２行目に対する対として足しこみます。
なぜなら２行目が決まった場合、一行目をどう取ろうが３行目や４行目に影響を与えません。
よって２行目が決まった場合一行目は最も貪欲に決めればいいことになります。
ある行を貪欲に決めるにはその行での掘削機の設置の組AとBがありAがBのサブセットでAのほうが手前の行も考慮に入れた場合掘削量が多い場合Aの掘削量でBの掘削量を上書きしこれを全てのセットで行います。
そうすると簡単に貪欲に決めることが出来ます。
次は３行目で同じことを２行目にたいしてもとめます。
これを一段ずつ繰り返せば最終的に最後の段で最大値がもとまり計算量は最悪４億回となります。
この問題は難しいため私の場合、ちょっと複雑な処理となりました。
これしか考えつかず今のところ合格できただけで満足してしまいますが、１位の方のコードを見ると恐ろしく早いシンプルな解法があるようです。
後日再挑戦するかもしれません。
#include<stdio.h>
#include<vector>
#include<bitset>
#include<algorithm>
#include<string.h>
std::vector<int> okPerm;//ある行に設置可能な全ての組み合わせ
int w,h;
int memo[2][1<<20];
void createOkPerm(int col,bool bildOK,int perm){
if(col==w){
okPerm.push_back(perm);
}else{
if(bildOK==true)createOkPerm(col+1,false,perm|(1<<col));
createOkPerm(col+1,true,perm);
}
}
void calc(int t1){
scanf("%d %d",&w,&h);
okPerm.clear();
createOkPerm(0,true,0);//ある行に設置可能な掘削機の全ての組を求める
//printf("%d\n",okPerm.size());
std::bitset<21> b;
std::vector<int> rowPerm[21];
for(int i=0;i<(1<<w);i++){
b=i;
rowPerm[b.count()].push_back(i);//サブセットをソートして用意する
}
int map[21],p1,p2,p3,sum,mask=0,ans=0;
for(int c=0;c<w;c++)mask|=(1<<c);
memset(memo,0,sizeof(memo));
for(int r=0;r<h;r++){
//一行ずつ動的計画法を試す
for(int c=0;c<w;c++)scanf("%d",&map[c]);
int now =r&1;
int old=(r+1)&1;
memset(memo[now],0,sizeof(memo[now]));
for(int i=0;i<okPerm.size();i++){
sum=0;
p1=okPerm[i];
for(int c=0;c<w;c++){
sum+=map[c]*((p1&(1<<c))!=0);//この行の可能な数と足す
}
p2=((~p1)&mask);//ビット反転してマスクを取ることでサブセットの最大を求める
memo[now][p1]=sum+memo[old][p2];//上の行の最大と足す
if(r==h-1)ans=std::max(ans,memo[now][p1]);
}
for(int i=0;i<w;i++){
for(int j=0;j<rowPerm[i].size();j++){
p1=rowPerm[i][j];
for(int k=0;k<w;k++){
p2=(p1|(1<<k));//サブセットの方が大きいなら上書きする
memo[now][p2]=std::max(memo[now][p2],memo[now][p1]);
}
}
}
}
printf("Case %d: %d\n",t1,ans);
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
calc(i);
}
}
最終更新：2012年07月29日 18:08
