2015年4月14日 星期二

2015 Google Code Jam Qualification Round

官方題目、比賽網站（可下載練習用測資並judge）
畢竟只是Qualification Round，
沒有名次、時間壓力，只要分數達到20分就晉級了，
我先前就自己下了一個目標：

要只使用python完成qualification round!


結果還算順利，自己比賽期間解了前三題，得到66分 時間15:44:11(含penalty) 1567名的成績。

Problem A. Standing Ovation 題意大致上就是每個人有一個「害羞程度x」，當已經有x人站起來鼓掌，他就會站起來鼓掌，你可以邀請一些會無條件站起來的人，請問你最少邀請幾個人便能使全部人都起立鼓掌？

輸入方式是依序輸入害羞程度為\(0,1,2,...\)的人數，十分有利於處理。
策略：從害羞程度小到大掃過去，如果已經站起來的人數不夠，就加自己邀請來的人
時間複雜度：\(O(S_{max})\)
AC的python code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
NumberOfTestCases = int( input() )
for NumTestCases in range(1,NumberOfTestCases+1):
    print('Case #',NumTestCases,': ',sep='',end='')
 
    Smax,str=input().split()
    Smax=int(Smax)
    ans = 0
    sum = 0
    for i in range(0,Smax+1):
        if sum < i:
            ans += 1
            sum += 1
        sum += int(str[i])
    print(ans)

Problem B. Infinite House of Pancakes 餐廳裡有無限張桌子，其中幾張有一些（數量不一樣）的派，每分鐘可以有兩種情況：
1.不做事，所有有派的桌子上會減少一個派
2.把某張桌子上的一些派移到某張桌子上，這一分鐘內所有桌子（除了被你調整）的派都不會減少
請以最佳策略在最少時間內讓所有桌子的派都被吃光。

我一開始想到一個策略：
用priority_queue維護所有桌子的派數量，每次把最多的一桌分兩半並更新答案
不過這是錯誤的！
1
9
 這個情況，最佳策略應該是直接把\(9\)分成\(3,3,3\)

因為是不夠熟悉的python，所以我還特地上網查priority_queue的用法，然後就這樣WA了一遍。
特別紀念這份code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from heapq import heappush
from heapq import heappop
from heapq import heapify

NumberOfTestCases = int( input() )
for NumTestCases in range(1,NumberOfTestCases+1):
 
    D = int(input())
    P = input().split()
    for i in range(0,D):
        P[i] = -int(P[i])
    heapify(P)
    ans = -P[0]
    t = 0
    while t < ans:
        t += 1
        tmp = heappop(P)
        th = tmp//2
        heappush(P,th)
        heappush(P,tmp-th)
        if -P[0]+t < ans:
            ans = -P[0]+t
    print('Case #',NumTestCases,': ',sep='',end='')
    print(ans)

WA了之後，我就拿剛剛下載的input慢慢測試、研究，
所幸當我發現錯誤的同時，我就想到一個比這好寫很多的正解了！
枚舉最多的一桌有幾個派，計算分派要花幾分鐘+吃派的時間，取最小
正確性也更加明確！
時間複雜度：\(O(D\times P_{max})\)
原本想說\(1000\times1000\)很小，所以code沒有特地取\(P_{max}\)
結果清楚感受到python效率不佳，large估計跑了半分鐘@@
AC的python code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
NumberOfTestCases = int( input() )
for NumTestCases in range(1,NumberOfTestCases+1):
    
    D = int(input())
    P = input().split()
    for i in range(0,D):
        P[i] = int(P[i])
    ans = 1000
    for i in range(1,1001):
        count = i
        for x in P:
            count += (x-1)//i
        if count < ans:
            ans = count
    print('Case #',NumTestCases,': ',sep='',end='')
    print(ans)

Problem C. Dijkstra 我覺得劇情很有梗，建議自己去讀，很好玩~
不過畢竟是題解，簡要的提點一下：給一串四元數，問是否能切成三段，使得三段的乘積分別是\(i,j,k\)
其中輸入四元數的方式是給長度不超過\(10^4\)的字串\(S\)及正整數\(X(X\leq10^{12})\)，表示該四元數為\(S\)重複\(X\)次

要發現兩個關鍵點：
1. \(i,j,k,1\)搭配負號共\(8\)個元素對乘法構成一個群(group)
2. 任何四元數的四次方都是\(1\)

基於1.，對於small，只要從前面開始找一段為\(i\)的、接續找一段為\(j\)的、看剩的是不是\(k\)。
至於large，有一種作法是把\(\geq12\)的\(X\)變成\([8,12)\)中與\(X\)模\(4\)同餘的數，然後套用上面的方法。

