パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301）をPythonで解く

こんにちは, Shinoryoです.

今回はパナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301）を, Pythonで解いてみた結果を書き連ねていこうと思います.

パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301） - AtCoder

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

A - N-choice question

先に$\lceil N/2 \rceil$回勝利した方が勝利になります. 高橋くんと青木くんのそれぞれが勝った回数をfor文で調べていき, どちらかが$\lceil N/2 \rceil$回勝利した時点でその人を出力して終了すればよいです.

Pythonにおける切り上げは, math.ceilで簡単に得ることができます.

B - Fill the Gaps

基本的には$A_1, A_2, \ldots , A_N$をそのまま出力し, もし途中で$| A_i - A_{i + 1} | \neq 1$となった場合にはその間を埋めるように出力すればよいことが分かります. Pythonのprint()は最後にデフォルトで改行を加えてしまうため, print(end = " ")のように最後に改行ではなく空白を加えるようにします.

C - AtCoder Cards

ミソなのは, 「$S$に含まれている文字が$T$にも含まれてい」るといったことを確認する手段です.

すでに使った文字が消去された新しい$T$を用いて検索をしなければなりません. しかし, ここにリストに対するinを使っていた場合, inの時間計算量は$O(N)$($N$はリストの要素数)であるため, 結果としてTLEになってしまいます.

これは, 文字列$T$の情報を, 「文字$x$が$y$個含まれている」といった情報に変換することです. これを辞書型で実装すれば, inの時間計算量は$O(1)$で済みます. 「$T$から文字$x$を消す」は$y$を$1$減らせばよく, $y$が$0$の場合は文字$x$が$T$に含まれていないものとみなすことにします.

「文字$x$が$y$個含まれている」といった情報への変換は, collections.Counterを用いると簡単に実装できます.

D - Bitmask

まず, 全ての?を$0$に変えたものが, $T$の最小値になります. これによりも$N$が小さい場合, $-1$を出力することになります.

その条件をクリアしたら, $N$を超えないように?を$1$に変えていくことになります. $1$に変えた?が左にあればあるほどその数字は大きくなりますので, 左の?から順に$1$に変えて, $N$を超えないかを確かめていくことになります.

2進法の文字列を10進法の整数に変えるには, int(文字列, 基数)を用います.

E以降

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

参考にしたサイト等

• 「解説 - パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301）」
  Editorial - パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301）

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

• nkmk様による「Pythonで小数点以下を切り捨て・切り上げ: math.floor(), math.ceil()」
  Pythonで小数点以下を切り捨て・切り上げ: math.floor(), math.ceil() | note.nkmk.me

  Pythonで浮動小数点数floatの小数点以下を切り捨て・切り上げするには, 標準ライブラリmathモジュールのfloor(), ceil()を使う. 小数点以下を切り捨て: math.floor() 小数点以下を切り上げ: math.ceil() math.floor()とint()との違い 無限大への丸め (rounding toward infinity; RI) なお, 厳密にはmath.floor()は「負の無...

• nkmk様による「PythonのCounterでリストの各要素の出現個数をカウント」
  PythonのCounterでリストの各要素の出現個数をカウント | note.nkmk.me

  Pythonでリストやタプルの全要素の個数は組み込み関数len(), 各要素の個数（要素ごとの出現回数）はcount()メソッドで取得できる. さらに, Python標準ライブラリcollectionsのCounterクラスを使うと, 出現回数が多い順に要素を取得できたりする. ここでは, 全要素数をカウント: len() 各要素の個数（要素ごとの出現回数）を...

• nkmk様による「Pythonで2進数, 8進数, 16進数の数値・文字列を相互に変換」
  Pythonで2進数, 8進数, 16進数の数値・文字列を相互に変換 | note.nkmk.me

  Pythonでは通常の10進数だけでなく2進数, 8進数, 16進数として数値や文字列を扱うことができる. 相互に変換するのも簡単. ここでは, 以下の内容についてサンプルコードとともに説明する. 整数を2進数, 8進数, 16進数で記述 数値を2進数, 8進数, 16進数表記の文字列に変換組み込み関数bin(), oct(), hex()組み込み関数format...