Home / Python /

サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219）をPythonで解く

投稿日：　

Atcoder Python

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

こんにちは, Shinoryoです.

今回はサイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219）を, Pythonで解いてみた結果を書き連ねていこうと思います.

Sciseed Programming Contest 2021（AtCoder Beginner Contest 219） - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A - AtCoder Quiz 2

素直に条件式を記述すればよいです.

B - Maritozzo

文字列$S_1$, $S_2$, $S_3$をリスト$S$に格納します. そして, 文字列$T$を1文字目から順に調べていき, 対応する文字列をリスト$S$から探してきて, 答えとなる文字列にくっつけていきます. 文字列をくっつける操作は, 普通の$+$でOKです.

C - Neo-lexicographic Ordering

sortにkeyを渡す方法

リストのsortメソッドやsorted()関数では, 引数keyに関数などを指定することができます. 例えば, key=absと設定すれば, 絶対値にした上でソートされることになります.

今回の場合keyには, ある文字列を引数にとり, 通常の辞書順で対応する文字に置き換える関数を指定します. 例えば, $X =$bacdefghijklmnopqrstuvwxzyならば, abxはbaxに置き換わります.

与えられた新しい辞書順と従来の辞書順の対応付けは, dict型を用いると便利です. キーのリストと値のリストから辞書を作成するには, 複数のリストなどの要素をまとめる関数であるzip()を用いることができます.

なんなら自分でソートしてやる方法(1)

やろうと思えば, 自分でソートすることができないわけではありません.

良く知られているソートアルゴリズムの1つに, バブルソート(bubble sort)があります.

リスト$S = [S_1, S_2, \ldots, S_N]$が与えられたときに, $S_1$と$S_2$を比べて$S_1 < S_2$となるように, $S_2$と$S_3$を比べて$S_2 < S_3$となるようにしていきます. 最後に, $S_{N - 1}$と$S_N$を比べて$S_{N - 1} < S_N$となるようにすることで, 最終的に$S_N$はその中で最も大きい要素になります.

これを再び繰り返します. $S_1$と$S_2$を比べて$S_1 < S_2$となるように, $S_2$と$S_3$を比べて$S_2 < S_3$となるようにしていきます. 最後に, $S_{N - 2}$と$S_{N - 1}$を比べて$S_{N - 2} < S_{N - 1}$となるようにすることで, 最終的に$S_{N - 1}$はその中で最も大きい要素になります.

これを最後まで繰り返せば, ソートが完了するというわけです.

図 バブルソートの概念図. これを繰り返すことによってソートする.

しかしながら, 計算量は$O(N^2)$かかってしまう方法なので, さすがにTLEです.

なんなら自分でソートしてやる方法(2)

比較的計算量が少ないソートアルゴリズムの1つに, マージソート(marge sort)があります.

あらかじめソートしてある2つのリストを合体させて, ソートされた新しいリストを得ることは難しくありません. それぞれのリストの先頭を比較して, 辞書順で小さい方を新リストに加えるという操作を繰り返せばよいだけです. これを利用したのが, マージソートになります.

マージソートは, 分割するフェーズと合体するフェーズの2つに分かれます. 分割するフェーズでは, 多くの場合, ほぼ2分割されるように分解していきます. 最終的にそれぞれ1つの要素しか含まないように分割した後に, それらを順に合体していきます(1つの要素しか含まないリストは, すでにソートされていると見なせます).

図 マージソートの概念図. 分割しまくった後, それらを互いにソートしつつ合体させていく.

分割や合体の回数が$O(\log N)$で, それぞれの分割や合体自体には最大で$O(N)$かかるので, 必要な計算量は$O(N \log N)$となります. これならACです.

D - Strange Lunchbox

動的計画法(dynamic programming)を用いて解くことを考えます.

動的計画法を用いて計算する量$\mathrm{dp}[i][j][k]$として, 以下の量を考えます.

  • $i$種類目までの弁当を購入するか否かを決定したときに, $j$個のたこ焼きと$k$個のたい焼きを購入するために買うべき弁当の個数の最小値

$0$種類目までの弁当を購入するか否かを決定したときに, $0$個のたこ焼きと$0$個のたい焼きを購入するために買うべき弁当の個数の最小値は当然$0$なので, 初期値として$\mathrm{dp}[0][0][0]= 0$としておきます.

$\mathrm{dp}[i][j][k]$が正しく入力されているとき, $i + 1$番目の弁当を買うか買わないかの選択とすることができます.

  1. 買う場合：新たに$A[i]$個のたこ焼きと$B[i]$個のたい焼きを獲得することになります.
    $\mathrm{dp}[i + 1][\min(j + A[i], X)][\min(k + B[i], Y)]$を$\mathrm{dp}[i][j][k] + 1$で更新します(小さい方の値にする).
  2. 買わない場合：新たにたこ焼きやたい焼きは増えません.
    $\mathrm{dp}[i + 1][j][k]$を$\mathrm{dp}[i][j][k]$で更新します(小さい方の値にする).

$\mathrm{dp}[i][j][k]$が正しく入力されていない(適切な初期値のままの)場合は, $i$種類目までの弁当を購入するか否かを決定していくプロセスでは, $j$個のたこ焼きと$k$個のたい焼きを獲得することができないということになるので, そのままにしておきます.

最後に出力すべきなのは, $\mathrm{dp}[N][X][Y]$になります. 初期値のままの場合は$-1$を出力することに注意してください.

初期値については, 例えば$N + 1$($N + 1$個以上の弁当を買うことにはなりません)などが適切でしょう.

E以降

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

参考にしたサイト等