トヨタ自動車プログラミングコンテスト2023#1(AtCoder Beginner Contest 298)をPythonで解く-Shinoryo's Weblog

Daniel AgreloによるPixabay(https://pixabay.com/)からの画像

こんにちは, Shinoryoです.

今回はトヨタ自動車プログラミングコンテスト2023#1(AtCoder Beginner Contest 298)を, Pythonで解いてみた結果を書き連ねていこうと思います.

1A - Job Interview
2B - Coloring Matrix
3C - Cards Query Problem
4D - Writing a Numeral
- 4.1なぜpow()の方が速いのか？
5E以降
6参考にしたサイト等

A - Job Interview

面接官の評価「良」の数を $A$ , 面接官の評価「良」の不可の数を $B$ とすると, Yesとなる条件は $A \geq 1$ かつ $B = 0$ となります.

	# 入力
	N = int(input())
	S = input()

	# 良、可、不可の数を調査
	ryou = sum(1 for s in S if s == "o")
	fuka = sum(1 for s in S if s == "x")

	# 出力
	if ryou >= 1 and fuka == 0:
	print("Yes")
	else:
	print("No")

view raw atcoder-abc-298-a.py hosted with ❤ by GitHub

B - Coloring Matrix

行列 $A$ を適切に回転したものと行列 $B$ とを比べる問題です. 行列 $A$ を回転することによりできる行列には, 以下の4つがあります.

行列 $A$
行列 $A$ を反時計回りに $90^{\circ}$ 回転させたもの
行列 $A$ を反時計回りに $180^{\circ}$ 回転させたもの
行列 $A$ を反時計回りに $270^{\circ}$ 回転させたもの

したがって, 上記4つの行列と行列 $B$ とをそれぞれ比べればよいことが分かります.

Pythonでは2次元配列の回転は, numpyのnp.rot90を用いることで簡単に実装できます. また, $A_{i, j} = 1$ である全ての $(i, j)$ に対して $B_{i, j} = 1$ であるかどうかを確かめるには, 行列 $B - A$ の最小値が $0$ 以上であるかどうかを調べればよいことも分かります.

	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)])

	# 0～3回回転させて、「Aが1ならばBが1」が成り立つか確認
	# BからA_rotを引いたものに-1が含まれていれば、「Aが1なのにBが0」ということ(以外ありえない)
	for l in range(4):
	if np.min(B - A) >= 0:
	print("Yes")
	exit(0)
	A = np.rot90(A)
	print("No")

view raw atcoder-abc-298-b.py hosted with ❤ by GitHub

配列の回転を愚直に実装することもできます.

	# N×Nの配列list2Dを反時計回りに90度回転させる関数
	def list2D_rot90(list2D, N):
	rot90_list2D = [[0] * N for _ in range(N)]
	for i in range(N):
	for j in range(N):
	rot90_list2D[N - j - 1][i] = list2D[i][j]
	return rot90_list2D

	# 入力
	N = int(input())
	A = [list(map(int, input().split())) for _ in range(N)]
	B = [list(map(int, input().split())) for _ in range(N)]

	# 0～3回回転させて、「Aが1ならばBが1」が成り立つか確認
	# BからA_rotを引いたものに-1が含まれていれば、「Aが1なのにBが0」ということ(以外ありえない)
	for l in range(4):
	ok = True
	for i in range(N):
	for j in range(N):
	if B[i][j] - A[i][j] < 0:
	ok = False
	if ok:
	print("Yes")
	exit(0)
	A = list2D_rot90(A, N)
	print("No")

view raw atcoder-abc-298-b-2.py hosted with ❤ by GitHub

C - Cards Query Problem

実装手法自体はシンプルです. 配列 ${box}_{i} (1 \leq i \leq N)$ を用意し, ここには箱 $i$ に入っているカードの番号を格納します. また, 配列 ${card}_{j} (1 \leq j \leq 200000)$ を用意し, ここにはカード $j$ が少なくとも1枚入っている箱の番号を格納します.

クエリ $1 i j$
1. ${box}_{i}$ に $j$ を格納する.
2. ${card}_{j}$ に $i$ が含まれていなければ, ${card}_{j}$ に $i$ を格納する.
クエリ $2 i$
1. ${box}_{i}$ を昇順にソートしたものを出力する.
クエリ $3 i$
1. ${card}_{i}$ を昇順にソートしたものを出力する.

	# 入力
	N = int(input())
	Q = int(input())

	# N個の箱の用意
	box = [[] for _ in range(N + 1)]
	# ある番号が格納されている箱の数を格納
	card = [[] for _ in range(200000 + 1)]

	# クエリの処理
	for i in range(Q):
	query = list(map(int, input().split()))
	if query[0] == 1:
	box[query[2]].append(query[1])
	if query[2] not in card[query[1]]:
	card[query[1]].append(query[2])
	elif query[0] == 2:
	print(" ".join(list(map(str, sorted(box[query[1]])))))
	else:
	print(" ".join(list(map(str, sorted(card[query[1]])))))

view raw atcoder-abc-298-c.py hosted with ❤ by GitHub

クエリ $1$ のたびにソートを行ってしまうとTLEです.

	import bisect

	# 入力
	N = int(input())
	Q = int(input())

	# N個の箱の用意
	box = [[] for _ in range(N + 1)]
	# ある番号が格納されている箱の数を格納
	card = [[] for _ in range(200000 + 1)]

	# クエリの処理
	for i in range(Q):
	query = list(map(int, input().split()))
	if query[0] == 1:
	bisect.insort_left(box[query[2]], query[1])
	if query[2] not in card[query[1]]:
	bisect.insort_left(card[query[1]], query[2])
	elif query[0] == 2:
	print(" ".join(list(map(str, box[query[1]]))))
	else:
	print(" ".join(list(map(str, card[query[1]]))))

