AtCoder Beginner Contest 189をPythonで解く

こんにちは, Shinoryoです.

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

AtCoder Beginner Contest 189 - AtCoder

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

A - Slot

愚直に条件を確認します. $C_1=C_2$かつ$C_2=C_3$で大丈夫です.

B - Alcoholic

お酒を$1$杯飲むたびに基準値を超えるかどうかを確認します. 今回入力は全て整数なので, アルコール等の量を$100$倍して計算することで, 整数の範囲で確実に計算することができます.

C - Mandarin Orange

全探索で計算することを考えます. $x$としては$A_l$から$A_r$までで最も小さい値をとれば問題ありません. しかし, この方法だと時間計算量が非常に多く^*1, TLE.

そこで, 固定された$l$に対して$r$を$l$から$n$まで順に大きくしながら$x$を更新していくという方法にすることによって, 時間計算量を減らすことができます^*2. しかし, これでもTLEになってしまいます.

PyPy3だとACできたので, これ以上は踏み込みません.

D - Logical Expression

$N\le 60$とはいえ全変数列を探索しようとすると大変な量になりますので, 工夫が必要です. ここでは, 動的計画法(dynamic programming)を用いて解くことを考えます.

簡単に, $N=1$の場合は以下のように考えられます.

• $S_1$が$\mathrm{AND}$であるとすると, $x_1$も$y_0$も$\mathrm{True}$でなければなりません. よって, $$\begin{array}{}\text{(1)}& (x_0,x_1)& =(\mathrm{True},\mathrm{True})\end{array}$$ のみが当てはまります.
• $S_1$が$\mathrm{OR}$であるとすると, $x_1$か$y_0$のどちらかが$\mathrm{True}$であればよいです. よって, $$\begin{array}{}\text{(2)}& (x_0,x_1)& =(\mathrm{True},\mathrm{True}),(\mathrm{False},\mathrm{True}),(\mathrm{True},\mathrm{False})\end{array}$$ のみが当てはまります.

これを一般化します. $N=K\ge 2$の場合は以下のように考えられます. 関数$f(S_1,S_2,\dots ,S_N)$を, 文字列$S_1,S_2,\dots ,S_N$に対する答え(すなわち, $y_N$が$\mathrm{True}$であるような変数列$(x_0,x_1,x_2,\dots ,x_N)$の数)とします.

• $S_K$が$\mathrm{AND}$であるとすると, $x_K$も$y_{K-1}$も$\mathrm{True}$でなければなりません. よって, $f(S_1,S_2,\dots ,S_K)$は, $y_{K-1}$が$\mathrm{True}$であるような変数列の数$f(S_1,S_2,\dots ,S_{K-1})$に一致し, $$\begin{array}{}\text{(3)}& f(S_1,S_2,\dots ,S_K)& =f(S_1,S_2,\dots ,S_{K-1})\end{array}$$ となります^*3.
• $S_K$が$\mathrm{OR}$であるとすると, $x_K$か$y_{K-1}$のどちらかが$\mathrm{True}$であればよいです. すなわち, 以下の2パターンになります.
  • $y_{K-1}$が$\mathrm{True}$であるような変数列$(x_0,x_1,x_2,\dots ,x_{K-1})$に$x_K=\mathrm{False}$を付け加えたもの
  • $x_K=\mathrm{True}$であるような任意の変数列$(x_0,x_1,x_2,\dots ,x_K)$
  したがって, $$\begin{array}{}\text{(4)}& f(S_1,S_2,\dots ,S_K)& =f(S_1,S_2,\dots ,S_{K-1})+2^K\end{array}$$ となります.

このようにすれば, $O(N)$で求めることができます.

E以降

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

参考にしたサイト等

• 「解説 - AtCoder Beginner Contest 189」
  Editorial - AtCoder Beginner Contest 189

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

脚注

*1 : $O(N^3)$と私は推測します. 間違っていたらコメントください.

*2 : $O(N^2)$と私は推測します. 間違っていたらコメントください.

*3 : この場合, $y_{K-1}$が$\mathrm{True}$であるような変数列$(x_0,x_1,x_2,\dots ,x_{K-1})$に$x_K=\mathrm{True}$を付け加えたものが, $y_K$が$\mathrm{True}$であるような変数列になります.