Hatena::Grouptopcoder

kitayutaのTopCoderの何か

|

2011-06-04

TopCoder SRM 507 Div1

22:45

結果

242.23 Failed Opened +50*0 -25*0 Total:242.23 1206→1330

Highestきた

250 CubeStickers

同じ色でいいのはサイコロの向かい合う面だけ。色ごとにその個数を計算して、2個以上あった場合には2個(向かい合う面の二つ)しか使えず、1個の場合は普通に使える。合計で6個以上あった場合にはすべての面が塗れる。

色ごとの個数の計算はmapを使うのが楽。

//include等省略
class CubeStickers {
    public:
        string isPossible(vector <string> sticker) {
            map<string,int> ints;
            for(int i=0;i<sticker.size();i++){
                ints[sticker[i]]++;
            }
            int sum=0;
            for(map<string,int>::iterator it=ints.begin();it!=ints.end();it++){
                sum+=min(it->second,2);
            }
            if(sum>=6) return "YES";
            else return "NO";
        }
};

500 CubePacking

嘘解法

全体の体積を V=Ns + L*L*L*Nb とする。

とりあえずLxLの立方体は縦に積み上げて、あとの1x1の立方体が入るように、

x>=L ∧ y>=L ∧ z>= L*Nb ∧ x*y*z>=V ∧ Vが最小

となるような求める立方体の三辺x,y,zを探索し、答えをVとする。

これには Ns=18, Nb=4, L=2 などの反例が見つかる。(正しい答えは50だが、この解法で計算すると52になる)

not嘘解法

省略

1000 CubeBuilding

よんでないー

Challenge Phase

ひま

2011-05-04

TopCoder SRM 505 Div2

20:00

結果

240.15 251.78 Opened +50x1 -25x2 合計: 491.93pt 1132 -> 1206

kitayutaになった!

250 SentenceCapitalizerInator

やるだけ

//include等省略
class SentenceCapitalizerInator {
    public:
        string fixCaps(string para) {
            para[0]=toupper(para[0]);
            for(int i=0;i<para.size();i++){
                if(para[i]=='.'){
                    if(i+2<para.size()){
                        para[i+2]=toupper(para[i+2]);
                    }
                }
            }
            return para;
        }
};

500 PerfectSequences

それぞれの項について、何を代入すると(seqの総積)=(seqの総和)になるかを二分探索する方針。いくつかの例外を除いて、項に代入する値が小さくなるほど(seqの総積)-(seqの総和)は小さくなるので、これを利用する。コーナーケースが大量にあるので注意する。これがSystemTestを通過したのは運が良かった。

工夫(?)した点として、

  • 総和はLONG_LONG_MAX未満となることが明らかだから、総積がLONG_LONG_MAXを超えるとしても、getprodはLONG_LONG_MAXを返せば総和と総積の大小関係は変わらない。
  • 二分探索はいろいろ考えるのが面倒くさいので定数回(ここでは100回)行った。

class PerfectSequences {
    public:
        ll getsum(vector<int> seq){
            ll ret=0;
            for(int i=0;i<seq.size();i++){
                ret+=seq[i];
            }
            return ret;
        }
        ll getprod(vector<int> seq){
            ll ret=1;
            for(int i=0;i<seq.size();i++){
                if(seq[i]==0) ret=0;
                else if(LONG_LONG_MAX/(ll)seq[i]<ret) ret=LONG_LONG_MAX;
                else ret*=(ll)seq[i];
            }
            return ret;
        }
        string fixIt(vector <int> seq) {
            if(seq.size()==1) return "Yes";
            else{
                for(int i=0;i<seq.size();i++){
                    bool isallzero=true;
                    bool isanyzero=false;
                    for(int j=0;j<seq.size();j++){
                        if(j!=i&&seq[j]!=0) isallzero=false;
                        if(j!=i&&seq[j]==0) isanyzero=true;
                    }
                    if(isallzero){
                        if(seq[i]!=0) return "Yes";
                    }else if(!isanyzero){
                        int moto=seq[i];
                        seq[i]=1;
                        if(moto!=1&&getsum(seq)==getprod(seq)) return "Yes";
                        else{
                            ll left=2,right=1000000000;
                            for(int j=0;j<100;j++){
                                ll mid=(left+right)/2;
                                seq[i]=mid;
                                ll sum=getsum(seq),prod=getprod(seq);
                                if(sum<=prod){
                                    right=mid;
                                }else if(sum>prod){
                                    left=mid;
                                }
                            }
                            seq[i]=left;
                            if(moto!=left&&getsum(seq)==getprod(seq)) return "Yes";
                            seq[i]=right;
                            if(moto!=right&&getsum(seq)==getprod(seq)) return "Yes";
                        }
                        seq[i]=moto;
                    }
                }
            }
            return "No";
        }
};

