AtCoder Beginner Contest 205参加記（～E問題）

あんまりおもしろくなかったな。知識不足
f:id:mmnkblog:20210613230226p:plain

A - kcal

$1$ mLあたり $\dfrac{A}{100}$ kcalなので、これを $B$ 倍すれば $B$ mLあたりのカロリーが求まる。答えは $\dfrac{AB}{100}$ 。答えは小数値で求めることに注意。計算量は $O(1)$ 。

B - Permutation Check

$(1, 2, \dots, N)$ を $P$ とする。 $P$ を並べ替えて $A$ に一致させるのは実装が大変なので、 $A$ を $P$ にすることを考える。 $P$ は昇順に並んでいるので $A$ をソートして $P$ に一致するか判定するだけでよい。計算量は $O(N\log N)$ 。

C - POW

~~クソ問~~
愚直に計算すると時間がかかるので $A, B, C$ の正負ゼロで場合分けする。 $A=B$ ならイコール、どちらかがゼロならもう片方の正負、負の数が含まれるなら $C$ の偶奇で場合分け。計算量は $O(1)$ 。

上記の考察より、 $C$ の偶奇さえわかればよいので $C=1$ または $C=2$ としてそのまま計算し値を比較する方法でも良い。

正整数 $x$ に対して、 $K_i$ 番目の正整数は $x$ 以上かを判定できれば、この $x$ を $1$ から $(10^{18}+10^5+1)$ の範囲で二分探索することで答えを求められる。
判定問題を解く。 $x$ 未満の正整数の中に $A$ の要素がいくつ含まれるかをlower_boundで求めてその個数を $c$ とすると、 $x$ は $x - c$ 番目の数であるとみなすことができる。よって $x - c \le K_i$ ならYesとなる。
計算量は $O(N+Q\log A_i \log N)$ 。

E - White and Black Balls

解けなかった。
動的計画法を考える。 $i$ 個ボールを置いて、そのうち $j$ 個が白いボールだったとき
dp[i+1][j+1] = dp[i][j] + dp[i][j+1]
と更新できるはず（ $i$ 個目に白いボールを置くとき＋ $i$ 個目に黒いボールを置くとき）。更新するときに白と黒のボールの個数の制約と問題文の条件を確認し、 $i, j$ が条件を満たしていないならdp[i][j] = 0にする。これで計算量 $O(N^2+M)$ 。ここから高速化できるのか、それとも違う解法なのかは分からない。