SRM629-630 Div1E

30問こえましたね

 ・SRM629 Div1E RectangleCovering

大きさH×Wの穴がある.n個の板があり,i番目の板の大きさはh[i]×w[i]である.なるべくすくない枚数の板で穴を完全に覆いたい.ただし板の頂点は全て穴の外側(境界を含まない)になければならず,板同士は重なってもよい.最小何枚で覆えるか?という問題.

まず板の頂点が穴の外側にないといけないことから,板を横に並べるのと縦に並べるのを両方用いた方が良いことはなく,片方だけに固定していいことがわかる.板を横に並べるときは,穴を縦にわたせるもののうち横幅の大きいものから順に並べていくのが最適.綺麗にプログラムを書くのにやや工夫が必要?(適当にコピペして通すアをした)

ソースコード

class RectangleCovering {
    public:
    int minimumNumber(int holeH, int holeW, vector<int> boardH, vector<int> boardW) {
        int N=boardH.size();
        vector<int> vs;
        for(int i=0;i<N;i++) {
            int h=boardH[i];
            int w=boardW[i];
            if(holeH<h && holeH<w) vs.push_back(max(h,w));
            else if(holeH<h) vs.push_back(w);
            else if(holeH<w) vs.push_back(h);
        }
        sort(vs.begin(),vs.end());
        int sum=0;
        int pos=vs.size()-1;
        while(pos>=0 && sum+vs[pos]<holeW) {
            sum+=vs[pos];
            pos--;
        }
        int ans=1<<30;
        if(pos>=0) ans=min(ans,(int)vs.size()-pos);
        vs.clear();
         for(int i=0;i<N;i++) {
            int h=boardH[i];
            int w=boardW[i];
            if(holeW<h && holeW<w) vs.push_back(max(h,w));
            else if(holeW<h) vs.push_back(w);
            else if(holeW<w) vs.push_back(h);
        }
        sort(vs.begin(),vs.end());
        sum=0;
        pos=vs.size()-1;
        while(pos>=0 && sum+vs[pos]<holeH) {
            sum+=vs[pos];
            pos--;
        }
        if(pos>=0) ans=min(ans,(int)vs.size()-pos);
        if(ans==1<<30) return -1;
        return ans;
    }
};

・SRM630 Div1E Egalitarianism3

n頂点の木がある.任意の二頂点間の距離が等しいような頂点の集合のサイズの最大値はいくつか?という問題.

わからなくて人のブログを見た.n≦2のときは明らかに答えはn.以下n≧3とする.答えが3以上になるのはどういう場合だろうか.これは,木であることを踏まえると,ある頂点から長さが同じパスが3本以上生えているようなときだとわかる.よって各頂点を根に固定してみて,根から各長さのパスが何本生えているかを数えればよい.

ソースコード

int d[50][50];
vector<int> G[50];
int cnt[50001];
class Egalitarianism3 {
    public:
    int maxCities(int n, vector<int> a, vector<int> b, vector<int> len) {
        if(n<=2) return n;
        fill((int*)d,(int*)(d+50),1<<25);
        for(int i=0;i<n;i++) d[i][i]=0;
        for(int i=0;i<n-1;i++) {
            a[i]--;
            b[i]--;
            d[a[i]][b[i]]=d[b[i]][a[i]]=len[i];
            G[a[i]].push_back(b[i]);
            G[b[i]].push_back(a[i]);
        }
        for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
        int ans=2;
        for(int i=0;i<n;i++) {
            for(int j:G[i]) {
                set<int> S;
                for(int k=0;k<n;k++) {
                    if(d[i][j]+d[j][k]==d[i][k]) S.insert(d[i][k]);
                }
                for(int e:S) cnt[e]++;
            }
            for(int i=0;i<=50000;i++) ans=max(ans,cnt[i]);
            memset(cnt,0,sizeof(cnt));
        }
        return ans;
    }
};