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

あったこといろいろ

ほぼ自分用備忘録です。

SRM613だめです。

div2にて見事ゼロ完を果たしましたので解き直しました。
SystemTestは通りましたが、問題文の解釈が間違っていない保証はありません。

はじめに

ほぼチラ裏な記事です、ご了承ください。

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を取れば、理想の(?)中心点が求まる。

f:id:Yazaten:20140322140910p:plain

#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;
	}
};

つぎは頑張りますので許してくださいふじこふじこ