Home / Python /

AtCoder Beginner Contest 181をPythonで解く

投稿日：　

Atcoder Python

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

こんにちは, Shinoryoです.

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

AtCoder Beginner Contest 181 - AtCoder

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

A - Heavy Rotation

偶数なら「White」, 奇数なら「Black」を出力すれば問題ないであろう.

B - Trapezoid Sum

$A_i$から$B_i$までの整数の合計は, 等差数列の公式で

\begin{align} S_i &= \frac{\left( B_i + A_i \right) \left( B_i - A_i + 1 \right)}{2} \end{align}

となるから, これを$N$個に対して合計すればよい. 2で割ったことによって変数ansがint型ではなくなってしまったので, 最後にint型にして出力している.

C - Collinearity

3点$(x_1 , y_1) , (x_2 , y_2) , (x_3 , y_3)$が1直線上にあるには, 2点$(x_1 , y_1) , (x_2 , y_2)$を結ぶ直線の傾きが, 2点$(x_1 , y_1) , (x_3 , y_3)$を結ぶ直線の傾きに等しければよい. すなわち,

\begin{align} \frac{\left( y_2 - y_1 \right)}{\left( x_2 - x_1 \right)} &= \frac{\left( y_3 - y_1 \right)}{\left( x_3 - x_1 \right)} \end{align}

となればよい. $x_1 = x_2$, $x_1 = x_3$のときにも利用できるように,

\begin{align} \left( x_3 - x_1 \right) \left( y_2 - y_1 \right) &= \left( x_2 - x_1 \right) \left( y_3 - y_1 \right) \end{align}

とすればよい.

この判定を, $N$個の点の組み合わせの数だけ実行すればよい. エラーにならないようにfor文の繰り返す範囲には注意されたい.

D - Hachi

8の倍数を判定するには, 「下3桁が8で割り切れればよい」という判定方法を利用する. しかし, 愚直に実行するとTLE.

そこで, リストの要素の数え上げをできるcollections.Counter()を利用する. collections.Counter()を利用することで, リストの中で「aが何個, bが何個, ……」というデータを得ることができる. 入力データの中に0はないため, 入力した数字からどれか3つを用いて112, 120, 128, ……のどれかを構成できるかを調べていけば, 計算量が少なくて済む.

1桁, 2桁の場合は別に処理する. これは単に8で割った余りで判断すればよいであろう.

E以降

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

参考にしたもの

Search