Codeforces Beta Round #14
はい。
A. Letter
implementation
ざっくりと大意
・外周で一直線に «.»が並んでる行や列を取り除く。
・一つでも «*»が出た内側の行や列は取り除かれない。
方針のようなもの
・上の行から見て、«*»を含んだ行が出るまで取り除く。下の行からも取り除く。
・横が見終わったら90°回して同様に取り除いてから元の方向へ90°戻す。
#!/usr/bin/env python # -*- coding: UTF-8 -*- import time import sys, io (n,m)=map(int, raw_input().split()) l,t=[],[] for i in range(n): l.append(raw_input()) while 1: if '*' not in l[0]: del l[0] elif '*' not in l[-1]: del l[-1] else: break for i in range(m): a='' for j in range(len(l)): a+=l[j][i] t.append(a) while 1: if '*' not in t[0]: del t[0] elif '*' not in t[-1]: del t[-1] else: break l=[] for i in range(len(t[0])): a='' for j in range(len(t)): a+=t[j][i] l.append(a) for i in l: print i
提出初回はdelじゃなくてremove使ってて大変な目に。。。。
はい。この問題は4行で書けたそうです。 2665613のdaidailanlanさん。
n, m = map(int, raw_input().split()) b = [raw_input() for _ in range(n)] x = [r for c in zip(*b) for r in range(n) if c[r] == '*'] y = [c for r in b for c in range(m) if r[c] == '*'] print '\n'.join(r[min(y) : max(y) + 1] for r in b[min(x) : max(x) + 1])
B. Young Photographer
ざっくりと大意
・Bobは写真を撮るのが好きでxの位置で場所を使って撮影。
・だがそのxの位置の前を対象全てが通過するとは限らない。
・対象たちのそれぞれはaからbの位置を通過、移動する。
・x地点ではなくどこか最短で移動できるトコに移動してそこで全ての選手を撮影したい??
方針のようなもの
・xと全ての選手が重なる地点で最も近所を探す。
n,x=map(int,raw_input().split()) l=[0 for i in xrange(1002)] for i in xrange(n): a,b=map(int,raw_input().split()) a,b=min(a,b),max(a,b) l[a]+=1 l[b+1]-=1 ans=1003 chk=0 for i in xrange(1001): chk+=l[i] if chk==n: ans=min(ans,abs(x-i)) print ans if ans!=1003 else -1
おそらく累積和とかいもす法と呼ばれる方法を使うと解決する。各選手のmin値がその人が出現する地点、max値がその人がいなくなる地点。配列で出現する和がnを下回る時はある1地点で全ての人を撮影できないので-1、nと等しくなるとこがあればxとの差が絶対値で最も小さな値を探す。