Manthan 2011
はい。
http://codeforces.com/contest/67
A. Partial Teacher
dp,graphs,greedy,implementation
ざっくりと大意
・学校の先生が生徒にtoffeesを配るのを最小の個数で済ませたい??
・=の時は手前の子と同じ個数、Lの時は手前の子より少ない個数、Rの時は手前の子より多い個数。
方針のようなもの
・自力ではAC出せず。。
・Lの処理がLの処理が難しかった。。。
565550のlxyxyntさんをパクリつつ、こういう目的の処理なんだろうなというのをコメント入れ。
#!/usr/bin/env python # -*- coding: UTF-8 -*- import time import sys, io import re, math #start = time.clock() n=int(raw_input()) #l=[int(x) for x in raw_input().split()] w=list(raw_input()) ans=[] #リストを左から右に作っていく for i in range(n): #for i in xrange(0,n,1): #初期値を用意 l=r=1 #w[i]がRか=だった時用 #Rが続く時はより大きくなるようにrを加算 #=が続く時はより左にRがあるならその時と同じ数が作れるようrを加算 for j in range(i-1,-1,-1): if w[j]=='L': break elif w[j]=='R': r+=1 #Lが右に続く時はより先に準備しておくようにlを加算 #=が右に続く時はより右にLがあるならその時と同じ数が作れるようlを加算 for j in range(i,n-1,1): if w[j]=='R': break if w[j]=='L': l+=1 ans.append(max(l,r)) print ' '.join(map(str,ans))