view raw atcoder-abc-298-c-tle.py hosted with ❤ by GitHub

D - Writing a Numeral

基本的には, 各クエリの処理に対して忠実になればよいです. 以下, 文字列 $S$ を整数型の配列として格納したものを $S$ , 整数型として格納したものを $ans$ のようにします(例えば, $S$ は[1,2,3,4,5], $ans$ は12345のようになります).

クエリ $1 x$
- $ans = ans \times 10 + x$
- $S$ の末尾に $x$ を追加
クエリ $2$
- $S$ の要素数を取得し, これを $l$ とする
- $S$ の先頭の要素を削除し, これを $y$ とする
- $ans = ans - y * 10^{l}$
クエリ $3$
- $ans$ を出力する

$\mod = 998244353$ で割った余りを求めることを忘れないようにすることに注意しましょう. あとは高速化のためにいくつかの点に注意するだけです.

配列 $S$ は先頭または末尾にしかアクセスしないので, collectionsモジュールのdeque型を用いるとよい.
$10^{l}$ を求める際に, これがあまりにも大きくなってしまうので, $\mod$ で割った余りにしてとよい. これを効率よく求めるために, Pythonの組み込み関数のpow()を用いることができる.

	from collections import deque

	# 入力
	Q = int(input())
	S = deque([1])
	ans = 1
	mod = 998244353

	# 各クエリを順に処理する
	for _ in range(Q):
	query = list(map(int, input().split()))
	if query[0] == 1:
	S.append(query[1])
	ans = (ans * 10 + query[1]) % mod
	elif query[0] == 2:
	ans = (ans - pow(10, len(S) - 1, mod) * S.popleft()) % mod
	else:
	print(ans)

view raw atcoder-abc-298-d.py hosted with ❤ by GitHub

なぜ`pow()`の方が速いのか？

pow()の方が速いのは, 繰り返し2乗法と呼ばれる方法が実装されているからです. 例えば, $10^{7}$ を

\begin{aligned} (1) & 10^{7} & = 10 \times 10 \times 10 \times 10 \times 10 \times 10 \times 10 \end{aligned}

のようにしてしまうと, 指数を $N$ として計算量が $O (N)$ になってしまいます. ここで, $7 = 2^{2} + 2^{1} + 2^{0}$ であることに着目すると,

\begin{aligned} (2) & 10^{2^{0}} & = 10, \\ (3) & 10^{2^{1}} & = 10 \times 10, \\ (4) & 10^{2^{2}} & = 10^{2^{1}} \times 10^{2^{1}}, \\ (5) & 10^{2^{2} + 2^{1} + 2^{0}} & = 10^{2^{2}} \times 10^{2^{1}} \times 10^{2^{0}} \end{aligned}

のよう計算することができます. このようにすることで, 指数を $N$ として計算量を $O (\log N)$ に減らすことができます.

E以降

E以降は私の能力不足故に省略いたします.

参考にしたサイト等

「解説 - トヨタ自動車プログラミングコンテスト2023#1(AtCoder Beginner Contest 298)」
Editorial - TOYOTA MOTOR CORPORATION Programming Contest 2023#1 (AtCoder Beginner Contest 298)
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
nkmk様による「Pythonのdequeでキュー, スタック, デック（両端キュー）を扱う」
Pythonのdequeでキュー, スタック, デック（両端キュー）を扱う | note.nkmk.me
Pythonの標準ライブラリcollectionsモジュールのdeque型を使うと, データをキューやスタック, デック（両端キュー）として効率的に扱うことができる. collections.deque --- コンテナデータ型 — Python 3.7.3 ドキュメント組み込みのリストlistをキューやスタック, デック（両端キュー）として使うことも可能だが, リスト...
nkmk様による「Pythonで指数関数・対数関数を計算（exp, log, log10, log2）」
Pythonで指数関数・対数関数を計算（exp, log, log10, log2） | note.nkmk.me
Pythonの数学関数の標準モジュールmathを使うと, 指数関数および対数関数（自然対数, 常用対数, 二進対数）の計算ができる. 9.2. math — 数学関数指数関数と対数関数 — Python 3.6.4 ドキュメントここでは, 自然対数の底（ネイピア数）: math.e べき乗: **演算子, pow(), math.pow() 平方根（ルート）: math.sqrt() 指...
「繰り返し2乗法, 行列累乗」
繰り返し2乗法, 行列累乗 - Qiita
繰り返し2乗法繰り返し2乗法とは, 指数を2の累乗の積に分解し, 計算を効率化するテクニック. 例えば, $3^{50}$ が与えられたとき, $50 = 2^{5} + 2^{4} + 2^{1}$ と表せるため, $3^{50} = 3^{2^{...

トヨタ自動車プログラミングコンテスト2023#1(AtCoder Beginner Contest 298)をPythonで解く

A - Job Interview

B - Coloring Matrix

C - Cards Query Problem

D - Writing a Numeral

なぜ`pow()`の方が速いのか？

E以降

参考にしたサイト等

0 件のコメント:

コメントを投稿 (Please feel free to ask me about your questions! You can use Japanese or English in the comments.)

Search

About Me

Labels

Blog Archives

Twitter

トヨタ自動車プログラミングコンテスト2023#1(AtCoder Beginner Contest 298)をPythonで解く

A - Job Interview

B - Coloring Matrix

C - Cards Query Problem

D - Writing a Numeral

なぜpow()の方が速いのか？

E以降

参考にしたサイト等

0 件のコメント:

コメントを投稿 (Please feel free to ask me about your questions! You can use Japanese or English in the comments.)

Search

About Me

Labels

Blog Archives

Twitter

なぜ`pow()`の方が速いのか？