読者です 読者をやめる 読者になる 読者になる

夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

久しぶりの2完

これからはちょっとこの調子保ってかなきゃね。
…といっても次順当に2完したらDiv.1かな。

RotatingBot

練習〜450Div.1Easyを解いてたので550Div.1Easyにしてみたらこの前のMedだった。
mapつかってシミュレーションして今度こそAC

class RotatingBot {
public:
   int minArea( vector <int> moves ) {
        int lx=0, rx=0, dy=0, uy=0;
        int nx=0, ny=0;
        int x=1, y=1;
        int sz=moves.size();
        // 0→ 1↑ 2← 3↓
        for (int i=0; i<sz; i++) {
            if (i%4==0) nx+=moves[i];
            else if (i%4==1) ny-=moves[i];
            else if (i%4==2) nx-=moves[i];
            else ny+=moves[i];
            lx=min(lx,nx); rx=max(rx,nx);
            dy=min(dy,ny); uy=max(uy,ny);
            if (i%2==0) x=max(x,moves[i]+1);
            else y=max(y,moves[i]+1);
        }
        bool flag=true;
        nx=ny=0;
        map<pii, bool> mp;
        mp[make_pair(nx,ny)]=true;
        cout<<lx<<" "<<rx<<endl;
        cout<<dy<<" "<<uy<<endl;
        for (int i=0; i<sz&&flag; i++) {
            if (i%4==0) {
                for (int j=nx+1; j<=nx+moves[i]; j++) {
                    if (mp.find(make_pair(j,ny))!=mp.end()) {
                        flag=false;
                        break;
                    }
                    mp[make_pair(j,ny)]=true;
                }
                nx+=moves[i];
                if (i!=sz-1&&nx<rx&&mp.find(make_pair(nx+1,ny))==mp.end()) flag=false;
            } else if (i%4==1) {
                for (int j=ny-1; j>=ny-moves[i]; j--) {
                    if (mp.find(make_pair(nx,j))!=mp.end()) {
                        flag=false;
                        break;
                    }
                    mp[make_pair(nx,j)]=true;
                }
                ny-=moves[i];
                if (i!=sz-1&&ny>dy&&mp.find(make_pair(nx,ny-1))==mp.end()) flag=false;
            } else if (i%4==2) {
                for (int j=nx-1; j>=nx-moves[i]; j--) {
                    if (mp.find(make_pair(j,ny))!=mp.end()) {
                        flag=false;
                        break;
                    }
                    mp[make_pair(j,ny)]=true;
                }
                nx-=moves[i];
                if (i!=sz-1&&nx>lx&&mp.find(make_pair(nx-1,ny))==mp.end()) flag=false;
            } else {
                for (int j=ny+1; j<=ny+moves[i]; j++) {
                    if (mp.find(make_pair(nx,j))!=mp.end()) {
                        flag=false;
                        break;
                    }
                    mp[make_pair(nx,j)]=true;
                }
                ny+=moves[i];
                if (i!=sz-1&&ny<uy&&mp.find(make_pair(nx,ny+1))==mp.end()) flag=false;
            }
        }
        if (flag) return x*y;
        else return -1;
   }
};

ColorfulBricks

一瞬え?って思ってしまう問題。
読解力あればおそらく250点も夢じゃなかった

class ColorfulBricks {
public:
    int countLayouts( string bricks ) {
        set<char> ret;
        for (int i=0; i<bricks.length(); i++) ret.insert(bricks[i]);
        if (ret.size()>2) return 0;
        if (ret.size()==1) return 1;
        return 2;
    }
};

ColorfulChocolates

考え方はすぐ思いついた。
スワップ回数は文字間の距離でわかるので、maxSwapsを超えない範囲でまぁ連結できるものを愚直に探していく。
…だけど思いついてから長かったし、試行錯誤の中ようやく見つけた答えだったので実装が頭悪い

class ColorfulChocolates {
public:
    int maximumSpread( string chocolates, int maxSwaps ) {
        set<char> chara;
        int sz=chocolates.length();
        for (int i=0; i<sz; i++) chara.insert(chocolates[i]);
        int ans=0;
        set<char>::iterator it;
        for (it=chara.begin(); it!=chara.end(); it++) {
            vector<int> adr, kyori;
            for (int i=0; i<sz; i++) if (chocolates[i]==(*it)) adr.push_back(i);
            if (adr.size()==1) {
                ans=max(ans, 1);
                continue;
            }
            int ret=1;
            for (int i=0; i<adr.size(); i++) {
                int sum=0;
                int cnt=1;
                bool f1=true, f2=true;
                for (int j=1; i-j>=0||i+j<adr.size(); j++) {
                    int a=0, b=0;
                    if (i+j<adr.size()&&f1) a=adr[i+j]-adr[i]-j;
                    else f1=false;
                    if (i-j<adr.size()&&f2) b=adr[i]-adr[i-j]-j;
                    else f2=false;
                    if (a<b) {
                        sum+=a;
                        if (f1&&sum<=maxSwaps) ret=max(ret, ++cnt);
                        else {
                            sum-=a;
                            f1=false;
                        }
                        sum+=b;
                        if (f2&&sum<=maxSwaps) ret=max(ret, ++cnt);
                        else {
                            sum-=b;
                            f2=false;
                        }
                    } else {
                        sum+=b;
                        if (f2&&sum<=maxSwaps) ret=max(ret, ++cnt);
                        else {
                            sum-=b;
                            f2=false;
                        }
                        sum+=a;
                        if (f1&&sum<=maxSwaps) ret=max(ret, ++cnt);
                        else {
                            sum-=a;
                            f1=false;
                        }
                    }
                }
            }
            ans=max(ans, ret);
        }
        return ans;
    }
};

結果

1105->1151(Highest)
あと49ですね、がんばります。

広告を非表示にする