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

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

こんにちは, Shinoryoです.

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

A - Echo

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

B - Base 2

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

C - Centers

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

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

D - Poisonous Full-Course

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

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

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

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

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

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

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

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

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

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

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

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

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