2020/07/24にTopcoderで行われたSRM788の参加記です。
公式解説はTopcoder Single Round Match 788 Editorials | Topcoderです。
Easy NextOlympics
"YYYY.MM.DD" 形式で今日の日付が与えられるので東京オリンピックの開催予定日である"July 23rd, 2021"までの日数を出力する問題です。
実装するだけですが、datetime ライブラリを使うより独自実装したほうが早いと思ったため、datetime ライブラリを使わずに実装しました。
ある月のX日からその先月のX日までの日数は先月が何月かに依存して決まるのですね。
class NextOlympics:
def countDays(self, today):
y, m, d = today.split('.')
y = int(y)
m = int(m)
d = int(d)
ty = 2021
tm = 7
td = 23
total = 0
if y < 2021:
total += 365 * (ty-y)
while m < tm:
total += [0, 31, 28, 31, 30, 31, 30][m]
m += 1
while tm < m:
total -= [0, 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31][m]
m -= 1
if d < td:
total += (td-d)
else:
total -= (d-td)
return total
Medium StarsInTheSky
2次元平面上の点集合が与えられるので、軸に平行な矩形で、異なる点集合を含むものを数え上げる問題です。
点の数 N <= 15 なので、総当りを行いました。矩形の判別は左下、右上の頂点対で行いました。
import itertools
class StarsInTheSky:
def countPictures(self, N, X, Y):
if N <= 2:
return [0, 1, 3][N]
count = set()
for i in range(2, N+1):
for p in itertools.combinations(range(N), r=i):
xs = [X[c] for c in p]
ys = [Y[c] for c in p]
count.add(self.getPic(xs, ys))
return len(count) + N
def getPic(self, xs, ys):
max_x, max_y = -float('inf'), -float('inf')
min_x, min_y = float('inf'), float('inf')
for x in xs:
max_x = max(max_x, x)
min_x = min(min_x, x)
for y in ys:
max_y = max(max_y, y)
min_y = min(min_y, y)
return (max_x, max_y, min_x, min_y)
Hard largestGCD
2次元グリッド上で (0,0) から (N-1,N-1) までの最短経路のうち、経路上の各頂点の最大公約数(GCD: Greatest Common Divisor)の最大値を求める問題です。
左上から右下に DPするだけ に見えます。
class SquareCityWalking:
def largestGCD(self, N, A):
best = [1]*(N*N)
best[0] = A[0]
for i in range(1, N):
best[i] = self.gcd(best[i-1], A[i])
for i in range(1, N):
best[N*i] = self.gcd(best[N*i-N], A[N*i])
for i in range(1, N):
for j in range(1, N):
a = A[N*i+j]
best[N*i+j] = max(self.gcd(best[N*i+j-N], a),
self.gcd(best[N*i+j-1], a))
return best[N*N-1]
def gcd(self, a, b):
while b != 0:
a, b = b, a % b
return a
嘘です。解説にある通り、途中で小さい方の値を保持する必要があるケースでWAします。
import unittest
class Test(unittest.TestCase):
def test(self):
scw = SquareCityWalking()
N = 3
A = [6, 2, 1, 3, 6, 2, 1, 2, 6]
expected = 2
self.assertEqual(scw.largestGCD(N, A), expected)
解になる可能性のある値を大きい順にループしながら、 その値を約数に持つマスだけを通って(0,0) から (N-1,N-1) まで最短経路で到達できるか検証するのが想定解でした。
下記がPythonによる実装です。
class SquareCityWalking:
def largestGCD(self, N, A):
divisors = []
for i in range(1, int(A[0]**0.5)+1):
if A[0] % i == 0:
divisors.append(i)
divisors.append(int(A[0]/i))
divisors.sort(reverse=True)
for d in divisors:
visitable = [False]*(N*N)
visitable[0] = True
for i in range(1, N):
visitable[i] = visitable[i-1] and A[i] % d == 0
for i in range(1, N):
visitable[N*i] = visitable[N*i-N] and A[N*i] % d == 0
for i in range(1, N):
for j in range(1, N):
a = A[N*i+j]
visitable[N*i+j] |= visitable[N*i + j - N] and a % d == 0
visitable[N*i+j] |= visitable[N*i + j - 1] and a % d == 0
if visitable[N*N-1]:
return d
assert False, "unreachable"
確認として求めた値で経路が復元できることを確かめたのですが、それ以上の値で経路が存在しないことを確認する必要がありました。
感想
SRMには久しぶりに参加しましたが、とても楽しいコンテストでした。どの問題もサンプルが強く、これ通ったらchallengeやること無いのでは？と思っているところに上記の落とし穴がありました。
今回のコンテストでレーティングは1197->1229と上昇しました。
ちなみにTopcoderには下記リンクのARENAから参加することが出来ます。興味がある方はぜひ参加してみて下さい。
www.topcoder.com
