AtCoder Beginner Contest 197（Sponsored by Panasonic）をPythonで解く

こんにちは, Shinoryoです.

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

A - Rotate

入力する文字列を$S$として, 求めるのは$S$の$2$文字目以降の後ろに$S$の$1$文字目をくっつけた, $S[1:]+S[0]$になります.

B - Visibility

マス目$(X,Y)$から上下左右4方向に順に進めていき(答えに$1$を足していく), 障害物#か端に突き当たったらそこで探索するのをやめればよいです. マス$(X,Y)$自身を含むので答えの初期値には$1$を加えておくこと, $X$と$Y$が数学の通常の座標の感覚とは違うことに注意して実装します.

図 B問題における探索のイメージ. 星のマスはマス目$(X,Y)$を表す. 上下左右4方向に順に進めていき, 障害物#か端に突き当たったらそこで探索するのをやめる.

C - ORXOR

区分けの仕方は, それぞれの数の間にあると仮定する$(N - 1)$個の仕切りそれぞれに, 仕切りを置くか置かないかの$2$通りになるので, $2^{N - 1}$通りになります. それぞれの区分けの仕方は, 整数$0 \leq i \leq 2^{N - 1} - 1$を2進数にした表現によって表すことができます. このような全探索方法をbit全探索といいます.

下のコードでは, $i$を2進法で表したとき右から$j$番目が$1$ならば, $A[j - 1]$と$A[j]$の間に仕切りがあると考えています. 右から$j$番目が$1$かどうかを確かめるには, $i$を2進法で表した数を右に$j - 1$だけシフト(>>演算子)し, それと$1$との論理積(&演算子)をとることによって確かめます.

図 右から$j$番目が$1$かどうかを確かめるイメージ. 左では, そのまま$1$との論理積をとることによって, 一番右が$1$であることを確かめている. 一方右では, 右へ$1$シフトしたあとで$1$との論理積をとることによって, 右から$2$番目が$0$であることを確かめている.

Pythonでは論理和(OR)(|演算子)と排他的論理和(XOR)(^演算子)があるので, それを用いることで計算をすることができます.

なお, 下のコードはPyPy3でACとなります. Python3だとTLEでした.

D - Opposite

任意の正多角形に対してある円が存在し, その正多角形はその円に内接するようにできます.

$p_0$と$p_{N/2}$の2点を結ぶ線分の中点をとることによって, 円の中心(あるいは「正多角形の中心」)$q$を得ることができます. そして, $p_0$の座標と$q$の座標, そして正多角形が正$N$角形であることが分かれば, $q$を中心に$2\pi / N \, \mathrm{rad}$だけ反時計回りに$p_0$を回転させた点が$p_1$であるということが分かります.

図 D問題を表した図. $p_0$と$p_{N/2}$の2点を結ぶ線分の中点をとることによって, 点$q$の座標が分かる. そして, $p_1$は, $q$を中心に$2\pi / N \, \mathrm{rad}$だけ反時計回りに$p_0$を回転させた点である.

座標の回転は行列(あるいは, 複素数平面など)を用いて考えます. $(x_0, y_0)$を中心に角度$\alpha$だけ反時計回りに$(x, y)$を回転させることを考えれば, その結果得られる$(x_1, y_1)$は

となることに注意してください. Pythonにおいて, $\cos$や$\sin$はmath.cos(), math.sin()で計算できます(引数は$\mathrm{rad}$). 円周率$\pi$はmath.piで扱えます.

E以降

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

参考にしたサイト等

• 「解説 - AtCoder Beginner Contest 197（Sponsored by Panasonic）」
  Editorial - AtCoder Beginner Contest 197（Sponsored by Panasonic）

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

• nkmk様による「Pythonのビット演算子（論理積, 論理和, 排他的論理和, 反転, シフト）」
  Pythonのビット演算子（論理積, 論理和, 排他的論理和, 反転, シフト） | note.nkmk.me

  Pythonには&, |, ^, ~, <<, >>のビット演算子が用意されており, 2進数で表した整数型intの値の各ビットに対して, それぞれ論理積, 論理和, 排他的論理和, ビット反転, 左ビットシフト, 右ビットシフトを行う. ここでは, 論理積（AND）: &演算子 論理和（OR）: |演算子 排他的論理和（XOR）: ^演算子 について説明してから, ...

• nkmk様による「Pythonで三角関数を計算（sin, cos, tan, arcsin, arccos, arctan）」
  Pythonで三角関数を計算（sin, cos, tan, arcsin, arccos, arctan） | note.nkmk.me

  Pythonの数学関数の標準モジュールmathを使うと, 三角関数（sin, cos, tan）および逆三角関数（arcsin, arccos, arctan）の計算ができる. 9.2. math — 数学関数 三角関数 — Python 3.6.4 ドキュメント ここでは, 以下の内容についてサンプルコードとともに説明する. 円周率（パイ）: math.pi 角度変換（ラジアン, 度）: m...