*問116 Rectangular Searching http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0116 図の中に描ける最大の面積を持つ長方形を探す問題 解法 私はBigO(n^3)のコードしか考え付きませんでした。 osa_kさんのコードがシンプルながらBigO(n^2)なのでAOJで見ておいてください。 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=496648&tab=2# 私もstackの代わりにmapをつかった解法であと一歩のところまで到達していたのであと一歩という感じでした。 mapから消すのは遅いけどstackは早い、その差が出ました。 *問117 A reward for a Carpenter http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0117 大工が柱を買い付けて戻ってくるまでのコストを最小にする問題。 解法 点の数が少ないグラフなので計算量の多い手抜きコードでも何の問題もありません。 点の数が増えたらダイクストラ法などを使います。 #include<stdio.h> #include<string.h> int G[21][21]; int calc(int s,int e,int n){ int cost[21]; memset(cost,-1,sizeof(cost)); cost[s]=0; while(1){ bool isUpDate=false; for(int i=1;i<=n;i++){ if(cost[i]==-1)continue; for(int j=1;j<=n;j++){ if(G[i][j]==-1)continue; if(cost[j]==-1 || cost[j]>cost[i]+G[i][j]){ cost[j]=cost[i]+G[i][j]; isUpDate=true; } } } if(isUpDate==false)break; } return cost[e]; } int main(){ int n,m,a,b,c,d; scanf("%d %d",&n,&m); memset(G,-1,sizeof(G)); while(m--){ scanf("%d,%d,%d,%d",&a,&b,&c,&d); G[a][b]=c; G[b][a]=d; } int x1,x2,y1,y2; scanf("%d,%d,%d,%d",&x1,&x2,&y1,&y2); printf("%d\n",y1-y2-calc(x1,x2,n)-calc(x2,x1,n)); } *問118 Property Distribution http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0118 この問題、数十万行*数十万列のデータになってもコードがBigO(行数*列数*log(列数,2))と列数の要素数の定数倍のメモリ使用量で動くコードを試行錯誤中。 今のところ人様に見せれるコードは書けてないのでコードは誰にも見せてない。
