天色グラフィティ

技術ちっくなことを書きます

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()

Bit Party

貪欲っぽくとけば良さそうだなーと思った時点で頭が止まったので飛ばした。貪欲っぽく解けば良かったらしい。無念。

Edgy Baking

区間を持っておくDPで解けば良さそうだと思ったが、時間がなかったのでvisible setだけ通る嘘解法(貪欲)を提出した。

反省

  • 実装力が低い。特に少しひねられたDPとかで頭が止まるのをなんとかしたい。atcoderのtypical dp contestとかを解いて出直してきます。

今日はABC・ARCもあるので競プロ漬けの1日にしましょう。