Kickstart Round G 2017

https://code.google.com/codejam/contest/3254486/dashboard#s=a&a=3

Problem A. Huge Numbers
矩阵快速幂

import sys

out_to_file = []

def slove(a,n,p):
    def pow(a, n, k):
        b = 1
        while n:
            if n&1: b=(b*a)%k
            n = (n>>1)
            a = (a*a)%k
        return b
    res = a%p
    for i in range(2,n):
        res = pow(res, i, p)
    return res
    
    
    
sys.stdin = open('submit.in', 'r')
cases = int(input())
for i_ in range(cases):
    print(i_)
    a,n,p=list(map(int, input().strip().split(' ')))
    out_to_file.append(slove(a,n,p))
    
fp = open('submit.out', 'w')
for i_,c_ in enumerate(out_to_file):
    fp.write('Case #%d: %s\n'%(i_+1, str(c_)))
#    fp.write('Case #%d: %s\n'%(i_+1,' '.join(list(map(str,c_)))))

Problem B. Cards Game
暴力AC small case

import sys

out_to_file = []

def slove(n,f,b):
    if n==1: return 0
    res = 9999999999999999
    for i in range(n):
        for j in range(n):
            if i==j: continue
            t = 0
            t += f[i]^b[j]
            t += min(slove(n-1,[f[t] for t in range(n) if t!=i], [b[t] for t in range(n) if t!=i]),
                       slove(n-1,[f[t] for t in range(n) if t!=j], [b[t] for t in range(n) if t!=j]))
            res = min(res, t)
    return res
    
sys.stdin = open('submit.in', 'r')
cases = int(input())
for i_ in range(cases):
    print(i_)
    n=int(input())
    f=list(map(int, input().strip().split(' ')))
    b=list(map(int, input().strip().split(' ')))
    out_to_file.append(slove(n,f,b))
    
fp = open('submit.out', 'w')
for i_,c_ in enumerate(out_to_file):
    fp.write('Case #%d: %s\n'%(i_+1, str(c_)))
#    fp.write('Case #%d: %s\n'%(i_+1,' '.join(list(map(str,c_)))))

Problem C. Matrix Cutting
small case是一维的情况，容易想到用DP，然后到large case就是二维转一维了。
逻辑还是一样的，就是二维数组变成4维数组

import sys
import numpy as np
import time

out_to_file = []

def slove(n,m,a):
    mi = [[[[99999999 for _ in range(m)] for _ in range(m)] for _ in range(n)] for _ in range(n)]
    arr = np.array(a)
    
    t0 = time.time()
    
    for i in range(n):
        for j in range(i,n):
            
            cols_min = [99999999]*m
            for p in range(m): cols_min[p] = arr[i:j+1,p].min()
                
            for p in range(m):
                mi[i][j][p][p] = cols_min[p]
                for q in range(p+1,m):
                    mi[i][j][p][q] = min(mi[i][j][p][q-1], cols_min[q])
    
    t1 = time.time()          
    print(t1-t0)
    
    memo = {}                
    def helper(i,j,p,q):
        if i==j and p==q: return 0
        if (i,j,p,q) in memo: return memo[(i,j,p,q)]
        
        res = 0
        mi0 = mi[i][j][p][q]
        
        for k in range(i, j):
            res = max(res, mi0+helper(i,k,p,q)+helper(k+1,j,p,q))
        for k in range(p, q):
            res = max(res, mi0+helper(i,j,p,k)+helper(i,j,k+1,q))
        
        memo[(i,j,p,q)] = res
        return res
    
    res = helper(0,n-1,0,m-1)
    
    t2 = time.time()          
    print(t2-t1)
    
    return res
    
    
    
sys.stdin = open('submit.in', 'r')
cases = int(input())
for i_ in range(cases):
    print(i_)
    n,m=list(map(int, input().strip().split(' ')))
    a=[]
    for j_ in range(n): 
        a.append(list(map(int, input().strip().split(' '))))
    out_to_file.append(slove(n,m,a))
    
fp = open('submit.out', 'w')
for i_,c_ in enumerate(out_to_file):
    fp.write('Case #%d: %s\n'%(i_+1, str(c_)))
#    fp.write('Case #%d: %s\n'%(i_+1,' '.join(list(map(str,c_)))))