Hatena::Grouptopcoder

kitayutaのTopCoderの何か

2011-11-13

TopCoder SRM 523 Div1

18:05

結果

<Challenge Succeeded> <215.83> <Unopened> +50*1 -25*1 Total: 240.83pt 1294→1396

Highest更新らしい!!

250 CountingSeries

簡単…なはずが、コーナーケースに当たって落ちる。こわい。

提出したコード(落ちる):

//include等省略
class CountingSeries {
    public:
        long long countThem(long long a, long long b, long long c, long long d, long long upperBound) {
            ll cnt=(upperBound-a)/b+1;
            while(c<=upperBound){
                if((c-a)%b==0&&(c-a)/b>=0);
                else cnt++;
                if(d==1) break;
                c*=d;
            }
            return cnt;
        }
};

落ちた原因は、upperBound<aの時に適切な処理をしていなかった点。

//include等省略
class CountingSeries {
    public:
        long long countThem(long long a, long long b, long long c, long long d, long long upperBound) {
            ll cnt;
            if(upperBound-a>=0) cnt=(upperBound-a)/b+1;  //修正点
            else cnt=0;
            while(c<=upperBound){
                if((c-a)%b==0&&(c-a)/b>=0);
                else cnt++;
                if(d==1) break;
                c*=d;
            }
            return cnt;
        }
};

500 BricksN

DP(メモ化再帰)をした。dp[一番下のブロックの幅][一番下のブロックの高さ]として、求める答えはdp[w][1]。これを求める過程として、ある長さの連続するブロックは何通りに敷き詰められるかをDPして求めておいたりする(dp2)。

オーバーフローに注意するべきかもしれない。

DPに慣れてきていい傾向。あと初めてMedium通した。

//include等省略
const ll MOD = 1000000007;
ll dp[51][51];
ll dp2[51];
ll solve(int wid,int hei,int k,int h){
    if(wid<1 || hei>h) return 1;
    if(dp[wid][hei]==-1){
        ll ret=0;
        for(int i=0;i<=wid;i++){
            ret+=(((dp2[i]*solve(i,hei+1,k,h))%MOD)*solve(wid-i-1,hei,k,h))%MOD;
            ret%=MOD;
        }
        dp[wid][hei]=ret;
    }
    return dp[wid][hei];
}
class BricksN {
    public:
        int countStructures(int w, int h, int k) {
            dp2[0]=1;
            for(int i=1;i<=w;i++){
                dp2[i]=0;
                for(int j=1;j<=min(i,k);j++){
                    dp2[i]+=dp2[i-j];
                    dp2[i]%=MOD;
                }
            }
            for(int i=1;i<=w;i++){
                for(int j=1;j<=h;j++){
                    dp[i][j]=-1;
                }
            }
            return solve(w,1,k,h);
        }
};

Challenge Phase

  • 上の500のコードにおける "ret+=(dp2[i]*solve(i,hei+1,k,h))%MOD)*solve(wid-i-1,hei,k,h))%MOD;" を "ret+=(dp2[i]*solve(i,hei+1,k,h)*solve(wid-i-1,hei,k,h))%MOD;" とかやって明らかにオーバーフローしてるコードを落とす。
  • 250が落とされる。
  • 250の落とされ方をなんとなく把握して、適当に人のをchallengeしたらミス。焦ってはいけない…

2011-08-31

TopCoder SRM 516 Div2

14:40

結果

235.95 Failed Failed +50*0 -25*0 Total:235.95 1192→1148(-44)

三回連続で減少している。ひどい。

250 NetworkXZeroOne

偶数番目にxが、もしくは奇数番目にoがある場合には、oxoxoxox...となり、そうでない場合はxoxoxoxo...となる。

