Codeforces Round #228 (Div. 2) - 君はまるで砂漠に咲く、一輪の花。

A. Fox and Number Game

ざっくりと大意

・n個ある\(x_1\)..\(x_n\)の数列で\(x_i\) > \(x_j\) な関係のものがあれば、 \(x_i\) = \(x_i\) - \(x_j\) の処理でも置き換えが出来なくなるまで繰返して数列の総和を最小にする。

方針のようなもの

・\(x_i\) = \(x_i\) - \(x_j\) が出来なくなるまで、数列の数が全て等しくなるまで繰り返す。

n=int(raw_input())
l=map(int,raw_input().split())
ans=chk=0
while 1:
    l.sort()
    chk=0
    for i in range(1,n):
        if l[i]>l[i-1]:
            l[i]=l[i]-l[i-1]
            chk=1
    if chk==0:
        break
print l[0]*n

全てに共通の最大公約数を探してnを掛けるのでも良かったらしい。scott_wuさんの解答例。 http://codeforces.com/contest/389/submission/5898249

n=input()
def gcd (a, b):
    return a if b == 0 else gcd (b, a % b)
print n * reduce (gcd, map (int, raw_input().split()))

B. Fox and Cross

ざっくりと大意

・n*nのフィールド上にある#は#が十字状に並んだものの集まりであるか？？

方針のようなもの

・#が十字状になっている箇所を.に置換していって#が残らなければYESと言えるし、残ったらNOだと思う。

xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
#start = time.clock()
n=int(raw_input())
l=[]
for i in range(n):
    l.append(list(raw_input()))
if l[0][0]=='#' or l[0][n-1]=='#' or l[n-1][0]=='#' or l[n-1][n-1]=='#':
    print 'NO'
    exit()
for i in range(1,n-1):
    for j in range(1,n-1):
        if l[i][j]=='#':
            for x,y in xy:
                chg=1
                if l[i+x][j+y]!='#':
                    chg=0
                    break
            if chg:
                l[i][j]='.'
                for x,y in xy:
                    l[i+x][j+y]='.'
for i in range(n):
    if '#' in l[i]:
        print 'NO'
        exit()
print 'YES'

C. Fox and Box Accumulation

ざっくりと大意

・\(x_i\)の強度の箱がn個ある。0強度の箱の上には1つも箱が置けない、1強度の上には箱が1つ置ける。
・下から2,1,1まで積んだら上にはもう何も積めない。1番下の2から見て上に3箱、2番下の1から見て上に2箱ある状態になるので。。

方針のようなもの

・強度の弱い方から使う。

n=int(raw_input())
l=map(int,raw_input().split())
ans=chk=cnt=0
l.sort()
while n:
    if n==chk:
        chk=0
        cnt=0
    if cnt==0:
        ans+=1
        l.pop(0)
        cnt+=1
        n-=1
    elif cnt<=l[chk]:
        l.pop(chk)
        cnt+=1
        n-=1
    else:
        chk+=1
print ans

強度の弱い方から使わないと積み方の判定が複雑になる。例えば強い方から使う積み方で2,2,1,1,0,0と荷物があった場合に1番下に2を使った後に2番目に2と1どちらを積むのが最善であるかが残りの要素によって大きく影響を受ける。最善は2,1,0と2,1,0の2列の積み方であるが2を続けて積んでしまっていたら2,2,1と1,0と0の3列になっているし、積み方が複数パターンあるのを全パターン試行しなくては最小が探せないと思う。そして1つ0を減らして2,2,1,1,0と荷物があった場合には2を続けて積んでも2,2,1と1,0か2,1,0と2,1のどちらでも2列ではあるが最小を確定するには全パターン試行が必要だと思う。
だが弱い方から使えば0を1つ使った後に最低でも必要な強度は1であり1の箱を続けて選択する。既に0,1の箱があるので最低でも必要な強度は2であり2の箱を選択する。続けて積むには最低必要な強度は3であるがソレはないため1列積みを終了して、再度2列目の積み方を0から使用して2列で積み終わる。
弱い方から使った場合は0を使った後に同じ0は使えず、1,2では1のほうがより優先度が高いものとして明確に選択できる。強い方から使った場合は2を使った後に優先度が高いかが2以下の箱が何種類何個残ってるかに影響を受けるため明確選択するための条件の設定が非常に困難である。
書き方が非常に下手である。。。