gcj2016-1b

README.md

Google Code Jam Round 1B 2016 の解答 https://code.google.com/codejam/contest/11254486/dashboard

a.py

# coding: utf-8
# numpyでゴリ押し
import sys
import heapq
import bisect
import operator
from itertools import *
import numpy as np

def read():
  return int(input())

def reads():
  return [int(s) for s in input().split()]

T = read()

dic = ["ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"]
chars = sorted(set("".join(dic)))
R = len(chars)
M = np.array([[sum(chars[i] == c for c in dic[j]) for j in range(10)] for i in range(R)])

for case in range(1, T+1):
  S = input()
  b = np.array([sum(chars[i] == c for c in S) for i in range(R)])
  sol = [int(x + 0.5) for x in np.linalg.lstsq(M, b)[0]]

  result = "".join(str(i) * sol[i] for i in range(10))
  print("Case #{0}: {1}".format(case, result))

b.py

# coding: utf-8
# かなり遅い
import sys
import heapq
import bisect
import operator
from itertools import *

def read():
  return int(input())

def reads():
  return [int(s) for s in input().split()]

T = read()

def ch(w, i, c):
  return w[:i] + c + w[i+1:]

def maximize(w):
  return w.replace("?", "9")

def minimize(w):
  return w.replace("?", "0")

def prv(c):
  return str(max(int(c) - 1, 0))

def nxt(c):
  return str(min(int(c) + 1, 9))


def solve(C, J):
  assert (len(C) == len(J))
  if not "?" in (C + J):
    return (abs(int(J) - int(C)), C, J)
  else:
    i = min(i for i in range(len(C)) if C[i] == "?" or J[i] == "?")
    if i > 0 and int(C[:i]) < int(J[:i]):
      C = maximize(C)
      J = minimize(J)
      return (abs(int(J) - int(C)), C, J)
    elif i > 0 and int(C[:i]) > int(J[:i]):
      C = minimize(C)
      J = maximize(J)
      return (abs(int(J) - int(C)), C, J)

    if C[i] != "?":
      c = C[i]
      return min(solve(C, ch(J, i, prv(c))),
                 solve(C, ch(J, i, c)),
                 solve(C, ch(J, i, nxt(c))))
    elif J[i] != "?":
      c = J[i]
      return min(solve(ch(C, i, prv(c)), J),
                 solve(ch(C, i, c),      J),
                 solve(ch(C, i, nxt(c)), J))
    else:
      return min(solve(ch(C, i, "0"), ch(J, i, "0")),
                 solve(ch(C, i, "0"), ch(J, i, "1")),
                 solve(ch(C, i, "1"), ch(J, i, "0")))


for case in range(1, T+1):
  (C, J) = input().split()
  (_, c, j) = solve(C, J)

  print("Case #{0}: {1} {2}".format(case, c, j))

c.py

# coding: utf-8
# 2部グラフの最大マッチングの実装は蟻本によった
import sys
import heapq
import bisect
import operator
from itertools import *

def read():
  return int(input())

def reads():
  return [int(s) for s in input().split()]

T = read()

for case in range(1, T+1):
  N = read()
  G = dict()
  V = set()

  for _ in range(N):
    (S, T) = input().split()
    V.add((S, 0)); V.add((T, 1))
    if not (S, 0) in G:
      G[(S, 0)] = []
    G[(S, 0)].append((T, 1))
    if not (T, 1) in G:
      G[(T, 1)] = []
    G[(T, 1)].append((S, 0))

  res = 0
  match = {v : -1 for v in V}

  def dfs(v, used):
    used[v] = True
    for u in G[v]:
      w = match[u]
      if (w == -1) or (not used[w]) and dfs(w, used):
        match[v] = u
        match[u] = v
        return True
    return False

  for v in V:
    if match[v] == -1:
      used = {v : 0 for v in V}
      if dfs(v, used):
        res += 1

  result = N - (res + sum(match[v] == -1 for v in V))

  print("Case #{0}: {1}".format(case, result))