//include等は省略
class NetworkXZeroOne {
    public:
        string reconstruct(string message) {
            int d;
            char a,b;
            for(int i=0;i<message.size();i++){
                if(message[i]=='o'){
                    if(i%2==0){
                        a='o';
                        b='x';
                    }else{
                        a='x';
                        b='o';
                    }
                }
                else if(message[i]=='x'){
                    if(i%2==0){
                        a='x';
                        b='o';
                    }else{
                        a='o';
                        b='x';
                    }
                }
            }
            for(int i=0;i<message.size();i++){
                if(i%2==0) message[i]=a;
                else message[i]=b;
            }
            return message;
        }
};

500 NetworkXOneTimePad

単純に全探索っぽいことをしたらTLEしてしまった。

提出したコードは

//include等は省略
class NetworkXOneTimePad {
    public:
        string _xor(string a,string b){
            string ret;
            for(int i=0;i<a.size();i++){
                if(a[i]==b[i]) ret+=string(1,'0');
                else ret+=string(1,'1');
            }
            return ret;
        }
        int crack(vector <string> pl, vector <string> ci) {
            set<string> strs;
            for(int j=0;j<pl.size();j++){
                for(int i=0;i<ci.size();i++){
                    string key=_xor(ci[i],pl[j]);
                    bool isok=true;
                    for(int k=0;k<ci.size();k++){
                        bool is=false;
                        for(int l=0;l<pl.size();l++){
                            if(_xor(pl[l],key)==ci[k]){
                                is=true;
                            }
                        }
                        if(!is)  isok=false;
                    }
                    if(isok) strs.insert(key);
                }
            }
            return strs.size();
        }
};

xorをstringのままシュミレートしていたところを、一旦long longに変換して、それでxorをとってやればTLEせずに通る。

//include等は省略
class NetworkXOneTimePad {
    public:
        int crack(vector <string> pl, vector <string> ci) {
            set<ll> keys;
            vector<ll> pln(pl.size()),cin(ci.size());
            for(int i=0;i<pl.size();i++){
                ll n=0;
                for(int j=0;j<pl[i].size();j++){
                    n+=(pl[i][j]-'0')*((ll)1<<j);
                }
                pln[i]=n;
            }
            for(int i=0;i<ci.size();i++){
                ll n=0;
                for(int j=0;j<ci[i].size();j++){
                    n+=(ci[i][j]-'0')*((ll)1<<j);
                }
                cin[i]=n;
            }
            for(int j=0;j<pl.size();j++){
                for(int i=0;i<ci.size();i++){
                    ll key=cin[i]^pln[j];
                    bool isok=true;
                    for(int k=0;k<ci.size();k++){
                        bool is=false;
                        for(int l=0;l<pl.size();l++){
                            if((pln[l]^key)==cin[k]){   // == は ^ よりも優先度が高いことに注意
                                is=true;
                            }
                        }
                        if(!is)  isok=false;
                    }
                    if(isok) keys.insert(key);
                }
            }
            return keys.size();
        }
};

ちなみに、上のプログラムのオーダーはO(N^4)くらいだが、二分探索などを使えばO(N^3logN)でも通る。そのプログラムは、

class NetworkXOneTimePad {
    public:
        int crack(vector <string> pl, vector <string> ci) {
            set<ll> strs;
            vector<ll> pln(pl.size()),cin(ci.size());
            for(int i=0;i<pl.size();i++){
                ll n=0;
                for(int j=0;j<pl[i].size();j++){
                    n+=(pl[i][j]-'0')*((ll)1<<j);
                }
                pln[i]=n;
            }
            for(int i=0;i<ci.size();i++){
                ll n=0;
                for(int j=0;j<ci[i].size();j++){
                    n+=(ci[i][j]-'0')*((ll)1<<j);
                }
                cin[i]=n;
            }
            for(int j=0;j<pl.size();j++){
                for(int i=0;i<ci.size();i++){
                    ll key=cin[i]^pln[j];
                    vector<ll> plci(pl.size());
                    for(int k=0;k<pl.size();k++){
                        plci[k]=pln[k]^key;
                    }
                    bool is=true;
                    sort(ALL(plci));
                    for(int k=0;k<ci.size();k++){
                        if(!binary_search(ALL(plci),cin[k])) is=false;
                    }
                    if(is) strs.insert(key);
                }
            }
            return strs.size();
        }
};

