「AOJ2111～2120」の編集履歴（バックアップ）一覧に戻る
AOJ2111～2120 - (2012/07/27 (金) 01:15:58) のソース
*2117 Connect Line Segments
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2117
平面上に散らばってる線分を繋げて一本の長い折れ線を作るとき、最小の長さの折れ線を作った時の長さを答えよという問題。
プログラミングコンテストの過去問を1000問解いたって学歴、職歴、実績の三無い人間の私では世間から何の評価もされません。
プロコンの問題を解くことは私にとって単なる趣味でしかないのです。
使い捨て労働で仕事を探しながらこの趣味を完遂するのだけが楽しみです。
何かアプリでも作って売れたら世間からの評価も変わるかもしれないのでその可能性にかけるくらいです。
どうでもい話だが金儲けといえば小説である。
昔このサイトは小説サイトでした。
最初のころは小学生よりひどい設定集を書きこれはサイトの表の方にあり探しやすいところにある。
ある程度慣れてきてそこそこのものを作っていた時期もあったのだが、これらはサイトの奥の方見つかりにくい位置に配置してしまっていた。
それでもそこそこのアクセス数がありアップするたびに1ページ頭4日で1000～3000アクセス、その後ぷっつりアクセス数が激減というそれなりに私の作品を楽しみにしている固定客がついたサイトでした。
これがご近所さんに盗作されてたらしいんだよね。
夏だから窓全開隣近所の会話が入ってくることもあるわけですよ。
「盗作がばれたなら偽物の堀江に謝らせればいいんですよ」
「編集担当なんて言ったと思います？ネットからの盗みは盗みになりません。盗みがばれたんならミックスすればいいんですよ」
録音し損ねたので証拠能力は無いけどこんな会話が隣家から飛び込んできた日もあったわけです。
まあ聞きに行ってもしらばくれられただけですけど。
堀江って私か私の家族でもう一人創作してるのがいるので我が家のことだと思うんだけどね。
私か私の家族の偽物がやってもない罪で謝罪していると思うと何とも悔しい話です。
創作で稼いでみたいなあとは思いますが、盗作されるが全部は書ききってない中途半端な設定や作りかけの残骸が多いので小説や設定で金儲けしたことは無いんだよね。
お隣さんはどうもクラッキングの手口にたけてるみたいなんだけど証拠がないんだよな。
堀江伸一
住所 兵庫県加古川市加古川町南備後79-16
解法
さてこの問題自分なりに考えた解法は2種類で以下の通りです。
コード実行速度が悪いコードとコード実行速度2位のコードです。
単純に深さ優先探索を行うと線分が10本を超えたあたりで10！*2^10となり計算量が限界を超えます。
13や14などは枝刈で挑むのは論外です。
分岐が不可能なのでプリム法も使えません。
よって動的計画法を使わなくてはいけません。
動的計画法は、memo[次に両端のどちらの点から新しい線分を伸ばすか][これから新しく線分を伸ばす場所はどの線か][今までつなげた線分のリスト]=ここまでの折れ線の最小の長さ。
で動的計画法を適用していくだけの簡単な問題です。
この問題私はあまりいい解法ではなかったようでコード実行速度が出ませんでした。
私の場合スタート時全ての線分を折れ線の開始候補としていますがもしかしたらどこか一本の線分からスタートしていくだけでいいのかもしれません。
コード実行速度2位の方は1つの線分を結んだ、2つの線分を結んだ、、、ｎ個の線分を結んだまでが綺麗な順序で無駄なく実行されるようにソートしてから動的計画法を適用して解いています。
毎回思うが一位の壁は厚い、ランキング上位に入れても一位を抜けることはめったにない、一位手ごわすぎ。
2位のコード実は動的計画法のｎ/２本目まで線分を結んだところで残り半分は実は計算する必要はありません。
結んでない線分の補集合を取ってその折れ線との結びつきを試せば真中で計算が終わります。
しかしこれでコード実行速度1位を取れますがコードが少し膨らみますし2倍しか早くならないのでたかが練習問題でそこまでして一位を取る必要もないかなと考えます。
この問題を解いた時点でカンニングして解いたプロコンの過去問題は480問中31問この比率をこれからどんどん下げていくのが楽しみです。
#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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2118
マス目に区切られたマップのオイル埋蔵量が与えられる、オイル掘削機を設置すればそのマスのオイルを全て回収できる。
事故時の連鎖爆発を防ぐために掘削機は隣り合ったマスにはおけないとする。
この時の最大の掘削量を求めよ。
仮説
この問題は普通に一段ずつ動的計画法で対処しようとすると組み合わせ爆発に巻き込まれて最後は泥沼に落ち込みます。
2行目に設置するしないを01であらわし例えば一つの組み合わせとして01001010と決まった場合、1行目は1011010の1の部分に掘削機を設置できます。
一行目の設置は3行目には影響を与えません。
すると一行目は出来る限り貪欲に設置すればいいことが判明します。
貪欲に設置した場合でも色々な方法がありますが、ある組み合わせのサブセット10100000は10100100のサブセットとなりこれを考慮する必要はありません。
サブセットが起こらないように集合を作り出すことが出来ればこの問題はギリギリ解けるはずです。
3行目を考える場合は1行目の一番貪欲な結果を2行目の各組み合わせに足し算してから2行目を一行目と同様に考えればかなり計算量が落ちるはずです。
もっと賢い方法があるかもしれませんが私が今のところ思いついたのはこれが一番ベターなやり方です。
