AtCoder Beginner Contest 210をPythonで解く

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 210を, Pythonで解いてみた結果を書き連ねていこうと思います.

AtCoder Beginner Contest 210 - AtCoder

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

A - Cabbages

$N \leq A$の場合, 全てのキャベツが$1$個$X$円で購入できるので, 合計金額は$NX$円です.

$N > A$の場合, $A$個のキャベツが$1$個$X$円で購入出来て, $N - A$個のキャベツが1個$Y$円で購入できるので, 合計金額は$AX + (N-A)Y$円です.

以上から, どちらの場合も合計金額を$\mathrm{min} \, (N, A) \times X + \, \mathrm{max} \, (0, N-A) \times Y$円と書けます.

B - Bouzu Mekuri

文字列$S$の先頭から見て初めて$1$が現れる場所を$X$文字目とします(ただし, 先頭から$0$文字目, $1$文字目と数えることとし, これはインデックスにそのまま一致します). $X$が偶数ならばそのカードを高橋君が食べ, $X$が奇数ならばそのカードを青木君が食べることになります.

文字列$S$にある文字が含まれるかどうかを探索するには, .find()を使用することができます. .find()を使う場合, 先頭から探索します.

.find()を使わなくても, 明示的に探索の操作を行えばよいです.

C - Colorful Candies

1つの区間に含まれるキャンディの色の種類数を求めるには 「区間内の$K$個のキャンディを一つずつ見て, 区間内の色の種類数を数える」という方法が考えられます. しかし, これだと時間計算量に$O(K(N-K+1))$になり, TLEです.

そこで, 「各$i = 1,2, \ldots, N - K$に対する$[i, i + K - 1]$と$[i + 1, i + K]$のキャンディの純粋に差分を確認する」という方法を考えます. 辞書型を用いて$\{1: \mathrm{number}(1), 2: \mathrm{number}(2), 3: \mathrm{number}(3), \ldots \}$のように各キャンディの個数を記録し, それを変化させていく方法を考えます. また, キャンディの種類数を別に記録しておけば, 辞書型のvalueを合計する時間計算量を減らすことができます.

D - National Railway

この問題は駅$(i_s, j_s)$から駅$(i_f, j_f)$までの鉄道を敷設するのにかかる最小の値段を動的計画法(dynamic programming)を用いて考えていきます.

その際, $i_s <= i_f$は一般に仮定してよいことに注意してください. 駅$(i_s, j_s)$から駅$(i_f, j_f)$までの鉄道を敷設するのにかかる最小の値段は, 駅$(i_f, j_f)$から駅$(i_s, j_s)$までの鉄道を敷設するのにかかる最小の値段と同一であることから, そのように仮定してよいことが分かります.

また, $j_s <= j_f$も仮定します. $j_s >= j_f$のパターンは, 例えば行列$A_{i, j}$の左右を反転させることによって実現できます. (これに関しては, $A_{i, j}$の左右を反転させたものに対して同様の作業を繰り返さなければならないことに注意してください. )

中間地点$(i, j)$を境に2段階に分けて考えると楽になります.

• 青木君が一方の駅をすでに建設して現在$(i,j)$にいるとき, それまでにかかった費用として考えられる最小値(dp[i][j])
  1. $(i, j)$に駅を立てた
     
  2. $(i-1, j)$から$(i,j)$に線路を引いて移動してきた
     
  3. $(i, j-1)$から$(i,j)$に線路を引いて移動してきた
     
• 2つ目の駅を$(i, j)$に建てて青木君がどこかへ飛び立ったとき, そこまでにかかった費用として考えられる最小値(X[i][j])
  1. $(i-1, j)$から$(i,j)$に線路を引いて移動してきて, $(i,j)$に駅を立てた
     
  2. $(i, j-1)$から$(i,j)$に線路を引いて移動してきて, $(i,j)$に駅を立てた
     

$A_{i, j}$の左右反転には, 例えば.reverse()を用いると便利です.

多次元配列の最小値を求めるには, 例えば多次元リストの平坦化を用いると便利です. Pythonには, itertoolsモジュールのitertools.chain.from_iterable()があり, itertools.chain.from_iterable(matrix)のような形で, 2次元配列を1次元配列にすることができます.

なお, Python (3.8.2)で実行するとTLEになります. PyPy3 (7.3.0)で実行することでACです.

E以降

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

参考にしたサイト等

• 「解説 - AtCoder Beginner Contest 210」
  Editorial - AtCoder Beginner Contest 210

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

• nkmk様による「Pythonで文字列を検索（〜を含むか判定, 位置取得, カウント）」
  Pythonで文字列を検索（〜を含むか判定, 位置取得, カウント） | note.nkmk.me

  Pythonで文字列を検索して任意の文字列を含むか判定したり, その位置を取得したり, ヒットした個数をカウントしたりする方法について説明する. 任意の文字列を含むか判定: in演算子 任意の文字列の位置を取得: find(), rfind() 任意の文字列の個数をカウント: count() 単語を検索, 個数をカウント 大文字小文字を区別せずに...

• nkmk様による「Pythonでリストや文字列を逆順に並べ替え（reverse, reversed）」
  Pythonでリストや文字列を逆順に並べ替え（reverse, reversed） | note.nkmk.me

  Pythonでリストの要素を逆順に並べ替えるにはreverse(), reversed()およびスライスを使った方法がある. 文字列やタプルを逆順に並べ替えたい場合はreversed()かスライスを使う. ここでは以下の内容について説明する. リスト型のメソッド reverse(): 元のリストを逆順に並べ替え 組み込み関数 reversed(): 要素を逆順に取り...

• nkmk様による「Pythonでflatten（多次元リストを一次元に平坦化）」
  Pythonでflatten（多次元リストを一次元に平坦化） | note.nkmk.me

  Pythonで多次元のリスト（リストのリスト, ネストしたリスト）を一次元に平坦化する方法について説明する. 2次元のリストを平坦化itertools.chain.from_iterable()sum()リスト内包表記処理速度の差 itertools.chain.from_iterable() sum() リスト内包表記 処理速度の差 3次元以上のリストや不規則なリストを平坦化 NumPy配...