1000 NetworkXMessageRecovery

解法が思いつかなかったので適当なアルゴリズムをでっちあげて提出する。順序が逆になってる間ずっとそれをもとに戻すようなアルゴリズム。ちゃんと辞書順になってくれないケースが存在するので通らない。

//include等は省略
class NetworkXMessageRecovery {
    public:
        string recover(vector <string> messages) {
            set<char> cs;
            set<pair<char,char> > cha;
            for(int i=0;i<messages.size();i++){
                for(int j=0;j<messages[i].size();j++){
                    cs.insert(messages[i][j]);
                }
                for(int j=1;j<messages[i].size();j++){
                    cha.insert(make_pair(messages[i][j-1],messages[i][j]));
                }
            }
            string fi;
            for(set<char>::iterator it=cs.begin();it!=cs.end();it++){
                fi+=string(1,*it);
            }
            for(;;){
                bool is=false;
                for(set<pair<char,char> >::iterator it=cha.begin();it!=cha.end();it++){
                    int fst,snd;
                    for(int i=0;i<fi.size();i++){
                        if(fi[i]==it->first) fst=i;
                        if(fi[i]==it->second) snd=i;
                    }
                    if(fst>snd){
                        is=true;
                        char t=fi[fst];
                        fi[fst]=fi[snd];
                        fi[snd]=t;
                    }
                }
                if(!is) break;
            }
            return fi;
        }
};

終わった後考えても分からなかったので解法を調べる。

次に取り出す文字を一回一回決めて、全部取り出したらそれを連結した文字列を返す。

その決め方:それぞれの部分文字列のまだ取り出していない文字のなかでもっとも先頭にあるもののうち、ほかの部分文字列のまだ取り出していない文字のうちの先頭以外の部分に含まれていない文字たちが次に取り出す候補となる。辞書順にしたいので、その候補のうちもっとも辞書順で小さいものが次に取り出す文字。

//include等は省略
class NetworkXMessageRecovery {
    public:
        string recover(vector <string> mes) {
            vector<int> pos(mes.size(),0);
            string ret;
            for(;;){
                vector<char> kouho;
                for(int i=0;i<mes.size();i++){
                    if(pos[i]==mes[i].size()) continue;
                    char nc=mes[i][pos[i]];
                    bool is=true;
                    for(int j=0;j<mes.size();j++){
                        if(i==j) continue;
                        for(int k=pos[j]+1;k<mes[j].size();k++){
                            if(mes[j][k]==nc) is=false;
                        }
                    }
                    if(is) kouho.push_back(nc);
                }
                sort(ALL(kouho));
                if(kouho.size()>=1){
                    ret+=kouho[0];
                    for(int i=0;i<pos.size();i++){
                        if(mes[i][pos[i]]==kouho[0]) pos[i]++;
                    }
                }else break;
            }
            return ret;
        }
};

Challenge Phase

なにもできない、なにもされない

2011-08-28

TopCoder SRM 515 Div1

08:51

書くのが遅くなってしまっている

結果

Challenged Compiled Unopened +50*0 -25*0 Total:0.00 1289→1192(-97)

いい国つくろう鎌倉幕府。

250 RotatedClock

シュミレーション的に書く。時計を一番上にしている場所が、数字のついている所にしなければいけないことを考慮しないといけない。

具体的には、(与えられた長針の角度)%30==(本当の長針の角度)%30∧(与えられた短針の角度)%30==(本当の短針の角度)が成り立つ、というのを考慮すればよくて、この方針は間違っていなかったけれど(使っている人はあまり見当たらない)、余りを取っていなかったりなど初歩的な処理をを忘れていた…。

提出したコードは