値を変化させる項を変数として一次方程式を立てて解く方法もあることに後で気付いたが、それもそれでなんだかめんどくさそう。

900 RectangleArea

SRM中は怪しいアルゴリズムを考えていたけど時間内に書き終わらなかったし、よく考えてみるとExampleも通らない。

Challenge Phase

プラマイゼロ。もったいない

2011-04-20

TopCoder SRM 503 Div2

22:31

ひさしぶりのSRM

結果

243.53 244.64 x 538.17pt 1082->1132

250 ToastXRaspberry

割り算するだけ.割り切れるときと割り切れないときの場合分けをするか,ceilを使うかしないと落ちる.

//include等省略
class ToastXRaspberry {
public:
    int apply(int upper_limit, int layer_count) {
        if(layer_count%upper_limit==0){
            return layer_count/upper_limit;
        }else return layer_count/upper_limit+1;
    } 
};

500 ToastXToast

  • 問題文難しい…
  • DPとかかな.でもDP分からない.
  • Greedyっぽい何かを書こうとするが明らかに判例がある
  • あ、これ最大でも二種類…?
  • たぶんそれでよさそう

まずundertoastedとovertoastedをソートする.

ここでundertoastedの最大値がovertoastedの最小値より小さければ,明らかに一種類でよい.

undertoastedの最小値がovertoastedの最小値より大きい場合,undertoastedの最小値に対応するovertoastedの要素は存在しないから,条件を満たすトーストの種類は存在しない.undertoastedの最大値がovertoastedの最大値より大きい場合も同様.

その他の場合は二種類で良い.理由を次に示す:

undertoastedとovertoastedの要素を時系列順に並べ,undertoastedの要素をO,overtoastedの要素をXとすると,

{O…O}{X…X}

というユニットが二個以上ならぶはず.つまり,

{O…O:1}{X…X:1}{O…O:2}{X…X:2}{O…O:3}{X…X:3} … {O…O:n-1}{X…X:n-1}{O…O:n}{X…X:n}

のようになるが,これを

{O…O:1}{X…X:1}        {X…X:2}        {X…X:3} …           {X…X:n-1}        
                {O…O:2}        {O…O:3}         … {O…O:n-1}          {O…O:n}{X…X:n}

という風に分割することができる.

//include等省略
class ToastXToast {
public:
    int bake(vector <int> under, vector <int> over) {
        sort(under.begin(),under.end());
        sort(over.begin(),over.end());
        if(under[0]>over[0]||under[under.size()-1]>over[over.size()-1]) return -1;
        else if(under[under.size()-1]<over[0]) return 1;
        else return 2;
    }
};

900 KingdomXCitiesandVillagesAnother

最小全域木を求めて,City間にあるパスの分だけ答えから引けばいいと思う.

SRM中には,最小全域木な気もしたが,なぜか最小全域木で解くこの方法が思いつかなかった.

実装したアルゴリズム:

CityとVillageを合わせたそれぞれの町の間の距離を小さい順にpriority_queueに入れておく.小さいものから取り出していき,もし両方がCityにつながってるもしくはCityならば廃棄する.両方ともただのVillageだった場合,後で入れ直す.片方がCityもしくはCityにつながっている場合は,二つの町の間の距離を答えに足し,つながっていない方をつながっている状態に変更する.これをくり返して,合計値を返す.

