kmjp's blog

競技プログラミング参加記です

VK Cup 2015 Qualification Round 1

Codeforces

VK Cup予選は出てないので練習だけ。
http://codeforces.com/contest/522

A. Reposts

"AがBの発言をrepostした"という文面が時系列でN個与えられる。
"Polycarp"の発言の最大repost chain数を答えよ。
なお、ハンドル名は大文字小文字を区別しない。

ハンドル名を小文字に変換しながら、mapを使い各ハンドルを先頭とする最大chain数を更新していけば良い。

map<string,int> M;
string S[3];
int N,ma;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	ma=M["polycarp"]=1;
	cin>>N;
	while(N--) {
		cin>>S[0]>>S[1]>>S[2];
		FORR(c,S[0]) c=tolower(c);
		FORR(c,S[2]) c=tolower(c);
		M[S[0]]=max(M[S[0]],M[S[2]]+1);
		ma=max(ma,M[S[0]]);
	}
	cout<<ma<<endl;
	
}

B. Photo to Remember

N人の人が横１列に並んでおり、それぞれを写真に撮ろうとすると高さH[i]ピクセル、横W[i]ピクセルの矩形分の領域が必要である。
各人のうち１人が欠けた状態で(N-1)人が並んでいるとき、全員を写真に収める矩形の面積を求めよ。

各人が欠けたときの幅は、(W[i]の総和)-W[i]である。
高さは、H[i]がN人で最大なら2番目の人の高さ、それ以外ならH[i]である。

int N;
int W[202000],H[202000];
vector<int> HH;
ll TW;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>W[i]>>H[i];
		TW+=W[i];
		HH.push_back(H[i]);
	}
	sort(HH.begin(),HH.end());
	reverse(HH.begin(),HH.end());
	FOR(i,N) _P("%I64d ",(TW-W[i])*HH[HH[0]==H[i]]);
	_P("\n");
}

C. Chicken or Fish?

1～K番のK種類の食事がA[i]個ずつある。
自分の前に(M-1)人の人がおり、それぞれ乗務員に対し以下の行動をとった。

  1. どれかわからないが食事を１つ取った。
  2. T[i]番の食事を１つ取った。
  3. 最初T[i]以外の番号の食事を選ぼうとしたが、その番号の食事がないので、T[i]番を選び直した。

自分のところに乗務員が来たとき、各食事がなくなっている可能性の有無を答えよ。

ちょっとややこしい問題。
まず１回(M-1)人の食事の内容を確認し、食事の番号が判明している分はA[i]から減らす。
次に２周目の処理を行う。３番目のタイプの行動が初めて来たとき、どれかの食事を空にしなければならない。
これには、以後はその食事が要求されないもののうち残り食事数が少ないものを空にしておけば良い。
その分、「どれかわからない食事」の数を消費する。
２周目の処理が終わった後、残りの食事数が「どれかわからない食事」数を下回るなら、その食事はなくなる可能性がある。

int N;
int M,K;
int A[101000],B[101000],NZ,ND;
int T[101000],R[101000],ret[101000];
int Z[101000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	while(N--) {
		NZ=ND=0;
		cin>>M>>K;
		FOR(i,K) cin>>A[i], B[i]=A[i], R[i]=0, ret[i]=0, Z[i]=-1;
		FOR(i,M-1) {
			cin>>T[i]>>R[i];
			if(T[i]==0) NZ++;
			else B[T[i]-1]--;
		}
		bool zero=false;
		
		FOR(i,M-1) {
			if(R[i] && !zero) {
				int mi=500000;
				FOR(j,K) if(A[j]==B[j] && A[j]<=ND) ret[j]=1, mi=min(mi,A[j]);
				zero=true;
				NZ -= mi;
			}
			if(T[i]) A[T[i]-1]--;
			else ND++;
		}
		FOR(i,K) {
			if(ret[i]==0 && B[i]<=NZ) ret[i]=1;
			_P("%c","NY"[ret[i]]);
		}
		_P("\n");
	}
}

D. Closest Equals

N要素の数列A[i]が与えられる。
ここでM個のクエリ(L[i],R[i])が与えられる。
各クエリに対し、部分列A[L[i]..R[i]]のうち、A[x]=A[y]となる(x,y)のうちabs(x-y)が最小のものを答えよ。

SegTreeを使う。
各yに対し、そのもっとも近いA[x]=A[y]となるxを求め、(y-x)を求め、最小値をSegTreeで管理する。
各クエリをL[i]順にソートし、x＜L[i]となるxに対してSegTreeの値を大きな値に差し替えて選択されないようにする。
あとはクエリ毎に(L[i]～R[i])の範囲でSegTreeから(y-x)の最小値を求める。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=1<<20;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

int N,M;
int D[505000];
int L[505000],R[505000],nex[505000],ret[505000];
pair<int,int> P[505000];
SegTree_1<int,1<<19> st;

map<ll,int> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x;
		D[i]=1<<20;
		nex[i]=-1;
		if(V.count(x)) D[i]=i-V[x], nex[V[x]]=i;
		st.update(i+1,D[i]);
		V[x]=i;
	}
	FOR(i,M) cin>>L[i]>>R[i], P[i]=make_pair(L[i],i);
	x=0;
	sort(P,P+M);
	FOR(i,M) {
		while(x<P[i].first-1) {
			if(nex[x]!=-1) D[nex[x]]=1<<20, st.update(nex[x]+1,D[nex[x]]);
			x++;
		}
		ret[P[i].second]=st.getval(L[P[i].second],R[P[i].second]+1);
	}
	FOR(i,M) _P("%d\n",(ret[i]>=1<<20)?-1:ret[i]);
	
}

まとめ

よく見たらBはRound 1に続くんだな。