//include等省略
class RotatedClock {
    public:
        string getEarliest(int hourHand, int minuteHand) {
            for(int i=0;i<60*12;i+=2){
                if(hourHand-minuteHand == (i/2 - i*6)%360 && hourHand%30==(i/2)%30 && minuteHand%30==(i*6)%30){
                    stringstream retss;
                    int hour=i/60;
                    if(hour<10){
                        retss<<'0';
                    }
                    retss<<hour<<':';
                    int minute=i%60;
                    if(minute<10){
                        retss<<'0';
                    }
                    retss<<minute;
                    return retss.str();
                }
            }
            return "";
        }
};

こんなコードを書けば通る。

//include等省略

class RotatedClock {
    public:
        string getEarliest(int hourHand, int minuteHand) {
            int motomod=(hourHand-minuteHand+360)%360;
            for(int i=0;i<60*12;i+=2){
                int hmod=(i/2)%360,mmod=(i*6)%360;
                if(motomod == (hmod-mmod+360)%360 && hourHand%30==hmod%30 && minuteHand%30==mmod%30){
                    stringstream retss;
                    int hour=i/60;
                    if(hour<10){
                        retss<<'0';
                    }
                    retss<<hour<<':';
                    int minute=i%60;
                    if(minute<10){
                        retss<<'0';
                    }
                    retss<<minute;
                    return retss.str();
                }
            }
            return "";
        }
};

550 NewItemShop

人が訪れたどうかの配列(最悪2^24通り程度)、今の時間(最悪24通り)、残りの本数(最悪25通り)でDP(メモ化再帰)すればよい。しかし、状態数が最悪で(2^24)*24*25ぐらいになるので、このままではTLEしてしまう。しかし、一回しか訪れない人についてはDPする上で保持する必要がない(少し考えれば分かると思う)ので、訪れたかどうかの配列の状態数は2^12通りにできる(これは自力では思いつかなかった)。この方法ではTLEはしない。

この方法に基づいて書いたコード:

//include等は省略
typedef pair<int,pair<int,int> > P;
struct cust{
    int T,C,P;
    cust(int t,int c,int p){
        T=t;
        C=c;
        P=p;
    }
    cust(){}
};
class NewItemShop {
    public:
        map<P,double> dp;
        vector<vector<cust> > custs;
        vector<int> mapping;
        double solve(vector<bool> whocame,int time,int nokori){
            if(time>=24 || nokori==0) return 0;
            int key=0;
            for(int i=0;i<whocame.size();i++){
                if(whocame[i]) key|=(1<<i);
            }
            P pa=make_pair(key,make_pair(time,nokori));
            if(dp.find(pa)==dp.end()){
                int ncome=-1,ncomeat,ntime=INT_MAX;
                for(int i=0;i<custs.size();i++){
                    if(mapping[i]==-1 || !whocame[mapping[i]]){
                        for(int j=0;j<custs[i].size();j++){
                            if(custs[i][j].T>=time && custs[i][j].T<ntime){
                                ncome=i;
                                ncomeat=j;
                                ntime=custs[i][j].T;
                            }
                        }
                    }
                }
                if(ncome==-1) return dp[pa]=0;
                double nmot=100,nson=custs[ncome][ncomeat].P;
                for(int i=0;i<custs[ncome].size();i++){
                    if(custs[ncome][i].T<ntime) nmot-=custs[ncome][i].P;
                }
                double pos=nson/nmot;
                double ret=0;
                if(mapping[ncome]!=-1) whocame[mapping[ncome]]=true;
                ret+=pos*(max(solve(whocame,ntime+1,nokori-1)+custs[ncome][ncomeat].C,solve(whocame,ntime+1,nokori)));
                if(mapping[ncome]!=-1) whocame[mapping[ncome]]=false;
                ret+=(1-pos)*solve(whocame,ntime+1,nokori);
                dp[pa]=ret;
            }
            return dp[pa];
        }
 
