TopCoder SRM 788 Div.2 感想
初めてのTopCoder．運がよかったのか青になった．やったね．
TopCoderのSRMは，AtCoderやCodeForcesよりもコンテストサイトがわかりにくかったり，入出力の形式が違ったりで少し参加しにくかったです．事前に過去問を解いたり，最初の一回目は慣れのために手探りでやったり，みたいなことが必要かもしれません．
かっつさんの記事を参考に環境構築．昔から使われている方がいいかもしれない，と思ってjavaappletを入れて参戦しました（ただコンテスト終了後のTLを見た感じweb arenaで参加していた人も多かったみたい？web arena参加した人でコンテスト中に困ったことがあった人もいなさそうだった）．
コンテストの説明とかも書こうと思ったけれど，かっつさんの記事に書いてあるからそっちを読めばいいですね…（？）． あとはコンテスト前に参考になった診断人さんのリツイートやtatyamさんのツイートを置いておきます．
Python2系について詳しくないんですが，なんか普段通りPython 3の気持ちで書いても動きました（？）．かっつさんの記事の紹介にあるGreedというプラグインのおかげで，勝手にクラスやテストコードが生成されたのがありがたかったです（最初デバッグ方法がわかりませんでしたが）．ただし，提出前にテストコードを消すのを忘れないようにしましょう．Challenge phaseやSystem Testがあるので，いつも以上に与えられる入力でバグらないかをチェックしてから出すといい気がします．Python使いの人で，普段クラスを書かない人（僕など）はクラスの書き方も確認しておきましょう（selfつけるの忘れないとか）．
以下問題ごとの感想とコードです．
NextOlympics（easy）
テストコード貼り付けたまま一回提出してもったいなかったです． Pythonにはdatetimeモジュールがあるので，これを使いました． whileを回しましたが，2021.07.23と差分を取るだけでよかったですね．
ACコード
# -*- coding: utf-8 -*-
import datetime
class NextOlympics:
def countDays(self, today):
A = today
T = datetime.date(int(A[0:4]), int(A[5:7]), int(A[8:]))
y, m, d = T.year, T.month, T.day
ans = 0
while not (y == 2021 and m == 7 and d == 23):
T += datetime.timedelta(days=1)
ans += 1
y, m, d = T.year, T.month, T.day
return ans
StarsInTheSky（medium）
いくつか座標が与えられて，条件を満たす部分集合を数え上げる問題です．サンプル1を見て問題を理解しました． bit全探索をすぐにやればよかったんですけど，ちょっともたもたしてしまい…うー，もったいない． ある星の組合せに対して，それ以外の星を含まないような長方形にできているかを毎回チェックして数えました．
ACコード
# -*- coding: utf-8 -*-
class StarsInTheSky:
def countPictures(self, N, X, Y):
ans = 0
for bit in range(1, 1 << N):
cur_not = []
XL = 1000000005
XR = -1
YL = 1000000005
YR = -1
for i in range(N):
if bit & (1 << i):
if XL > X[i]:
XL = X[i]
if XR < X[i]:
XR = X[i]
if YL > Y[i]:
YL = Y[i]
if YR < Y[i]:
YR = Y[i]
else:
cur_not.append(i)
flag = True
for i in cur_not:
if XL <= X[i] <= XR and YL <= Y[i] <= YR:
flag = False
break
if flag:
ans += 1
return ans
SquareCityWalking（hard）
サンプルは通ったんですけど，システスで落ちました（えーん）． 適当にダイクストラしたんですけど，うーん．なんか間違えたらしい．明日復習します．
WAコード
# -*- coding: utf-8 -*-
from heapq import heapify, heappop, heappush
class SquareCityWalking:
def gcd(self, x, y):
if y == 0:
return x
while y != 0:
x, y = y, x % y
return x
def largestGCD(self, N, A):
A = list(A)
g = self.gcd(A[0], A[(N-1)*N+(N-1)])
for i in range(N):
for j in range(N):
v = self.gcd(g, A[i*N+j])
A[i*N+j] = v
d = [[0 for j in range(N)] for i in range(N)]
d[0][0] = g
que = [(-d[0][0], (0, 0))]
heapify(que)
finished = set()
dyx = ((0, 1), (1, 0))
while que:
u = heappop(que)
u = (-u[0], u[1])
while que and u[1] in finished:
u = heappop(que)
for dy, dx in dyx:
next_y = u[1][0] + dy
next_x = u[1][1] + dx
v = (next_y, next_x)
if not(0 <= next_y < N and 0 <= next_x < N):
continue
if v in finished:
continue
if d[v[0]][v[1]] < self.gcd(u[0], A[v[0]*N+v[1]]):
d[v[0]][v[1]] = self.gcd(u[0], A[v[0]*N+v[1]])
heappush(que, (-d[v[0]][v[1]], v))
finished.add(u[1])
return d[N-1][N-1]
公式解説はココ．
