ABC298の振り返り(B, C, D)

Arakaki Tokyo -

振り返りです。

TOYOTA MOTOR CORPORATION Programming Contest 2023#1 (AtCoder Beginner Contest 298) - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
AtCoderAtCoder Inc.
import sys from io import StringIO input = lambda: sys.stdin.readline()[:-1] def test(f, data): stdin = sys.stdin stdout = sys.stdout sys.stdin = StringIO(data["in"]) out = StringIO() sys.stdout = out err = None try: f() except BaseException as e: err = e else: ans = out.getvalue() exp = data["out"] sys.stdin = stdin sys.stdout = stdout if err: raise err result = "AC" if exp == ans else "WA" print(f"{result}: expected: {exp}, output: {ans}") def test_all(f): for i, data in enumerate(eval(f'test_data{f.__name__[0]}'), 1): print(f"case {i}") test(f, data)

B - Coloring Matrix

やってみよう！

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

test_dataB = [ { "in":"""3 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 1 1 1 """, "out": """Yes """ },{ "in":"""2 0 0 0 0 1 1 1 1 """, "out": """Yes """ },{ "in":"""5 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 1 0 1 0 """, "out": """No """ }, ] def B(): pass test_all(B)

自由欄

振り返り

コンテスト中は設問通りに実装しましたが、『回転』という処理で言えばnumpyにそのものズバリの関数があったなぁと振り返って気づきました。
A, Bの取りうる値は0, 1なので判定もカンタンですね。

def B(): import numpy as np N = int(input()) A = np.array([list(map(int, input().split())) for _ in range(N)]) B = np.array([list(map(int, input().split())) for _ in range(N)]) for _ in range(4): if np.all(B-A>-1): print("Yes") break A = np.rot90(A) else: print("No") test_all(B)

結果：#40824816

自由欄

線形代数(？)っぽく解く

文系出身なのでここらへんコンプレックスなのですが、サクッと行列の演算で処理できたらカッコいいですよね！
…考えても全然分からんのでググって以下参考にしました😇

matrices - How to rotate the positions of a matrix by 90 degrees - Mathematics Stack Exchange

転置して行を逆順にすれば90度回転になるのか。なんかあんまり行列の演算っぽくはないですね😩

import numpy as np def B(): N = int(input()) A = np.array([list(map(int, input().split())) for _ in range(N)]) B = np.array([list(map(int, input().split())) for _ in range(N)]) for _ in range(4): if np.all(B-A>-1): print("Yes") break A = A.T[::-1] else: print("No") test_all(B)

結果：#40895995

自由欄

解説を見る

ユーザ解説で紹介されている通り、「転置して行を逆順にする」なら生のPythonでも短く書けます。

A = np.arange(9).reshape(3, -1) print(A) print(np.array([a[::-1] for a in zip(*A)]))

C - Cards Query Problem

やってみよう！

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

test_dataC = [ { "in":"""5 8 1 1 1 1 2 4 1 1 4 2 4 1 1 4 2 4 3 1 3 2 """, "out": """1 2 1 1 2 1 4 4 """ },{ "in":"""1 5 1 1 1 1 2 1 1 200000 1 2 1 3 200000 """, "out": """1 2 200000 1 """ }, ] def C(): pass test_all(C)

自由欄

コンテスト中

競プロ初めてもうすぐ1年になりますが、相変わらずアホみたいなミスと言うか、自分で「なんで！？」と突っ込みたくなるようなコーディングしてハマってしまってます…
本問もWA, TLEで終わってしまったのですが、とりあえずコンテスト中に提出した中で一番ましなのが以下。

def C(): from collections import defaultdict from bisect import bisect N = int(input()) Q = int(input()) box = defaultdict(list) card = defaultdict(list) for _ in range(Q): idx, *args = input().split() if idx == "1": i, j = args box[j].append(i) card[i].append(j) #print(box) #print(card) elif idx == "2": print(*sorted(box[args[0]])) elif idx == "3": print(*sorted(set(card[args[0]]))) test_all(C)

結果：#40660450

自由欄

振り返り

まずアホみたいなところから修正しましょう。
上コードでは11行目のidx, *args = input().split()です。

なんで文字列のまま受け取ってんねん！！！！！！

箱の数、カードの数ともに$\le 2 \times 10^5$なので文字列のまま大小比較できるわけがありません。
なんで今更こんなミスするかな…

もう一つ、3番目のクエリにおいてカードが入っている箱は重複を除いて出力するので、情報として保持する時点でユニークにしておけばいいです。(9行目)

以上2つを修正したのが以下。

def C(): from collections import defaultdict N = int(input()) Q = int(input()) box = defaultdict(list) card = defaultdict(set) for _ in range(Q): idx, *args = map(int, input().split()) if idx == 1: i, j = args box[j].append(i) card[i].add(j) elif idx == 2: print(*sorted(box[args[0]])) elif idx == 3: print(*sorted(card[args[0]])) test_all(C)

結果：#40825330

無事AC…はぁ😩

自由欄

D - Writing a NumeralD - Writing a Numeral

やってみよう！

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

test_dataD = [ { "in":"""3 3 1 2 3 """, "out": """1 12 """ },{ "in":"""3 1 5 2 3 """, "out": """5 """ },{ "in":"""11 1 9 1 9 1 8 1 2 1 4 1 4 1 3 1 5 1 3 2 3 """, "out": """0 """ }, ] def D(): pass test_all(D)

自由欄

振り返り

これは純粋に実力不足。コンテスト中の愚直解は当然TLE(& RE)となったので解説を見てやり直したのが以下。

def D(): from collections import deque M = 998244353 Q = int(input()) S = deque("1") ans = 1 for _ in range(Q): idx, *args = input().split() if idx == "1": ans = ans * 10 + int(args[0]) ans %= M S.append(args[0]) elif idx == "2": sub = int(S.popleft()) * pow(10, len(S), M) ans -= sub ans %= M else: print(ans) test_all(D)

結果：#40826483

自由欄

自由欄