Google Code Jam Round1B 通過

Round 1Aは通過できなかったが，1Bで通過できた．深夜ラウンド辛い...．日本は幸い翌日が休日なので参加できた．

Visibleを通ってUnvisibleを通らないコードもUnvisible正解時のpenaltyになるので，少し考えてunvisibleも通せそうならその解法でいった方が良い．interaction problemのデバッグがよくわからん...．

Code Jam - Google’s Coding Competitions

Question 1. Manhattan Crepe Cart

問題概略：南北東西それぞれQ+1本(西から0-Q, 南から0-Q番）の通りと交差点からなる．P人の人が各々(Xi, Yi)の交差点にいてDi(W,E,N,S)の方向へ向かって歩いている．ほとんどの人はマンハッタン距離に沿って，(X, Y)にあるクレープ屋さんを目指しているらしい．一番多くの人が向かっていることになるX,Yの座標のうち最も西南のものを求めよ．（制約：Q<=10⁵, P<500，街の端にいるとき街の外は向いていない）

from itertools import accumulate

def Solution(P,Q,XYD):
    X = [0]*(Q+1)
    Y = [0]*(Q+1)
    
    for x,y,d in XYD:
        if d=='W':
            X[0] += 1
            X[x] -= 1
        elif d=='E':
            X[x+1] += 1
        elif d=='N':
            Y[y+1] += 1
        elif d=='S':
            Y[0] += 1
            Y[y] -= 1
    
    X = list(accumulate(X))
    Y = list(accumulate(Y))
            
    minx=0
    for x in range(Q+1):
        if X[x]<X[minx]:
            minx=x
    
    miny=0
    for y in range(Q+1):
        if Y[y]<Y[miny]:
            miny=y
    
    return x,y

T = int(input())
for t in range(T):
    P, Q = list(map(int, input().split()))
    XYD = [list(map(int, input().split())) for _ in range(P)]
    x, y = Solution(P,Q,XYD)
    print('Case #{}: {} {}'.format(t+1,x,y))

xi, yiの人がWに向かっているなら，x < xiの全領域が候補でyは関係ない．よってx, yを別に考えることにして，x < xiにフラグを立てて，全員分の和を取れば良い．愚直にやると遅いO(N²)ので，領域の端点をそれぞれ+1, -1しておいて最後に累積和を取るとO(N)．この累積和が最大となるxのうち一番西のものを答えれば良い．素のpythonでちょこちょこ書いたが，numpyをimportしてargminをとっても良いかも．

Question2. Draupnir

問題概要：Odirさんは1日毎に倍増するリングをR[1]個，2日ごとに倍増するリングをR[2]個，...，6日ごとに倍増するリングをR[5]個持っている（0<=R[i]<=100, 1<=sum(R))．あなたはある日（1～500）日目における合計の指輪の個数（mod 2⁶³）をW回（tests et1: 6回, test set: 2回）まで尋ねることができる．Rを求めよ．

def Solution(n42, n210):
    R = [0]*6
    R[3] = (n210>>52) & 0b1111111
    R[4] = (n210>>42) & 0b1111111
    R[5] = (n210>>35) & 0b1111111
    n42 = n42 - R[3]*2**10 - R[4]*2**8 - R[5]*2**7
    R[0] = (n42>>42) & 0b1111111
    R[1] = (n42>>21) & 0b1111111
    R[2] = (n42>>14) & 0b1111111
    return R

T,W = list(map(int, input().split()))
for t in range(T):
    print(42, flush=True)
    n42 = int(input())
    
    print(210, flush=True)
    n210 = int(input())
    
    R = Solution(n42, n210)
    
    print(' '.join([str(r) for r in R]), flush=True)
    ret = int(input())
    if ret == -1:
        raise

キレイに解けてよかった．ビット演算の問題はじめてまともに解けた気がする．100 < 2⁷=128なので，それ以上差が開く日を聞けば良い．mod 2⁹¹以上とかなら，n=42の代わりにn=84を聞けば，途中でn42 = n42 - R[3]*2**10 - R[4]*2**8 - R[5]*2**7が要らない．終わってから気づいたけど，REってWAのことか...．

