久しぶりの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ですね、がんばります。