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

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

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

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

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

このようにすれば, $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, \ldots, x_{K-1})$に$x_K = \mathrm{True}$を付け加えたものが, $y_K$が$\mathrm{True}$であるような変数列になります.