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

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

こんにちは, Shinoryoです.

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

1A - Echo
2B - Base 2
3C - Centers
4D - Poisonous Full-Course
5E以降
6参考にしたサイト等

A - Echo

愚直に実装すれば問題ありません.

	N = int(input())
	S = list(input())

	print("".join([S[i // 2] for i in range(2*N)]))

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

B - Base 2

$\sum_{i = 0}^{63} A_{i} \times 2^{i}$ を求めればよいです.

	A = list(map(int, input().split()))
	print(sum(A[i] * (2**i) for i in range(len(A))))

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

C - Centers

実装方針は以下のようになります.

$A$ の要素を順に調べていく.
1. 整数 $i$ が出現した回数 $B_{i}$ を, 配列を利用して記録する.
2. ある整数 $i$ に対して $B_{i} = 2$ となったら, 出力順を記録する配列 $C$ に $i$ を追加する.

	# 入力
	N = int(input())
	A = list(map(int, input().split()))

	# Aの要素を順に調べていく
	# 今までの発生回数を記録
	appearance_count = [0 for _ in range(N + 1)]
	# 1～Nを出力する順にappendする用の配列
	ans = []

	for i in range(3 * N):
	appearance_count[A[i]] += 1
	# 発生回数が2回になったとき、ansにその整数をappendする
	if appearance_count[A[i]] == 2:
	ans.append(str(A[i]))

	# 出力
	print(" ".join(ans))

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

D - Poisonous Full-Course

ここでは, 動的計画法(dynamic programming)を用いることを考えます. 以下の2次元配列を用意して, 入れるべき値を計算していきます.

${dp}_{i, j}$ ：料理 $i$ までの料理を食べるか下げてもらうか選択したとき, 高橋くんが状態 $j$ である場合の, 食べた料理の美味しさの総和の最大値
状態 $j = 0$ ：高橋くんがお腹を壊していない状態
状態 $j = 1$ ：高橋くんがお腹を壊している状態

初期状態のため, ${dp}_{0, 0} = 0$ , ${dp}_{0, 1} = 0$ です. 次に運ばれてくる料理が解毒剤入り( $X_{i} = 0$ )のとき, この後高橋くんがお腹を壊さなかった場合の, 食べた料理の美味しさの総和の最大値は, 以下の3つの場合の最大値になります.

高橋くんがお腹を壊していない状態で, その料理を食べなかった( ${dp}_{i - 1, 0}$ ).
高橋くんがお腹を壊していない状態で, その料理を食べた( ${dp}_{i - 1, 0} + Y_{i}$ ).
高橋くんがお腹を壊している状態で, その料理を食べた( ${dp}_{i - 1, 1} + Y_{i}$ ).

次に運ばれてくる料理が解毒剤入り( $X_{i} = 0$ )のとき, この後高橋くんがお腹を壊した場合の, 食べた料理の美味しさの総和の最大値は, 以下の場合の値になります.

高橋くんがお腹を壊している状態で, その料理を食べなかった( ${dp}_{i - 1, 1}$ ).

次に運ばれてくる料理が毒入り( $X_{i} = 1$ )のとき, この後高橋くんがお腹を壊さなかった場合の, 食べた料理の美味しさの総和の最大値は, 以下の場合の値になります.

高橋くんがお腹を壊していない状態で, その料理を食べなかった( ${dp}_{i - 1, 0}$ ).

次に運ばれてくる料理が毒入り( $X_{i} = 1$ )のとき, この後高橋くんがお腹を壊した場合の, 食べた料理の美味しさの総和の最大値は, 以下の2つの場合の最大値になります.

高橋くんがお腹を壊していない状態で, その料理を食べた( ${dp}_{i - 1, 0} + Y_{i}$ ).
高橋くんがお腹を壊している状態で, その料理を食べなかった( ${dp}_{i - 1, 1}$ ).

以上のことを考慮して配列 $dp$ の値を計算していきます. 最終的に出力するべき値は, ${dp}_{N, 0}$ か ${dp}_{N, 1}$ のいずれか大きい方です.

	# 入力
	N = int(input())

	# 配列dpの初期状態
	dp = [[0, 0] for _ in range(N + 1)]

	# 配列dpを順番に計算
	for i in range(1, N + 1):
	X, Y = map(int, input().split())
	if X == 0:
	dp[i][0] = max(dp[i - 1][0], dp[i - 1][0] + Y, dp[i - 1][1] + Y)
	dp[i][1] = dp[i - 1][1]
	else:
	dp[i][0] = dp[i - 1][0]
	dp[i][1] = max(dp[i - 1][0] + Y, dp[i - 1][1])

	# 出力
	print(max(dp[N]))

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

動的計画法は, 他のページでも解説しています.

E以降

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

参考にしたサイト等

「解説 - トヨタ自動車プログラミングコンテスト2023#3(AtCoder Beginner Contest 306)」
Editorial - Toyota Programming Contest 2023#3（AtCoder Beginner Contest 306）
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

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

A - Echo

B - Base 2

C - Centers

D - Poisonous Full-Course

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