Foregone Solution

https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/0000000000088231

任意の数値を二つの和に分ける。ただし、その和は4を使ってはならない。

1桁ずつ、繰上りが発生しないように分けていく。 6以下は、奇数の時に備えてceil / floorを使えば単に半分にすればよい。 7以上はその実装では4が発生する可能性があるので、6を引けばよい。これで桁ごとに計算が可能なので、計算量はO(logN)になる。

import math

t = int(input())
for i in range(1, t + 1):
  N = int(input())
  a = 0
  b = 0
  for d in str(N):
      a *= 10
      b *= 10
      d = int(d)
      if d >= 6:
          a += 6
          b += d - 6
      else:
          a += math.ceil(d / 2)
          b += math.floor(d / 2)
  print("Case #{}: {} {}".format(i, a, b))

You Can Go Your Own Way

https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/00000000000881da

これはまじでサンプルのイラストがひっかけ。

N * Nのマス目の一番左上から右下までの経路が与えられる。経路は右か下のみ。この経路のいずれとも重なり合わない経路を一つ出す。

はじめはサンプルのように、与えられた経路に対して四角形を作るような経路を思い立つが、既存経路を超えて四角形を作るか、既存経路を超えずに手前で作るかは、そのあとの経路次第で決まってしまうためしばらく悩む。

が、最終的に、一番最初と最後が一番重要であることに気が付く。

最初が右、最後が下で入った場合、左の壁と下の壁に沿った経路は被らないし、最初が下、最後が右で入った場合も、同様に、上の壁と右の壁に沿えば被らない。

最初も最後も右であった場合、まず左の壁と右の壁に沿っていれば被らない。どこかで左から右にわたれればよい。そこで考えると、既存経路の縦と横は同数なのに、最初と最後に右を使っているため、必ずどこかで下下と連続でつながっているところがあるはずである。ので、これを見つけて左の壁から右の壁に飛び移ればよい。

最初と最後が下であった場合も同様に、上の壁から下の壁に、右右のつながりを見つけて飛び移ればよい。

def solve(N, P):
    if P[0] != P[-1]:
        return P[-1] * (N - 1) + P[0] * (N - 1)
    else:
        t = "E" if P[0] == "S" else "S"
        c = 0
        for i in range(len(P)):
            if P[i] == t:
                c += 1
            if P[i] == t and P[i + 1] == t:
                break

        return c * t + P[0] * (N - 1) + t * (N - 1 - c)

t = int(input())
for case in range(1, t + 1):
    N = int(input())
    l = input()
    print("Case #%d: %s" % (case, solve(N, l)))

エンジニア。

Google Code Jam Qualification Round 2019 - Foregone Solution / You Can Go Your Own Way

Foregone Solution

You Can Go Your Own Way