AtCoder Beginner Contest 189のきろく

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

AtCoder Beginner Contest 189に参加して青色になることができました。コンテストから1週間たっていますが、この回から参戦記を書いていきたいと思います。

A - Slot (100点)

std::string型の変数で受け取り、全て同じか調べる。
C++だとC[0] == C[1] == C[2]のような書き方はできないので2つの条件文に分割する。
Ａ問題は1分切れるぐらいになりたいなぁ...

B - Alcoholic (200点)

\displaystyle\sum_{i=1}^{n}\frac{V_i\,P_i}{100}>X となるような最小の nを求める問題。小数で計算すると誤差が出るかもしれないので両辺を100倍して \displaystyle\sum_{i=1}^{n} {V_i\,P_i}>100X として判定すればいい。

C - Mandarin Orange (300点、実行時間制限: 1.5 sec)

区間 [l, r] を決めればxは1からその区間内の最小値をとれるが、(r-l+1)x の最大値を求める問題なので、その区間内の最小値にすればいい。区間を決めた後その中の最小値を探しているのでは O(N^3) で間に合わないと思って先にD問題へ。先に l を決めておいて r を大きくしながら x を更新しつつ (r-l+1)x の最大値を求めていけばいいことに気が付いて戻ってきて通す。

D - Logical Expression (400点)

見た瞬間DPだなと思う。演算 S_i がANDなら y_{i-1} と y_i の両方が \mathrm{True} なら \mathrm{True}、そうでなければ \mathrm{False}。ORのときは y_{i-1} と y_i の両方が \mathrm{False} なら \mathrm{False}、そうでなければ \mathrm{True} となるので $$ {\mathrm{dp}}_{i,j} = \left(y_i=\left\{
\begin{array}{ll}
\mathrm{False} & (j = 0)\\
\mathrm{True} & (j = 1)
\end{array}
\right. \text{となるような \((x_0, \dots, x_i)\) の組の数}\right) $$ として
$$ {\mathrm{dp}}_{0,0} = {\mathrm{dp}}_{0,1} = 1 $$
$$ {\mathrm{dp}}_{i,0} =\left\{
\begin{array}{ll}
2{\mathrm{dp}}_{i-1,0} + {\mathrm{dp}}_{i-1,1} & (S_i = \texttt{"AND"})\\
{\mathrm{dp}}_{i-1,0} & (S_i = \texttt{"OR"})
\end{array}
\right. $$
$$ {\mathrm{dp}}_{i,1} =\left\{
\begin{array}{ll}
{\mathrm{dp}}_{i-1,1} & (S_i = \texttt{"AND"})\\
{\mathrm{dp}}_{i-1,0} + 2{\mathrm{dp}}_{i-1,1} & (S_i = \texttt{"OR"})
\end{array}
\right. $$ という漸化式に従って順に計算する。求める答えは {\mathrm{dp}}_{N,1}です。

E - Rotate and Flip (500点)

元の座標を (x,\,y) として
操作が3なら操作後は (2p-x,\,y)、4なら (x,\,2p-y) で...とうんうん考えていたらこれらは軸についての対称移動と平行移動で表せられるなぁ、となりました。回転と対称移動は1次変換であるのでこれはアフィン変換かぁと思いましたが、それを行列で表現できないかと思って調べて提出しました。
このアフィン変換については別記事にて。

F - Sugoroku2 (600点)

全く分かんねぇぜ、とりあえず「すごろく 振り出し 期待値」で検索するとふか杯5thのE問題とその解説ページが見つかりました。このE問題は各マスが、「何も起こらない」「振り出しに戻る」「x_i マス進む」のいずれかという問題でその解法を参考にして実装し、提出しました。
$$
f_i = (\text{マス \(i\) からゴールするまでにルーレットを回す回数の期待値})
$$ として、振り出しに戻るがなければ f_i=\displaystyle\frac{1}{M}\sum_{j=1}^{M}\,f_{i+j} ですが、振り出しに戻るというますがあるのでうまくいきません。f_i=a_i+b_i f_0 と1次式の形で考えると

a_i=\left\{ \begin{array}{ll} 0 & (i \in A)\\ 1+\displaystyle\frac{1}{M}\sum_{j=1}^{M}\,a_{i+j} & (\text{otherwise}) \end{array} \right.
b_i=\left\{ \begin{array}{ll} 1 & (i \in A)\\ \displaystyle\frac{1}{M}\sum_{j=1}^{M}\,b_{i+j} & (\text{otherwise}) \end{array} \right.
という漸化式が成り立ちます。i が N+1 以上の時は a も b も 0 となるので、係数が降順に求まっていきます。
ここで f_0=a_0+b_0 f_0 より答えは \displaystyle f_0 = \frac{a_0}{1-b_0} です(b_0 が 1 の時はゴールに到達不可能)。

結果、感想

f:id:Flkanjin:20210201161449p:plain
久しぶりの全完でした。本番で黄Diffの問題を解けるとは思いませんでした。F問題がACになった時にレート変化の推定値が1650越えでパフォ推定値が2350越えだったので「マジで!?」って叫んでしまいました。こっから黄色になるは難しいですがこれからも頑張っていこうと思います。