Home / Python /

Panasonic Programming Contest (AtCoder Beginner Contest 186)をPythonで解く

投稿日：　

Atcoder Python

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

こんにちは, Shinoryoです.

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

Panasonic Programming Contest (AtCoder Beginner Contest 186) - AtCoder

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

A - Brick

$N$を$W$で割った商を出力すればよいです.

B - Blocks on Grid

2次元配列$A$の最小値を求め, 2次元配列$A$の各成分からその最小値を差し引いた残差を全て足し合わせればよいです.

下の例では, 多次元リストを1次元に平坦化するためにitertools.chain.from_iterable()を用いています. 単に2次元配列をmin()の引数にとるだけでは, list型の和になってしまいます.

C - Unlucky 7

Pythonには数値を8進数の文字列に変換できる関数oct()があるので, それをありがたく使わせていただこうと思います.

oct()を使わないのだとすれば, 定義に則って10進数を8進数に変換することになります. 関数化した方が楽だと思います.

D - Sum of difference

この結果は$A_1, \ldots , A_N$の順序に依存しないので, ソートして並べ替えてしまってよいです. $A_1 \leq \cdots \leq A_N$とすれば, $\left| A_i - A_j \right| = A_j - A_i$になります.

まずぱっと思いつくのは, 律儀に全パターン計算する方法です. しかし, この方法だと$O(N^2)$となり, TLE.

そこで, 若干工夫をします. 求めるのは

\begin{align} \sum_{i=1}^{N-1} \sum_{j=i+1}^N \left| A_i - A_j \right| \end{align}

ですが, $A_1 \leq \cdots \leq A_N$とできることを利用すれば,

\begin{align} \sum_{i=1}^{N-1} \sum_{j=i+1}^N \left| A_i - A_j \right| &= \sum_{i=1}^{N-1} \sum_{j=i+1}^N \left( A_j - A_i \right) \nonumber \\ &= \sum_{i=1}^{N-1} \left( \sum_{j=i+1}^N A_j - A_i \sum_{j=i+1}^N \right) \nonumber \\ &= \sum_{i=1}^{N-1} \left( \sum_{j=i+1}^N A_j - \left( N - i \right) A_i \right) \end{align}

となります. $\sum_{j=i+1}^N A_j$はあらかじめ累積和を$O(N)$で求めておくことで対応できます. これを用いることで, (ソートでかかる時間計算量を考慮して)$O(N \log N)$でできます.

E以降

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

参考にしたサイト等

Search

About Me

自分の写真
理系大学生でした. Bloggerを利用して発信を行っています.

Labels

Blog Archives