CODE FESTIVAL 2015 予選B : Python練習編

Dにだいぶ手こずってしまった。
http://code-festival-2015-qualb.contest.atcoder.jp/assignments

A - ダブル文字列/Double String

ある同じ文字を２つ以上含まない文字列が与えられる。
この文字列に登場する各文字に対し２つずつ持つ文字列を答えよ。

元の文字列を２つ連結させればよい。

S=raw_input()
print S+S

B - 採点/Grading

N人の意見はそれぞれA[i]である。
過半数である意見を求めよ。

ある意見xがC(x)回出てきているとき、C(x)*2＞Nなら過半数。

import sys

N,M=map(int,raw_input().strip().split(" "))
A=map(int,raw_input().strip().split(" "))
C=[0]*101010

for x in A:
	C[x]+=1
for i in range(M+1):
	if C[i]*2 > N:
		print i
		sys.exit(0)

print '?'

C - 旅館/Hotel

N個の部屋があり、各定員はA[i]である。
ここにM個の団体客が来る予定で、それぞれの人数はB[i]である。
１つの部屋には１つの団体しか止まれず、また１つの団体を複数の部屋に分割して泊めることはできない。
全団体を泊めるような部屋の割り当ては可能か。

A,Bをソートして、Bの多い順にAの多い部屋を順に割り当てていけば良い。

N,M=map(int,raw_input().strip().split(" "))
A=map(int,raw_input().strip().split(" "))
B=map(int,raw_input().strip().split(" "))

A.sort()
B.sort()

ok = 0
if N>=M:
	ok = 1
	for i in range(M):
		if A[N-M+i] < B[i]:
			ok = 0

if ok > 0:
	print "YES"
else:
	print "NO"

D - マスと駒と色塗り/Squares, Pieces and Coloring

一次元に無限に続くマス目の列がある。マスには端から0,1,2...と連番がついている。
ここでN個のクエリを順次処理せよ。

各クエリは２値S,Cからなる。
S番のマスから数えて順にC個、過去に塗っていないマスに到達するまで順にマスを塗っていく。
各クエリについて最後に塗ったマスの位置を求めよ。

以下はsetのiteratorを使った解法のためC++。
色々方法はありそうだが、自分は連続して塗られた領域[L,R]の組をsetで管理した。
Cの大きなクエリを処理すると、元々不連続に塗られていた領域がくっつき１つの領域になる場合があるので、うまく処理していこう。

今回、区間の末尾の値をpairのfirstに割り当ててみたけど、lower_boundとはなかなか相性がいいかも。

int N;
ll S,C;

set<pair<ll,ll> > SS;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	SS.insert({2LL<<60,1LL<<60});
	
	cin>>N;
	FOR(i,N) {
		cin>>S>>C;
		ll OS=S;
		auto ss=SS.lower_bound({S,0});
		
		if(ss->second<=OS) {
			C+=ss->first-ss->second+1;
			S=OS=ss->second;
			SS.erase(ss);
		}
		
		while(C>0) {
			auto ss=SS.lower_bound({S,0});
			
			if(S+C==ss->second) {
				ll a=ss->first;
				SS.erase(ss);
				SS.insert({a,OS});
				cout<<S+C-1<<endl;
				break;
			}
			
			if(S+C-1 < ss->second-1) {
				SS.insert({S+C-1,OS});
				cout<<S+C-1<<endl;
				break;
			}
			
			C-=ss->second-S;
			S=ss->first+1;
			SS.erase(ss);
		}
	}
	
}

まとめ

区間のくっつけたり離したりはいい加減何度もやってるしライブラリにしようかな…。