SRM613だめです。
div2にて見事ゼロ完を果たしましたので解き直しました。
SystemTestは通りましたが、問題文の解釈が間違っていない保証はありません。
元の問題文
easy →http://community.topcoder.com/stat?c=problem_statement&pm=13006
medium→http://community.topcoder.com/stat?c=problem_statement&pm=13005
はじめに
ほぼチラ裏な記事です、ご了承ください。
easy
解き方
- 与えられた文字列中に「C,A,T」の文字が各一つづつ含まれている。
- 出現する順番が「C→A→T」の順である。
これに当てはまれば"possible"すれば良い。
#include <string> #include <vector> #include <algorithm> #include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> using namespace std; typedef long long ll; class TaroString{ public: string getAnswer(string S){ bool c=false,a=false,t=false; for(int i=0;i<S.size();i++){ if(S[i]=='C' || S[i]=='A' || S[i]=='T'){ if(S[i]=='C' && !c)c=true; else if(S[i]=='A' && c && !a)a=true; else if(S[i]=='T' && a && !t)t=true; else return "Impossible"; } } if(t)return "Possible"; else return "Impossible";</b> </span> } };
medium
解き方
- 1次元の線上の全ての猫が、ある任意の座標(以下中心点と呼ぶ)に向かってX移動する。
- 移動後に左端にいる猫と、右端にいる猫の距離が最小となるときの中心点を求める。※後述
- その時の距離をint型で返せば良い。
※中心点の決め方
隣り合った猫と猫の間に中心点を設定し、左端の猫と右端の猫の距離を求める。
これを全ての猫猫間と両端で試してminを取れば、理想の(?)中心点が求まる。
#include <string> #include <vector> #include <algorithm> #include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #define INF 1000000000 using namespace std; typedef long long ll; class TaroFriends{ public: int nearCenter(vector<int> str,ll center,int n){ ll len=str.size(); if(n==1){ for(int i=0;i<len;i++){ if(str[i]<=center){ return str[i]; } } return -INF; } else{ for(int i=len-1;i>=0;i--){ if(str[i]>center){ return str[i]; } } return INF; } } int getNumber(vector <int> coordinates, int X){ vector<int> str=coordinates; ll len=str.size(); ll center,l,r,n=INF; sort(str.begin(),str.end(),greater<int>()); for(int i=0;i<=len;i++){ if(i==len)center=str[0]+1; else center=str[i]-1; l=min(str[len-1]+X,nearCenter(str,center,0)-X); //most right r=max(str[0]-X,nearCenter(str,center,1)+X);//most left n=min(n,r-l); } return (int)n; } };
つぎは頑張りますので許してくださいふじこふじこ