不過我不是這樣做！
我的想法是：從前面找一段為\(i\)、從後面找一段為\(k\)，然後判斷中間是不是\(j\)，針對中間段優化避免\(X\)很大的問題。
不過寫完之後很快就WA了QQ
所以我把上述只能處理small的作法寫出來幫助我debug。
只能過small的code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
def mul(a,b):
    minus=0
    if a[0]=='-':
        minus+=1
        x=a[1]
    else:
        x=a[0]
    if b[0]=='-':
        minus+=1
        y=b[1]
    else:
        y=b[0]
    if x=='1':
        if minus%2==1:
            y='-'+y
        return y
    if y=='1':
        if minus%2==1:
            x='-'+x
        return x
    if x==y:
        if minus%2==1:
            return '1'
        return '-1'
    use='ijkij'
    for i in range(0,3):
        if x==use[i] and y==use[i+1]:
            if minus%2==1:
                return '-'+use[i+2]
            return use[i+2]
        if x==use[i+1] and y==use[i]:
            if minus%2==0:
                return '-'+use[i+2]
            return use[i+2]

NumberOfTestCases = int( input() )
for NumTestCases in range(1,NumberOfTestCases+1):
    print('Case #',NumTestCases,': ',sep='',end='')
    L,X=map(int,input().split())
    ori=input()
    s=ori*X
    sum='1'
    u=0
    end=len(s)
    while u<end:
        sum=mul(sum,s[u])
        u+=1
        if(sum=='i'):
            break
    if sum!='i':
        print('NO')
        continue
    sum='1'
    while u<end:
        sum=mul(sum,s[u])
        u+=1
        if(sum=='j'):
            break
    if sum!='j':
        print('NO')
        continue
    sum='1'
    while u<end:
        sum=mul(sum,s[u])
        u+=1
    if sum!='k':
        print('NO')
    else:
        print("YES")
之後很快找到bug，順利解決這題！
AC的python code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
def mul(a,b):
    minus=0
    if a[0]=='-':
        minus+=1
        x=a[1]
    else:
        x=a[0]
    if b[0]=='-':
        minus+=1
        y=b[1]
    else:
        y=b[0]
    if x=='1':
        if minus%2==1:
            y='-'+y
        return y
    if y=='1':
        if minus%2==1:
            x='-'+x
        return x
    if x==y:
        if minus%2==1:
            return '1'
        return '-1'
    use='ijkij'
    for i in range(0,3):
        if x==use[i] and y==use[i+1]:
            if minus%2==1:
                return '-'+use[i+2]
            return use[i+2]
        if x==use[i+1] and y==use[i]:
            if minus%2==0:
                return '-'+use[i+2]
            return use[i+2]

NumberOfTestCases = int( input() )
for NumTestCases in range(1,NumberOfTestCases+1):
    print('Case #',NumTestCases,': ',sep='',end='')
    L,X=map(int,input().split())
    ori=input()
    sum='1'
    for x in ori:
        sum = mul(sum,x)
    tmp=ori*4
    end=len(tmp)
    Iuse=0
    r='1'
    while Iuse<end:
        r=mul(r,tmp[Iuse])
        if r=='i':
            break
        Iuse+=1
    Kuse=end-1
    r='1'
    while Kuse>=0:
        r=mul(tmp[Kuse],r)
        if r=='k':
            break
        Kuse-=1
    if Iuse>=end or Kuse<0:
        print('NO')
        continue
    Ilen=Iuse+1
    Klen=end-Kuse
    if Ilen+Klen>=L*X:
        print('NO')
        continue
    result = '1'
    if Ilen%L>0:
        for i in range(Ilen%L,L):
            result=mul(result,ori[i])
    mid = L*X - ((Ilen-1)//L+1)*L - ((Klen-1)//L+1)*L
    mid = mid//L
    mid = mid%4
    for i in range(0,mid):
        result=mul(result,sum)
    for i in range(0,Kuse%L):
        result=mul(result,ori[i])
    if result=='j':
        print('YES')
    else:
        print('NO')
不，過！
賽後與其他人討論時才發現，他是一個群(group)，所以他當然有反元素啊！
因此，中間那段根本不用那麼麻煩，只要「前面有\(i\)」、「後面有\(k\)」、「中間段長度大於\(0\)」、「全部是\(-1\)」就足夠了！
所以那段寫得最累還產生bug的地方根本白寫了OAO

Problem D. Ominous Omino 一開始有讀過題目，覺得有點麻煩；寫完problem C時也蠻晚了，就不想管這題了。
賽後聽說大部分人的作法就是硬爆，然後判斷一大堆case就結束了（想當然耳，很容易漏一兩個就炸了）。
也有少部分人認真的寫程式計算。


這回，一開始很順的開了pA，然後一口氣讀完所有題目，就跑去做其他事，有空時想作法、想到就寫。
第三年參加GCJ，感覺今年Qualification最難，不過往年沒有這麼認真寫，而且都用C++
前年，還在資芽，學程式不超過一年的我，在Round1被電爆了。
去年，在TOI，通過Round1，最終Round2衣服戰仍然戰敗。
今年，敬請期待！
P.S. GCJid: jo4
張貼者： 於
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)