Home / Python /

日鉄ソリューションズプログラミングコンテスト2023（AtCoder Beginner Contest 303）をPythonで解く

投稿日：　

Atcoder Python

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

こんにちは, Shinoryoです.

今回は日鉄ソリューションズプログラミングコンテスト2023（AtCoder Beginner Contest 303）を, Pythonで解いてみた結果を書き連ねていこうと思います.

NS Solutions Corporation Programming Contest 2023（AtCoder Beginner Contest 303） - AtCoder

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

A - Similar String

文字列$S$, $T$のそれぞれ$i$文字目同士に対して, 以下のいずれかを満たすかどうかを確認すればよいです.

  • $S_i$と$T_i$が同じ文字
  • $S_i$と$T_i$の片方が1, もう片方がi
  • $S_i$と$T_i$の片方が0, もう片方がo

例では, 引数に指定した要素がすべてTrueと判定されるとTrueを返すall()を用いています. 全ての$0 \leq i < N$において, S[i] == T[i] or {S[i], T[i]} == {"1", "l"} or {S[i], T[i]} == {"0", "o"}が成り立てばTrueとなり, Yesを出力します.

B - Discord

ある人$i$連続して並んで撮影したことがある人の集合を$\mathrm{friend}_i$として格納します. 最終的に, ある人$i$と不仲である可能性のある人の数を調べ足し上げて, $2$で割ったものが答えになります.

単に足し上げるだけだと, 例えば人$A$と人$B$の組に関して, 人$A$目線と人$B$目線で2倍足し上げてしまうことに注意が必要です.

C - Dash

基本的には以下を繰り返せばよいです.

  1. $H$を$-1$させて実際に移動させる(現在座標を表す変数を更新する).
  2. $H < 0$の場合, 終了.
  3. そこにアイテムがあって$H < K$の場合, そのアイテムを消費して$H = K$とする.

アイテムは同じ場所に存在しないことを利用して, アイテムの場所を表すリストはset()にして保存しておくと良いです. list()で保存してしまうと, inの計算に時間がかかってしまいTLEとなってしまいます.

なお, set()の要素としてリストを加えることはできないため, 例では座標の数値を文字列で結合してset()の要素に加えています.

D - Shift vs. CapsLock

動的計画法を使用します. 公式解説を引用します.

$\mathrm{dp}_{i,j}$を「$i$文字目まで入力した時点でCapsLockキーのランプが$j = 0$ならばOFF, $j = 1$ならばONである状態にするために必要な時間の最小値」として動的計画法を行います.
(出典元：https://atcoder.jp/contests/abc303/editorial/6442)
(参照：2023年5月28日)

例えば, $\mathrm{dp}_{0, 0} = 0$, $\mathrm{dp}_{0, 1} = Z$となります. $\mathrm{dp}_{1, 0}$は「$1$文字目まで入力した時点でCapsLockキーのランプがOFFである状態にするために必要な時間の最小値」ですので, $1$文字目がaだとすれば, $\mathrm{dp}_{0, 0} + X = X$または$\mathrm{dp}_{0, 1} + Y + Z = Y + 2Z$のどちらか小さい方が入ります.

このようにして, $\mathrm{dp}_{N, 0}$, $\mathrm{dp}_{N, 1}$まで計算していきます. 最終状態におけるCapsLockキーのON・OFFは問わないので, $\mathrm{dp}_{N, 0}$または$\mathrm{dp}_{N, 1}$のどちらか小さい方を出力します.

動的計画法は, 例えば再帰的な構造を持つ問題に有効です. 問題をより小さな部分問題に分割($i$文字目までの状況に分割)し, 再帰的に解を計算することで($i$文字目までの結果で$i + 1$文字目までの状況に対する解を求める), 最終的な解を得ることができるような問題です.

本ブログでも, 過去に以下のような動的計画法を用いる問題を取り扱っています.

E以降

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

参考にしたサイト等