パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）参加記（～E問題）

100-200-300(1)-400-500-0で1ペナ5完1500点。

A - Brick

割り算の問題で、 $\dfrac{N}{W}$ の商が答えとなる。余りは切り捨ててよい。

計算量は、 $O(1)$ 。

B - Blocks on Grid

ブロックに対してできる操作は、「ブロックを取り除く」のみである。この操作でブロックの個数が増えることはないので、操作後のブロックの個数はすべてのマスの中で一番少ないものに合わせる必要がある。
よって、マス目を全探索してブロックの個数の最小値 $A_{min}$ を保持し、各マスにあるブロックの個数 $A_{i, j}$ と $A_{min}$ の差の総和を求めればよい。

計算量は、 $O(HW)$ 。

C - Unlucky 7

公式解説とは違うオーバーキル気味な方法で通した。

前計算として、「 $10$ 進数で表すと $7$ を含む」「 $8$ 進数で表すと $7$ を含む」数を列挙する。再帰関数で幅優先探索を実装し、 $7$ が含まれる数のみを配列に放り込んでsort->unique->eraseすると、 $7$ を含む数が昇順で並ぶ。あとは与えられた $N$ 以下の数の個数を、配列の二分探索を用いて求めればよい。

計算量ってどれくらいなんだろう？幅優先探索で生成されるノードの数は $10$ 進数の場合 $111111$ 個なんだけど、これを数式で $N$ を使ってきれいに書けないな…。 $O(N)$ くらいということにしておく。
[追記]ソートしているので計算量は $O(N\log N)$ でした。ソートの存在忘れがち

A進数をB進数に変換する関数を暇なときに組もうと思った（暇なときにやる気が起きるはずがないので永遠に実装されない）。

D - Sum of difference

絶対値記号が邪魔なので配列をソートして考える。さらに引かれる数と引く数ごとにわけて考えると、それぞれの整数が足される回数は配列の添え字番号に依存していることがわかる。
具体的には、
$\displaystyle \sum_{i=1}^n \{A_i\times i\} - \displaystyle \sum_{i=1}^n \{A_i\times (N-i)\}$
が答え。

計算量は、 $O(N)$ 。

E - Throne

拡張ユークリッドの互除法で解いた。

玉座を $0$ 番目の椅子と考えると、
$S+Ki \equiv 0 \pmod N$
を満たす最小の $i$ が解となる。少し変形すると
$Ki \equiv N-S \pmod N$
となる。これは、拡張ユークリッドの互除法を用いて
$Kx+Ny=N-S$
を満たす $x$ を求める問題に落とせる。