Home / Python /

東京海上日動プログラミングコンテスト2023(AtCoder Beginner Contest 299)をPythonで解く

投稿日：　

Atcoder Python

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

こんにちは, Shinoryoです.

今回は東京海上日動プログラミングコンテスト2023(AtCoder Beginner Contest 299)を, Pythonで解いてみた結果を書き連ねていこうと思います.

Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 299) - AtCoder

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

A - Treasure Chest

|の位置と*の位置を取得し, その大小関係をもとに判断すればよいです. |は2つあるので, 左側のものはfindメソッドで, 右側のものはrfindメソッドで検索します.

B - Trick Taking

以下のステップに分けて考えるとよいでしょう.

  1. 勝者になりうるカードの色$A$を調べる.
  2. 色が$A$のカードの中で, 最も大きい値のカードを調べる.

勝者になりうるカードの色$A$は, 数値$T$と配列$C$の比較で調べることができます. $C$に$T$が含まれれば$A = T$, $C$に$T$が含まれなければ$A = C_1$です.

その後, カードを一つひとつ調べていって, カードの色が$A$であれば最大判定に加えればよいです.

C - Dango

oと-が両方含まれているかどうかで区別すると, この問題は非常に簡単になります.

  • 両方含まれていれば, oが連続している数の最大が答えになります.
  • いずれかが含まれていなければ, $S$はダンゴ文字列になりえないので$-1$が答えになります.

oが連続している数を調べるには, $S$を-で分割してみればよいです. S.split("-")とすることで, ["ooo", "o","oooo","oo","ooooo", ...]のように, oが連続している部分を取り出すことができます. それぞれの要素に対してlen関数を適用したものの最大値をとれば, 答えが分かります.

D - Find by Query

二分探索のようにして探していけばよいでしょう. 例えば, $N = 7$, $S = 0010011$というパターンを考えます. すると, 以下のようにしていくことで効率よく探せることが分かります.

  1. $l = 1$, $r = 7$とします.
  2. $m = (l + r) / 2 = 4$とします.
  3. $S_m = S_4$の値を調べます.
  4. $S_m = S_4 = 0$なので, $l = 4$と更新します.
  5. $m = (l + r) / 2 = 5$とします(小数点以下は切り捨てます).
  6. $S_m = S_5$の値を調べます.
  7. $S_m = S_5 = 0$なので, $l = 5$と更新します.
  8. $m = (l + r) / 2 = 6$とします.
  9. $S_m = S_6$の値を調べます.
  10. $S_m = S_4 = 1$なので, $r = 6$と更新します.
  11. $l = 5$, $r = 6$より$l + 1 = r$となったので, $l = 5$を出力して終了します.

このように, $S_l = 0$, $S_r = 1$の条件のもとで少しずつ$l$と$r$の差を縮めていって, $l + 1 = r$となったときに, $l$が求める答えとなるようにします. $l$と$r$の真ん中の値$m$を計算して$S_m$の値を取得して$l$または$r$の値を更新するのを$1$ループとすれば, 高々$\log N$ループで$l + 1 = r$となります. $N \leq 2 \times 10^5$なので, 高々$18$ループで$l + 1 = r$となります.

E以降

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

参考にしたサイト等