適当解法なので合ってる気があまりしなかったが,解法自体は問題なくて,intのオーバーフローで落ちた.もったいない.

//include等省略
typedef pair<int,int> P;

class KingdomXCitiesandVillagesAnother {
    public:
        double determineLength(vector <int> cityX, vector <int> cityY, vector <int> villageX, vector <int> villageY) {
            vector<P> mas(cityX.size()+villageX.size());
            vector<bool> iscity(cityX.size()+villageX.size(),false);
            for(int i=0;i<cityX.size();i++){
                mas[i]=make_pair(cityX[i],cityY[i]);
                iscity[i]=true;
            }
            for(int i=0;i<villageX.size();i++){
                mas[cityX.size()+i]=make_pair(villageX[i],villageY[i]);
            }
            priority_queue<pair<double,pair<int,int> > ,vector<pair<double,pair<int,int> > >, greater<pair<double,pair<int,int> > > > dists;
            for(int i=0;i<mas.size();i++){
                for(int j=i+1;j<mas.size();j++){
                    dists.push(make_pair((mas[i].first-mas[j].first)*(mas[i].first-mas[j].first)+(mas[i].second-mas[j].second)*(mas[i].second-mas[j].second),make_pair(i,j)));
                }
            }
            double sum=0;
            while(!dists.empty()){
                vector<pair<double,pair<int,int> > > amari;
                while(!dists.empty()){
                    pair<double,pair<int,int> > p=dists.top();
                    dists.pop();
                    P mp=p.second;
                    if(iscity[mp.first]&&iscity[mp.second]){
                    }else if(iscity[mp.first]||iscity[mp.second]){
                        sum+=sqrt(p.first);
                        iscity[mp.first]=iscity[mp.second]=true;
                        break;
                    }else{
                        amari.push_back(p);
                    }
                }
                for(int i=0;i<amari.size();i++){
                    dists.push(amari[i]);
                }
            }
            return sum;
        }
};

次のように修正すれば通る.

typedef pair<int,int> P;

class KingdomXCitiesandVillagesAnother {
    public:
        double determineLength(vector <int> cityX, vector <int> cityY, vector <int> villageX, vector <int> villageY) {
            vector<P> mas(cityX.size()+villageX.size());
            vector<bool> iscity(cityX.size()+villageX.size(),false);
            for(int i=0;i<cityX.size();i++){
                mas[i]=make_pair(cityX[i],cityY[i]);
                iscity[i]=true;
            }
            for(int i=0;i<villageX.size();i++){
                mas[cityX.size()+i]=make_pair(villageX[i],villageY[i]);
            }
            priority_queue<pair<double,pair<int,int> > ,vector<pair<double,pair<int,int> > >, greater<pair<double,pair<int,int> > > > dists;
            for(int i=0;i<mas.size();i++){
                for(int j=i+1;j<mas.size();j++){
                    dists.push(make_pair((mas[i].first-mas[j].first+0.0)*(mas[i].first-mas[j].first)+(mas[i].second-mas[j].second+0.0)*(mas[i].second-mas[j].second),make_pair(i,j)));  //修正点
                }
            }
            double sum=0;
            while(!dists.empty()){
                vector<pair<double,pair<int,int> > > amari;
                while(!dists.empty()){
                    pair<double,pair<int,int> > p=dists.top();
                    dists.pop();
                    P mp=p.second;
                    if(iscity[mp.first]&&iscity[mp.second]){
                    }else if(iscity[mp.first]||iscity[mp.second]){
                        sum+=sqrt(p.first);
                        iscity[mp.first]=iscity[mp.second]=true;
                        break;
                    }else{
                        amari.push_back(p);
                    }
                }
                for(int i=0;i<amari.size();i++){
                    dists.push(amari[i]);
                }
            }
            return sum;
        }
};

