Codeforces Beta Round #16 (Div. 2 Only)

はい。最終更新日:2014/05/08
http://codeforces.com/contest/16

A. Flag

implementation

ざっくりと大意

・なんか新しい決まり事で国旗が横縞の模様でないといけないことになるらしい
・横列一直線の中に違う模様が混ざるのと、二列同じ模様が続くのはNO

方針のようなもの

・一列目は違う模様が混ざってないか判定
・二列目以降は違う模様が混ざってないかと、上の列と同じ模様になってないかを判定

(n,m)=map(int, raw_input().split())
l=[list(raw_input()) for _ in range(n)]
ans='YES'
for i in range(n):
    if i==0 and l[0].count(l[0][0])!=len(l[0]):
        ans='NO'
        break
#最終列
    elif i>0 and i==n-1:
        if l[-1].count(l[-1][0])!=len(l[-1]):
            ans='NO'
        elif l[-1][0]==l[-2][0]:
            ans='NO'
    elif i>0 and l[i].count(l[i][0])!=len(l[i]):
        ans='NO'
        break
    elif i>0 and l[i][0]==l[i-1][0]:
        ans='NO'
        break
print (ans)

そろそろ3系に移行しようとしたら色々エラーでダメでした。

328937のAntonDubovikさん。

n,m=map(int,raw_input().split())
p='x'
ok=1
for i in range(0,n):
    s = raw_input()
    if len(set(list(s))) != 1 or s[0] == p:
        ok=0
        break
    p = s[0]
print "YES" if ok else "NO"

同列内に違う模様が混ざってないかの判定にset型にしてlenが1よりで大きいかで判定してた。あと前列との比較は一行受けとりながら保存で比較してた。最初は'x'が代入されているので一列目は何が来ても大丈夫なように。

2636064のdaidailanlanさん

n, m = map(int, raw_input().split())
b = [raw_input() for _ in range(n)]
print ['NO', 'YES'][all(len(set(r)) < 2 for r in b) and all(b[i - 1] != b[i] for i in range(1, n))]

B. Burglar and Matches

greedy,implementation,sortings

ざっくりと大意

・burglarさんが持ち出せる限度の中で最も効率が良いのを？？
・nが持ち出せる限度量、aが量、bが価値？？

方針のようなもの

・価値の高い順にソートして、そこから制限量になるまで持ちだしている価値を加算する

l=[]
chk,ans=0,0
(n,m)=map(int, raw_input().split())
for _ in range(m):
    i=map(int, raw_input().split())
    l.append(i)
l1=sorted(l, key=lambda l:l[1])
l1.reverse()
for i in l1:
    if n==chk: break
    elif n>=chk+i[0]:
        ans+=i[0]*i[1]
        chk+=i[0]
    else:
        ans+=(n-chk)*i[1]
        chk+=(n-chk)
print ans

lambdaを使うんでなくてa,bで受け取ってappendはb,aという方法もあったらしい。

v = []
for i in xrange(M):
   a, b = map(int, stdin.readline().split())
   v.append((b, a))
v.sort()
v.reverse()

ソートさえ終わればreverseは必要なかったかも。forでリストの-1番目からを-1ずつみていけばよかった。

C. Monitor

binary search,number theory

ざっくりと大意

・a,bが今の画面サイズ？で、それをx:yの比率にしたい？？
・a,bは与えられた数より大きくは出来ないので小さくする方に調整してx:yの比率にする
・調整後の画面サイズか出来ない場合は0 0を出力

方針のようなもの

・a,bそれぞれをx,yで割り切れるかチェック、割り切れなければ余りを引く ・比率を最大公約数で割る(初回提出はこれに気付かなかった)
・画面サイズ/比率で倍率？を求めて小さい方を基準にする

(a,b,x,y)=map(int, raw_input().split())
if x-y:
    c,k=max(x,y),min(x,y)
    while c%k:
        c,k=k,c%k
if k!=1:
    x/=k
    y/=k
if a%x:
    a-=a%x
if b%y:
    b-=b%y
if a==0 or b==0:
    print '0 0'
    exit()
ax=a/x
by=b/y
if ax<by:
    print a,y*ax
else:
    print x*by,b