        double getMaximum(int swords, vector <string> customers) {
            custs=vector<vector<cust> >(customers.size());
            mapping=vector<int>(customers.size());
            int sz=0;
            for(int i=0;i<customers.size();i++){
                vector<string> custrs;
                int at=0;
                for(;;){
                    string now;
                    for(;at<customers[i].size()&&customers[i][at]!=' ';at++){
                        now+=string(1,customers[i][at]);
                    }
                    custrs.push_back(now);
                    if(at==customers[i].size()) break;
                    at++;
                }
                vector<cust> nowc(custrs.size());
                for(int j=0;j<custrs.size();j++){
                    int t,c,p;
                    sscanf(custrs[j].c_str(),"%d,%d,%d",&t,&c,&p);
                    nowc[j]=cust(t,c,p);
                }
                custs[i]=nowc;
                if(nowc.size()<=1) mapping[i]=-1;
                else mapping[i]=sz++;
            }
            return solve(vector<bool>(sz,false),0,swords);
        }
};

1000 MeetInTheMaze

みていない

Challenge Phase

250を落とされて萎える

2011-08-16

Codeforces Beta Round #81

16:59

結果

Failed 608 - - - +0/-0 Total:608 291st 1553→1675

id:rng_58の部屋から、id:kyuridenamidaid:hogloidと共に参加した。

ところで、途中からCFにほとんどつながらないようになっていて謎だった。他のサイトにはつながっていたのに。

A Transmigration

やるだけ∧実装楽 なのだが、浮動小数点の掛け算における誤差に気づかずに死亡する。

もちろん自分が知らないのが悪いのだが、えげつない…

また、「k is a real number with exactly two digits after decimal point」という記述を読み飛ばしていなければこの問題に気づいた可能性もあるなぁと思う。

Failedしたコード

//include等省略
int main(){
    int N,M;
    double K;
    cin>>N>>M>>K;
    vector<pair<string,int> > abs;
    string in;
    double a;
    for(int i=0;i<N;i++){
        cin>>in>>a;
        if(a*K>=100) abs.push_back(make_pair(in,a*K));
    }
    int sz=abs.size();
    for(int i=0;i<M;i++){
        cin>>in;
        bool is=true;
        for(int j=0;j<sz;j++){
            if(abs[j].first==in) is=false;
        }
        if(is) abs.push_back(make_pair(in,0));
    }
    sort(ALL(abs));
    cout<<abs.size()<<endl;
    for(int i=0;i<abs.size();i++){
        cout<<abs[i].first<<" "<<abs[i].second<<endl;
    }
}

こんな感じのコードを書くと通る。

//include等省略
int main(){
    int N,M;
    double K;
    cin>>N>>M>>K;
    K+=0.000000001;     //変更点
    vector<pair<string,int> > abs;
    string in;
    double a;
    for(int i=0;i<N;i++){
        cin>>in>>a;
        if(a*K>=100) abs.push_back(make_pair(in,a*K));
    }
    int sz=abs.size();
    for(int i=0;i<M;i++){
        cin>>in;
        bool is=true;
        for(int j=0;j<sz;j++){
            if(abs[j].first==in) is=false;
        }
        if(is) abs.push_back(make_pair(in,0));
    }
    sort(ALL(abs));
    cout<<abs.size()<<endl;
    for(int i=0;i<abs.size();i++){
        cout<<abs[i].first<<" "<<abs[i].second<<endl;
    }
}

B Dark Assembly

(ダーク♂議会 とか言ってる人がいた)

やるだけだけど、実装はそれなりに大変。

「The probability that a player will be able to kill a certain group of senators is equal to A / (A + B), where A is the sum of levels of all player's characters and B is the sum of levels of all senators in this group. 」という問題文の一部を読み間違えていてそれなりに悩んだ。