Question.3 Fair Fights

問題概要：数列Cと数列Dが与えられる．その部分列CL～CRの最大値とDL～DRの最大値について，差の絶対値がK以下となるようなL, Rの組み合わせの数を求めよ．（制約：0<=Ci,Di<=10⁵, K<= 10⁵, test case 1: n<=100, test case 2: n<=10⁵)

class SegTree():
  def __init__(self, func, A, identity=1e9):
    self._func = func
    self._N = 1
    while self._N < len(A):
      self._N *= 2
       # 長さ 7 なら N=3 (2^3=8)
    self._identity = identity # maxなら-1e9, sumなら0, productなら1

    self._tree = [self._identity] * (2*self._N -1) 
    self._tree[self._N-1:self._N-1+ len(A)] = A #最下段に元の配列を
    for i in range(self._N-2, -1, -1):
      self._calc_single_node(i)
    ########
    # N=3: #
    # 0000 #
    # 1122 #
    # 3456 #
    ########
    self._node_range = [(i-self._N+1,i-self._N+2) for i in range(2*self._N-1)] #right_exclusive
    for i in range(self._N-2, -1, -1):
      self._node_range[i] = (self._node_range[2*i+1][0], self._node_range[2*i+2][1])

  def _calc_single_node(self,i):
    self._tree[i] = self._func(self._tree[2*i+1], self._tree[2*i+2])

  def point_update(self,i,x):
    # A[i] = x (addではないので注意)
    j = self._N-1+i
    self._tree[j] = x
    while j>0:
      j = (j-1)//2
      self._calc_single_node(j)

  def range_query(self, l, r, on=0):
    # reduce(func, A[l:r])
    # onはノード[on]上と重なる部分の，ということ
    onl, onr = self._node_range[on]
    
    # ノード[on]上はすべて覆う
    if l<=onl and onr<=r:
      return self._tree[on]
    
    # 重なりなし
    elif onr<=l or r<=onl:
      return self._identity
    
    else:
      return self._func(self.range_query(l, r, on=2*on+1),
                        self.range_query(l, r, on=2*on+2))


from itertools import combinations

def Solution(N,K,C,D):
    C_st = SegTree(max, C, identity=0)
    D_st = SegTree(max, D, identity=0)

    answer = 0
    
    for l,r in combinations(range(N+1), 2):
        C_max = C_st.range_query(l,r)
        D_max = D_st.range_query(l,r)
        if abs(C_max-D_max)<=K:
            answer += 1
    return answer

T = int(input())
for t in range(T):
    N, K = list(map(int, input().split()))
    C = list(map(int, input().split()))
    D = list(map(int, input().split()))
    answer = Solution(N,K,C,D)
    print('Case #{}: {}'.format(str(t+1), str(answer)))

N=10⁵で制限時間は30秒なのでO(N²)は通らない．test set1はok．test set2はTLEと予想通り．class SegTreeは時間内に実装したわけではなく，自作コード集からのコピペ．ただ，解説によるとn=100なので愚直にmaxとっても通るらしい．

なお，test set2を通すためにはこれだけではだめで，選ばれるCiに注目してCL～Ci-1のmaxがCi未満となるような最大のL，DL～DiのmaxがCi＋K以下となる最大のL，DL～DiのmaxがCi-K以上となる最小のLを，それぞれ二分探索＋上記Seg木のrange_queryで探す，ということらしい．

教訓：何を固定するかをよく考える．最大値・最小値などの極端な値に注目すること（L固定，R固定しか考えてなかった）．Seg木はそれで終わりではなく二分探索と組み合わせられると強力．二列あるときはあえて非対称に扱うことも考える．

勉強の記録

機械学習、情報処理について勉強した事柄など

Google Code Jam Round1B 通過

Question 1. Manhattan Crepe Cart

Question2. Draupnir

Question.3 Fair Fights