GCJ 2018 Round1Aに参加した - 天色グラフィティ

f:id:ejinote:20180414130120p:plain

Google Code Jam 2018 Round1Aに参加しました。上位1500人がRound2に進めるらしいのですが、結果としては1717位で敢えなく敗退。

まぁ今回で強い人は全員消えるはずなので、Round1Bがんばりましょ。

前回の記事：

amalog.hateblo.jp

振り返り

Waffle Choppers

横方向に累積和を取った後に縦方向に累積和を取ると、左上から任意の点までの長方形に何個チョコチップが含まれているかが分かる(盤面の累積和)。

望ましい分割をするためには、縦だけに注目したときも横だけに注目したときもチョコチップが均等に別れていることが必要。なので、盤面の累積和の右端列と下端行に着目すると、そもそもうまくいく分割が存在するかが分かる。

うまくいく分割が存在するならそれに従って実際に分割してみて、ちゃんとそれぞれの部分にチョコチップが割り振られているかを累積和を参照しながら確認すれば良い。

解きながら「numpy使いたい！」ってn回叫んだ。

def cumsum(lst):
    res = [0]*len(lst)
    res[0] = lst[0]
    for i in range(1, len(lst)):
        res[i] = res[i-1] + lst[i]
    return res

def cumsum2(area):
    height = len(area)
    width = len(area[0])
    res = [[0]*width for _ in range(height)]
    
    for i in range(height):
        for j in range(width):
            if j==0:
                res[i][j] = area[i][j]
            else:
                res[i][j] = res[i][j-1] + area[i][j]

    for i in range(height):
        for j in range(width):
            if i!=0:
                res[i][j] = res[i-1][j] + res[i][j]

    return res

def case(R, C, H, V):
    hcnt = [0]*R
    vcnt = [0]*C
    total = 0
    area = [[0]*C for _ in range(R)]
    
    for i in range(R):
        row = input()
        for j, c in enumerate(row):
            if c=='@':
                area[i][j] = 1
                hcnt[i] += 1
                vcnt[j] += 1
                total += 1

    if total%((H+1)*(V+1))!=0 or total%(H+1)!=0 or total%(V+1)!=0:
        return 'IMPOSSIBLE'

    each = total//((H+1)*(V+1))
    area_cumsum = cumsum2(area)
    h_cumsum = cumsum(hcnt)
    v_cumsum = cumsum(vcnt)

    hcuts = []
    vcuts = []

    for i in range(1, H+2):
        target = total//(H+1)*i
        if target not in h_cumsum:
            return 'IMPOSSIBLE'
        else:
            hcuts.append(h_cumsum.index(target))

    for i in range(1, V+2):
        target = total//(V+1)*i 
        if target not in v_cumsum:
            return 'IMPOSSIBLE'
        else:
            vcuts.append(v_cumsum.index(target))
    
    for i, hcut in enumerate(hcuts):
        for j, vcut in enumerate(vcuts):
            if area_cumsum[hcut][vcut] != each*((i+1)*(j+1)):
                return 'IMPOSSIBLE'

    return 'POSSIBLE'


def main():
    T = int(input())
    for t in range(1, T+1):
        R, C, H, V = map(int, input().split())
        print('Case #{}: {}'.format(t, case(R, C, H, V)))

if __name__=='__main__':
    main()