SRM788 Div2 - matsu7874のブログ

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"