Challenge Phase

250で割り切れるときに1を足していないコードがあったのでありがたく撃墜.はじめて.

2011-03-19

TopCoder SRM 500 Div2

01:04

Registerできなかったわろす

2011-02-11

TopCoder SRM 497 Div2

15:02

結果

106.84 - - 0 106.84pt 1160 -> 1081

明後日はJOIです。まずい。

250 Filtering

よく分からないがフィルターを作るらしい。フィルターはAからBの間のものを通さないという(A,B)-filterというものしか作れない。ここで、通さなきゃいけないものと通したらいけないものの配列が与えられて、(A,B)-filterを作って返す問題。

やり方があたま悪くて遅い。あとresubmitしてしまった。

//include等省略

class Filtering {
    public:
        vector <int> designFilter(vector <int> sizes, string outcome) {
            vector<pair<int,char> > tups(sizes.size());
            for(int i=0;i<tups.size();i++){
                tups[i]=make_pair(sizes[i],outcome[i]);
            }
            sort(tups.begin(),tups.end());
            int st=-1,en=-1;
            bool isca=false;
            for(int i=0;i<tups.size();i++){
                if(tups[i].second=='A')isca=true;
            }
            if(!isca){
                for(int i=1;i<=100;i++){
                    for(int j=0;j<tups.size();j++){
                        if(tups[j].first!=i){
                            vector<int> ret;
                            ret.push_back(sizes[i]);
                            ret.push_back(sizes[i]);
                            return ret;
                        }
                    }
                }
                return vector<int>();
            }
            bool is=false,able=true,isend=false;
            for(int i=0;i<tups.size();i++){
                if(is){
                    if(tups[i].second=='R'){
                        en=i-1;
                        isend=true;
                        is=false;
                    }
                }else if(tups[i].second=='A'){
                    if(isend){
                        able=false;
                        is=false;
                        break;
                    }else{
                        st=i;
                        is=true;
                    }
                }
            }
            if(is)en=tups.size()-1;
            if(able){
                vector<int> ret;
                ret.push_back(tups[st].first);
                ret.push_back(tups[en].first);
                return ret;
            }else{
                return vector<int>();
            }
        }
};

500 PermutationSignature

250に時間を掛けすぎて焦ってしんだ。終わったあとPracticeでAC

usedは1からnまでの値を使ったかどうかを管理している。rankは値の大小を決めるための配列。間違った解法で解いてた時に書いたものを流用したので冗長。

求める順列のk番目を求めることを考える。この時、k番目より前の要素はすでに決まっているものとする。k番目より後で、自分より確実に小さいものの個数をm個とすると、k番目の要素は、1からnまでの整数のうちでまだ使っていないもののうち小さい方からm+1番目。

みたいな感じの解法。Greedy?

//include等省略

class PermutationSignature {
    public:
        vector <int> reconstruct(string signature) {
            vector<bool> used(signature.size()+2,false);
            used[0]=true;
            vector<int> rank(signature.size()+1);
            int now=0;
            rank[0]=now;
            for(int i=1;i<=signature.size();i++){
                if(signature[i-1]=='I'){
                    rank[i]=++now;
                }else{
                    rank[i]=--now;
                }
            }
            vector<int> ret(signature.size()+1);
            for(int i=0;i<ret.size();i++){
                int rigs=0;
                if(i+1<ret.size()&&rank[i]>rank[i+1]){
                    rigs++;
                    for(int j=i+1;j+1<rank.size();j++){
                        if(rank[j]>=rank[j+1])rigs++;
                        else break;
                    }
                }
                for(int j=0;j<used.size();j++){
                    if(!used[j]){
                        if(rigs>0)rigs--;
                        else{
                            ret[i]=j;
                            used[j]=true;
                            break;
                        }
                    }
                }
            }
            return ret;
        }
};

Challenge Phase

「なんだそれは!?でたらめ言うんじゃないよ!!!そんな物この世にないだろ!」

|