ABC257の振り返り(A, B, C, D)

遅ればせながら、2022/06/25に開催されたABCの振り返りです。

このコンテストで初めてC問題までACできたんだよね😁

NS Solutions Corporation Programming Contest 2022(AtCoder Beginner Contest 257) - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

テスト関数定義↓

# 縮小表示 from copy import deepcopy def test_all(f): for i, data in enumerate(eval(f'test_data{f.__name__[0]}')): exp = data["out"] ans = f(*deepcopy(data["in"])) result = "AC" if exp == ans else "WA" print(f"{i+1} {result}: expected: {exp}, output: {ans}")

A - A to Z String 2

A - A to Z String 2

やってみよう!

A関数を完成させて「Run」ボタンをクリックしよう!

test_dataA = [ { "in":[1, 3], "out": "C" },{ "in":[2, 12], "out": "F" }, ] def A(N, X): pass test_all(A)

自由欄

try

from string import * def A(N, X): d, m = divmod(X, N) if not m: d -= 1 return ascii_uppercase[d] test_all(A)

結果:提出 #32830397

try2

解説参照。
先にX-1しといたほうが簡単だな…

from string import * def A(N, X): return ascii_uppercase[(X-1)//N] test_all(A)

結果:提出 #32830728

自由欄

B - 1D Pawn

B - 1D Pawn

やってみよう!

B関数を完成させて「Run」ボタンをクリックしよう!

test_dataB = [ { "in":[5, 3, 5, [1, 3, 4], [3, 3, 1, 1, 2]], "out": [2, 4, 5] },{ "in":[2, 2, 2, [1, 2], [1, 2]], "out": [1, 2] },{ "in":[10, 6, 9, [1, 3, 5, 7, 8, 9], [1, 2, 3, 4, 5, 6, 5, 6, 2]], "out": [2, 5, 6, 7, 9, 10] }, ] def B(N, K, Q, A, L): pass test_all(B)

自由欄

try

def B(N, K, Q, A, L): for l in L: if A[l-1] == N: continue elif l == K: pass elif A[l-1]+1 == A[l]: continue A[l-1] += 1 return A test_all(B)

結果:提出 #32831103

自由欄

C - Robot Takahashi

C - Robot Takahashi

やってみよう!

C関数を完成させて「Run」ボタンをクリックしよう!

test_dataC = [ { "in":[5, '10101', [60, 45, 30, 40, 80]], "out": 4 },{ "in":[3, '000', [1, 2, 3]], "out": 3 },{ "in":[5, '10101', [60, 50, 50, 50, 60]], "out": 4 }, ] def C(N, S, W): pass test_all(C)

自由欄

try

コンテスト中にACした提出はインデックスの扱いがちょっと分かりづらくなってしまったので、以下のように修正。

from itertools import accumulate def C(N, S, W): S = [int(s) for s in S] W, S = zip(*sorted(zip(W, S))) *S, = accumulate(S) # 「全員大人」判定 ans = S[-1] # i と i+1 の間で区切る。最後は「全員子供」判定 for i, (w, s) in enumerate(zip(W, S)): if i != N-1 and w == W[i+1]: continue ans = max(ans, i+1-s + S[-1]-s) return ans test_all(C)

結果:提出 #32831702

try2

上のコードでループしなくても良くない?でも体重が同じ場合の扱いが難しいな~
と思いながらユーザー解説を見る。

体重で昇順ソートをして、大人子供設定は降順ソートする
この状態ではより良い結果を出すためには境界線を先頭か末尾に入れるしかなくなる
Robot Takahashi [日鉄ソリューションズプログラミングコンテスト2022(AtCoder Beginner Contest 257) C] - はまやんはまやんはまやん

ほほ~。これならループさせずにいけそう!
ということで以下。

from itertools import accumulate def C(N, S, W): S = [int(s) for s in S] W, S = zip(*sorted( sorted(zip(W, S), key=lambda ws:ws[1], reverse=True), key=lambda ws: ws[0])) *S, = accumulate(S) return max([i - 2*s for i, s in enumerate(S)]+[-1]) + 1 + S[-1] test_all(C)

結果:提出 #32832344

いけた~
けど、このコードからだと何やってるかさっぱり分からんな…
ていうか、内包表記も実質ループだしな…

自由欄

try3

別解としてaccumulateを使わない方法。
並べ替えた後$X$を一人分ずつ増やしていき、新たに子供判定となる人が実際に子供なら一つ前の$f(X)$に+1、そうでなければ-1する。

def C(N, S, W): data = sorted(zip(W, S)) data.append([None, None]) # 番兵 ans = [S.count("1")] cnt = 0 for i in range(N): cnt = cnt + (1 if data[i][1] == "0" else -1) if data[i][0] == data[i+1][0]: continue ans.append(ans[-1] + cnt) cnt = 0 return max(ans) test_all(C)

結果:提出 #33418954

自由欄

D - Jumping Takahashi 2


D - Jumping Takahashi 2

やってみよう!

D関数を完成させて「Run」ボタンをクリックしよう!

test_dataD = [ # input format: [N, [[x, y, P]]] { "in":[4, [[-10, 0, 1], [0, 0, 5], [10, 0, 1], [11, 0, 1]]], "out": 2 },{ "in":[7, [[20, 31, 1], [13, 4, 3], [-10, -15, 2], [34, 26, 5], [-2, 39, 4], [0, -50, 1], [5, -20, 2]]], "out": 18 }, ] def D(N, points): pass test_all(D)

自由欄

try1

コンテスト中はC問題をACした後に10分ぐらいしか残ってなかったので、ぼーっと問題文を眺めただけでした😅

考えてもよく分からんのでいそいそと解説を見てみます。(6つもある!)

最初の解説によると、

  • 訓練を行う回数で二分探索
  • $N$頂点、$XP_i \ge |x_i - x_j| + |y_i - y_j|$ならば頂点$i$から頂点$j$へ有向辺を貼ったグラフを用意
  • 最初のジャンプ台をどこにするかは全探索。その始点から全ての頂点に到達できるかは BFS。

とのこと。

まだよくイメージできないのでとりあえず実装してみます。
処理の流れとしては6つ目の解説と大体一緒ですが、せっかくなのでジャンプ台の情報をクラス化してみました。

from collections import deque def D(N, points): class P(): items = [] distances = {} @staticmethod def get_dist(a, b): return abs(a.x - b.x) + abs(a.y - b.y) def __init__(self, x, y, p): self.x = x self.y = y self.p = p CLASS = self.__class__ now = len(CLASS.items) for i, item in enumerate(CLASS.items): d = CLASS.get_dist(self, item) CLASS.distances[(now, i)] = d CLASS.distances[(i, now)] = d CLASS.items.append(self) def __repr__(self): return f'({self.x}, {self.y}), {self.p}' def bfs(start, x): q = deque([start]) visited = [start] while len(q): now = q.popleft() for to in range(N): if now != to and to not in visited and P.items[now].p * x >= P.distances[(now, to)]: q.append(to) visited.append(to) return True if len(visited) == N else False def is_connected(x): for i in range(N): if bfs(i, x): return True return False for point in points: P(*point) ok = max(P.distances.values()) ng = -1 while abs(ok - ng) > 1: mid = (ok + ng) // 2 if is_connected(mid): ok = mid else: ng = mid return ok test_all(D)

結果:TLE

切ないほどのTLEです。
ちょっと修正するとTLEを12個まで減らせたりしますが、それでもこの数は根本的な間違いを示唆しています。(C++とかならいけんのかなぁ…?)

自由欄

try2

改めて最初の解説を確認してみましょう。(再掲)

  • 訓練を行う回数で二分探索
  • $N$頂点、$XP_i \ge |x_i - x_j| + |y_i - y_j|$ならば頂点$i$から頂点$j$へ有向辺を貼ったグラフを用意
  • 最初のジャンプ台をどこにするかは全探索。その始点から全ての頂点に到達できるかは BFS。

グラフ作んのが先か!!!

そうなんです、ちゃんと書いてあったのです。
上の実装では、任意の訓練回数で「ある始点から全ての頂点に到達できるかどうか」判定する際、全ての頂点を始点として全探索する度にグラフを作っていることになります(35行目)。
しかしながら、訓練回数が決まっていればどの頂点を始点にしようとグラフ自体は変わらないので、先に作っておけばよいということになります。

from collections import deque from itertools import chain def D(N, points): class P(): items = [] distances = [[0]*N for _ in range(N)] @staticmethod def get_dist(a, b): return abs(a.x - b.x) + abs(a.y - b.y) def __init__(self, x, y, p): self.x = x self.y = y self.p = p CLASS = self.__class__ now = len(CLASS.items) for i, item in enumerate(CLASS.items): d = CLASS.get_dist(self, item) CLASS.distances[now][i] = d CLASS.distances[i][now] = d CLASS.items.append(self) def __repr__(self): return f'({self.x}, {self.y}), {self.p}' def bfs(graph, start): q = deque([start]) visited = set([start]) while q: now = q.popleft() for to in graph[now]: if to not in visited: q.append(to) visited.add(to) return True if len(visited) == N else False def is_connected(x): graph = [[] for i in range(N)] for i in range(N-1): for j in range(i+1, N): if P.items[i].p * x >= P.distances[i][j]: graph[i].append(j) if P.items[j].p * x >= P.distances[i][j]: graph[j].append(i) for i in range(N): if bfs(graph, i): return True return False for point in points: P(*point) ok = max(set(chain.from_iterable(P.distances))) ng = -1 while abs(ok - ng) > 1: mid = (ok + ng) // 2 if is_connected(mid): ok = mid else: ng = mid return ok test_all(D)

Diffは以下の通り。

色々試行錯誤したところ、上述の「先にグラフ作る」の修正だけで普通にACとなりました。
加えて、dictとして保持していたdistancesの情報をlistにすることで、数百ms短縮されました。

# 縮小表示 from difflib import HtmlDiff as diff from urllib.parse import quote tobecompared = { "fromlines": ''' from collections import deque def D(N, points): class P(): items = [] distances = {} @staticmethod def get_dist(a, b): return abs(a.x - b.x) + abs(a.y - b.y) def __init__(self, x, y, p): self.x = x self.y = y self.p = p CLASS = self.__class__ now = len(CLASS.items) for i, item in enumerate(CLASS.items): d = CLASS.get_dist(self, item) CLASS.distances[(now, i)] = d CLASS.distances[(i, now)] = d CLASS.items.append(self) def __repr__(self): return f'({self.x}, {self.y}), {self.p}' def bfs(start, x): q = deque([start]) visited = [start] while len(q): now = q.popleft() for to in range(N): if now != to and to not in visited and P.items[now].p * x >= P.distances[(now, to)]: q.append(to) visited.append(to) return True if len(visited) == N else False def is_connected(x): for i in range(N): if bfs(i, x): return True return False for point in points: P(*point) ok = max(P.distances.values()) ng = -1 while abs(ok - ng) > 1: mid = (ok + ng) // 2 if is_connected(mid): ok = mid else: ng = mid return ok '''.splitlines(), "tolines": ''' from collections import deque from itertools import chain def D(N, points): class P(): items = [] distances = [[0]*N for _ in range(N)] @staticmethod def get_dist(a, b): return abs(a.x - b.x) + abs(a.y - b.y) def __init__(self, x, y, p): self.x = x self.y = y self.p = p CLASS = self.__class__ now = len(CLASS.items) for i, item in enumerate(CLASS.items): d = CLASS.get_dist(self, item) CLASS.distances[now][i] = d CLASS.distances[i][now] = d CLASS.items.append(self) def __repr__(self): return f'({self.x}, {self.y}), {self.p}' def bfs(graph, start): q = deque([start]) visited = set([start]) while q: now = q.popleft() for to in graph[now]: if to not in visited: q.append(to) visited.add(to) return True if len(visited) == N else False def is_connected(x): graph = [[] for i in range(N)] for i in range(N-1): for j in range(i+1, N): if P.items[i].p * x >= P.distances[i][j]: graph[i].append(j) if P.items[j].p * x >= P.distances[i][j]: graph[j].append(i) for i in range(N): if bfs(graph, i): return True return False for point in points: P(*point) ok = max(set(chain.from_iterable(P.distances))) ng = -1 while abs(ok - ng) > 1: mid = (ok + ng) // 2 if is_connected(mid): ok = mid else: ng = mid return ok '''.splitlines()} f'''''' # 縮小表示 diff().make_file(**tobecompared)

自由欄

他の解法

今回はもう力尽きたので、他の解説などで言及されているワーシャルフロイド法ダイクストラ法については別記事でまとめたいと思います😇

まとめ

コンテストから日が経つと振り返り作業がつらい…

自由欄