AtCoder Beginner Contest 191をPythonで解く

こんにちは, Shinoryoです.

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

A - Vanishing Pitch

条件は, $D < VT$または$VS < D$となります.

B - Remove It

配列$A^\prime$を作成して, それを空白でつなげた文字列を用意し, 出力します.

あるいは, 文字列メソッドjoin()を使うと, 文字列のリストを一つの文字列に連結することができます. 「"間に挿入する文字列".join([連結したい文字列のリスト])」の形です. 今の場合, 「間に挿入する文字列」は半角空白, 連結したい文字列のリストは$A^\prime$の各要素を文字列型にしたものになります.

C - Digital Graffiti

マス$S_{ij}$に対応して, 図のように格子点を定めます. 端の点に関しては考えなくてよいので, 格子点は全部で$(H-1)(W-1)$個あります.

格子点$(x,y)$が多角形の頂点であるのは, 以下の条件のどちらかを満たす場合です.

• その点の周囲$4$マス($S_{x,y}$, $S_{x+1,y}$, $S_{x,y+1}$, $S_{x+1,y+1}$)のうち$1$マスが黒に塗られている.
• その点の周囲$4$マス($S_{x,y}$, $S_{x+1,y}$, $S_{x,y+1}$, $S_{x+1,y+1}$)のうち$3$マスが黒に塗られている.

$2$マスだけが黒の場合は多角形の周の一部に対応しますし, $4$マスなら多角形の内部の点, $0$マスなら関係ない点になります.

以下がその例です. 図に入っている範囲では, $(0,0)$, $(1,0)$, $(1,1)$が多角形の頂点になります.

D - Circle Lattice Points

入力が高々小数点第4位までなので, 入力値に予め$10^4$をかけておけば, 精度に関して問題なく計算を行うことができます.

$\mathrm{const} = 10^4$単位で切り上げる関数と切り下げる関数をあらかじめ用意しておくと, 記述が楽になります. $X - R$($10^4$単位で切り上げ)から$X + R$($10^4$単位で切り下げ)までの間の$x$座標に対して,

($10^4$単位で切り上げ)から,

($10^4$単位で切り下げ)までの$y$座標が, 条件に適合します(三平方の定理より). それを数え上げればよいです.

sampleは全て通ったのですが, 提出するとWAとなってしまいました(6個から10個くらい). 今の時点ではこれを改善する方法を理解できていません.

E以降

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

参考にしたサイト等

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

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

• nkmk様による「Pythonで文字列を連結・結合（+演算子, joinなど）」
  Pythonで文字列を連結・結合（+演算子, joinなど） | note.nkmk.me

  Pythonでの文字列操作において, 文字列を連結・結合する方法として, 複数の文字列を連結・結合: +演算子, +=演算子 数値と文字列を連結・結合: +演算子, +=演算子, str(), format() 文字列のリスト（配列）を一つの文字列に連結・結合: join() 数値のリスト（配列）を一つの文字列に連結・結合: join(), str() を説明する. ...

• なっちゃん様による「【ちょっとづつAtCode】ABC191　C – Digital Graffiti」
  【ちょっとづつAtCode】ABC191　C – Digital Graffiti

  引用（引用）問題文H 行 W 列のマス目があります. このマス目の, 上から i 番目, 左から j 番目のマスを, マス(i,,j)と呼ぶことにします. 各マスは黒または白に塗られています. Si,jが # ならばマス (i,,j)は黒に塗られており