AtCoder Beginner Contest 234のきろく

AtCoder 競技プログラミング AtCoder Beginner Contest 参戦記

またまた日が空きました。AtCoder Beginner Contest 234に参加です。

A - Weird Function (100点)

問題文にあるような関数を実装して、f(f(f(t)+t)+f(f(t)))を出力させればいいです。
また、f(f(f(t)+t)+f(f(t)))=4t^8+40t^7+216t^6+740t^5+1789t^4+3060t^3+3746t^2+2960t+1371 であるため、こちらを実装するのもありでしょう。
多項式の計算にはHorner法を用いることで累乗による計算回数を減らすことができます。

B - Longest Segment (200点)

点の個数が N \leq 100 と小さいため、全ての組 (i,\,j) (1 \leq i \lt j \leq N) についての線分の長さ \sqrt{(x_i-x_j)^2 + (y_i-y_j)^2} を計算して最大値を求めればいいです。
C++などの言語ではstd::fixed, std::setprecisionや"%.8d"などを用います。

C - Happy New Year! (300点)

0,\,2 を 0,\,1 に変換してもその大小関係は変わらないため、条件を満たす中で K 番目に小さい数は二進数表記での K に対応します。そのため十進数を二進数に変換し、1 を 2 に変換することで答えが求まります。

D - Prefix K-th Max (400点)

毎回、既出の数のリストから K 番目に大きな数を求めたり、ソートしたりすると計算量が O(N^2) や O(N^2 \log N) となってしまい、TLEします。
ある時点で大きい方から K+1 番目以降の数がそれ以降で答えになることはないため、各時点での大きい方から K 番目までの数が分かればいいです。よってこれらを集合std::setや優先度付きキューstd::priority_queueを用いて、毎回、この集合内の最小値と A_i の比較で大きい方を集合内にあるようにして要素数が常に K になるようにすれば、その中の最小値が各回の答えになり、全体として O(N \log N) になります。
コンテスト内では最初は、二重二分探索で O(N (\log N)^2) 解で通しましたが、探索範囲を間違えて2WA出してしまいました。

E - Arithmetic Number (500点)

一番左の数は 1 から 9 の 9 通り、公差は -9 から 8 の 18 通りであるため、これらを全探索することができます。各条件について右に数を増やしていき(増やす数がマイナスになればその条件については打切り)、X 以上になったら、答えの候補にして、その中の最小値が答えとなります。

F - Reordering (500点)

S 内の i 種目の英小文字の出現数を c_i とします。このとき

{\mathrm{dp}}_{i,j} = (\text{\(i\) 種目までの英小文字で作れる \(j\) 文字の文字列の数})
というDPを考えます。公式解説では貰うDPで考えているようでしたが、私は配るDPをもとに考えました。
{\mathrm{dp}}_{i,j} の状態について (i+1) 種目の英小文字を文字の隙間(前後含む) (j+1) 個の隙間に配置していきます。このとき同じ隙間に複数個おいてもよく、1個も置かれない隙間があってもいいです。初期状態
{\mathrm{dp}}_{i,j}=\left\{ \begin{array}{ll} 1 & (i = 0 \land j = 0)\\ 0 & (\mathrm{Otherwise}) \end{array} \right.
として 0 \leq k \leq c_{i+1} について {\mathrm{dp}}_{i+1,j+k} に {\mathrm{dp}}_{i,j} \times {}_{j+1}\mathrm{H}_{k} を足すことで答えが \displaystyle \sum_{j=1}^{N} {\mathrm{dp}}_{26,j} と求まります。ここで {}_{n}\mathrm{H}_{r} は重複組み合わせで {}_{n}\mathrm{H}_{r} = \displaystyle\binom{n+r-1}{r} = \frac{(n+r-1)!}{r!(n-1)!} であり、変形すると公式解説と同じ
{\mathrm{dp}}_{i,j} =\displaystyle \sum_{k=0}^{\min\{j,\,c_i\}} {\mathrm{dp}}_{i-1,j-k} \binom{j}{k}
となります。

G - Divide a Sequence (600点): 未提出

これもDPっぽいですが、未だ解けてません。

Ex - Enumerate Pairs (600点、実行時間制限: 4 sec): 未提出

計算量が落ちない...

結果、感想

f:id:Flkanjin:20220109131832p:plain
ちゃんと6完で来たので良かったという感じですが、Dで2WA出してしまったのが痛いなと、要反省です。