vector<int> ses;
double solve(vector<int> ks,int dim,int at,int plpower,int sepower,int mi){
    if(at==ks.size()-1){
        ks[at]+=dim*10;
        double kaku=0;
        for(int i=0;i<(1<<ks.size());i++){
            int nu=0;
            for(int j=0;j<ks.size();j++){
                if((i&(1<<j))!=0) nu++;
            }
            double nowk=1;
            int power=0;
            for(int j=0;j<ks.size();j++){
                double now=ks[j];
                if(now>=100) now=100;
                if((i&(1<<j))!=0){
                    nowk*=now/100;
                }else{
                    nowk*=1-(now/100);
                    power+=ses[j];
                }
            }
            if(nu<=mi) nowk*=(double)plpower/(plpower+power);
            kaku+=nowk;
        }
        return kaku;
    }else{
        double ma=0;
        for(int i=0;i<=dim;i++){
            ks[at]+=i*10;
            ma=max(ma,solve(ks,dim-i,at+1,plpower,sepower,mi));
            ks[at]-=i*10;
        }
        return ma;
    }
}
int main(){
    int N,K,A;
    scanf("%d%d%d",&N,&K,&A);
    ses=vector<int>(N);
    vector<int> ks(N);
    double sesum=0;
    for(int i=0;i<N;i++){
        scanf("%d%d",&ses[i],&ks[i]);
        sesum+=ses[i];
    }
    printf("%.8f\n",solve(ks,K,0,A,sesum,N/2));
}

感想・反省

  • まれに見る悪問セットではないか?
  • でも悪問セットも取れなければいけない

2011-07-26

TopCoder SRM 513 Div1

22:39

結果

110.91 Opened Opened +50*0 -25*0 Total:110.91 1330→1289(-41)

帰りの電車でSRMあることなんて思い出さなければよかったのではないか。

250 YetAnotherIncredibleMachine

  • 問題文長い…
  • 全てのボールを受けられるようにする場合の数を求めるのかなぁ
  • 違った
  • 簡単だな
  • 書く
  • 最後のケースだけ合わない
  • どうしようもない
  • ちょうあせる
  • 手計算で確かめたりとかするけど無駄
  • アッ、掛け算のなかでオーバーフローしてるやん
  • 直す(編集距離3)
//include等省略
class YetAnotherIncredibleMachine {
    public:
        int countWays(vector <int> platformMount, vector <int> platformLength, vector <int> balls) {
            int sz=platformMount.size();
            ll now=1;
            for(int i=0;i<sz;i++){
                int kake=0;
                for(int k=platformMount[i]-platformLength[i];k<=platformMount[i];k++){
                    bool is=true;
                    for(int j=0;j<balls.size();j++){
                        if(k<= balls[j] && balls[j]<=k+platformLength[i]){
                            is=false;
                        }
                    }
                    if(is){
                        kake++;
                        kake%=1000000009;
                    }
                }
                printf("%d\n",kake);
                kake%=1000000009;
                now*=kake;
                now%=1000000009;
            }
            return now;
        }
};

500 PerfectMemory

読んだ

1000 Reflections

読んでちょっと書いた

Challenge Phase

250のmodの値間違ってる人を探す作業をしていたけどmod間違ってると最後のテストケースではじかれるはずなので無駄やん

0 Reflection

やるだけ。

#include <iostream>
using namespace std;

int main(){
    for(;;){
        cout<<"オーバーフローに気をつけましょう"<<endl;
    }
}

LouiseLouise2012/11/15 11:55I cnaont tell a lie, that really helped.

xuniidarmeoxuniidarmeo2012/11/16 06:07xHsIQY <a href="http://nwewqvcmkbkx.com/">nwewqvcmkbkx</a>

sgfjpjylcqbsgfjpjylcqb2012/11/17 05:34i1Qeue , [url=http://ktwxtgbfnoiz.com/]ktwxtgbfnoiz[/url], [link=http://meruzyddfigv.com/]meruzyddfigv[/link], http://fvwzyvyloiif.com/