SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)をPythonで解く

こんにちは, Shinoryoです.

今回はSOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)を, Pythonで解いてみた結果を書き連ねていこうと思います.

AtCoder Beginner Contest 192 - AtCoder

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

A - Star

求めるのは, $X$を$100$で割った余りを$100$から引いた値です.

B - uNrEaDaBlE sTrInG

文字列$S$から奇数番目を取り出した文字列と偶数番目を取り出した文字列を用意します.

文字列の中の文字が大文字か小文字かを判定するには, .islower()や.isupper()を使用します.

.islower()は, 以下の2つの条件がどちらも満たされる場合, Trueを返します. そうでなければFalseを返します.

• 文字列中に大文字と小文字の区別のある文字が1文字以上存在する.
• その大文字と小文字の区別のある文字の全てが小文字である.

.isupper()は, 以下の2つの条件がどちらも満たされる場合, Trueを返します. そうでなければFalseを返します.

• 文字列中に大文字と小文字の区別のある文字が1文字以上存在する.
• その大文字と小文字の区別のある文字の全てが大文字である.

偶数番目を取り出した文字列に関する判定には注意が必要です. 文字列$S$が1文字の場合, 偶数番目を取り出した文字列としては, おそらく何もない空白の文字列が用意されるはずです. そうすると, .isupper()としてはFalseが返ってきてしまうので, 偶数番目を取り出した文字列が空白である可能性を考慮しなければなりません.

C - Kaprekar Number

意外にも, 問題文にあることをそのまま実行すれば通ります. 「各桁の数字を大きい順に並び替えて」「各桁の数字を小さい順に並び替えて」には, 整数型を文字列型にして, その各文字を整数型にしてソートすればよいです.

D - Base n

$N$進法における$X$の値を出力する関数を用意するのは, 「C - Kaprekar Number」と同じなのでそこまで難しくはないでしょう.

$N$進数の$N$が大きいほど2桁目以降の表す値が大きくなっていくので, $N$を大きくすればするほど$X$の値は大きくなる(狭義単調増加)ということになります. よって, 二分探索(binary search)を用いることができます.

ここで用いる二分探索の概要

二分探索とは, ソート済みのリストに対する検索を行うにあたって有用なアルゴリズムです.

• ある$\mathrm{low}$とある$\mathrm{high}$の値を用意します.
• $\mathrm{low}$と$\mathrm{high}$の真ん中の値として$\mathrm{mid} = \left( \mathrm{low} + \mathrm{high} \right) / 2$をとります.
• $\mathrm{mid}$進法における$X$の値を確認します.
  • $\mathrm{mid}$進法における$X$の値が$M$以下である(つまり, 条件を満たす)ならば, $\mathrm{low} = \mathrm{mid}$とします(次は, より大きい値を確認します).
  • $\mathrm{mid}$進法における$X$の値が$M$より大きい(つまり, 条件を満たさない)ならば, $\mathrm{high} = \mathrm{mid}$とします(次は, より小さい値を確認します).
• $\mathrm{low}$と$\mathrm{high}$の差が$1$になるまで上の作業を続けます.

このようにして得られた$\mathrm{low}$と$\mathrm{high}$について, $\mathrm{low}$以下では条件を満たし, $\mathrm{high}$以上では条件を満たさないということになるので, 求める値は$\mathrm{low} - d$(ただし, $d$は$X$に含まれる最も大きい数字)となります.

lowとhighの初期値

二分探索を行うにあたって, $\mathrm{low}$と$\mathrm{high}$の初期値を検討する必要があります.

• $\mathrm{low}$：$d$を採用します. もし$\left( d+1 \right)$以上の全ての$N$に対して, $N$進法における$X$の値が$M$より大きい(つまり, 条件を満たさない)場合は$\mathrm{low} = d$となり, 出力される値は$d - d = 0$となります.
• $\mathrm{high}$：$M+1$を採用します. 後述するように, $X$が2桁以上の場合(つまり, $X = 10$以上)に対して二分探索を適用します. すると, $M$進法における$X$の値は必ず$M$以上になります. よって, $\left( M+1 \right)$進法における$X$の値は必ず$M$より大きくなります.

細かい場合の補足

• そもそもが$\mathrm{low} + 1 >= \mathrm{high}$の場合：$\left( d+1 \right)$以上の全ての$N$に対して, $N$進法における$X$の値が$M$より大きくなります. 下のコード例では「while low + 1 < high」として, $\mathrm{low} + 1 >= \mathrm{high}$の場合には二分探索を行わず$\mathrm{low} = d$となるようになっています.
• $X$が1文字の場合：二分探索は使えないので, 最初に場合分けしておく必要があります.

E以降

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

参考にしたサイト等

• 「解説 - AtCoder Beginner Contest 187」
  Editorial - AtCoder Beginner Contest 192

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

• TATSUO IKURA様による「文字列の中の文字が大文字か小文字かを判定する(islower, isupper, istitle)」 >
  文字列の中の文字が大文字か小文字かを判定する(islower, isupper, istitle)

  文字列で用意されているメソッドの中で, 文字列の中に含まれる文字が大文字か小文字かを判定するのに使用できるメソッドの使い方について解説します.

• 渡部 拓也様による「アルゴリズムを勉強するなら二分探索から始めよう！ 『なっとく！アルゴリズム』より」
  アルゴリズムを勉強するなら二分探索から始めよう！ 『なっとく！アルゴリズム』より

  　新しいサービスやプロダクトを開発するなら, アルゴリズムの理解はもはや欠かせなくなってきました. まだ理解が浅い, 勉強したいと思っている, そんな方には翔泳社が1月31日に刊行した『なっとく！アルゴリズム』をおすすめします. 今回は本書の読み方と, アルゴリズムの例として二分探索について紹介します.