AtCoder Beginner Contest 347をPythonで解く-Shinoryo's Weblog

こんにちは, Shinoryoです.

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

A - Divisible

空のリストquotientsを用意します. リスト$A$をループして, 各要素$A_i$に対して次の操作を行います.

$S$の部分文字列を全探索して, 何種類あったかを数え上げればよいです. $S$の部分文字列を取得するには, 文字列のスライスを用います. 重複なく用いるには, 集合(set)に追加していって, 最後にその要素数を数えます.

1週間の何日目に予定があるかが重要なので, $D$の各要素を$(A + B)$で割った余りを用意し, ソートしてしまいましょう.

高橋くんの予定が全て休日であるということは, ある予定とその次の予定の間に全ての平日が含まれればよいです.

例えば, 1週間のうち2日が休日で5日が平日の例を考えてみます. 次の表のようになっている場合, 3, 4, 5, 6, 0日目が平日であれば, 高橋くんの予定は全て休日です.

次の表のようになっている場合, 1, 2, 3, 4, 5日目が平日であれば, 高橋くんの予定は全て休日です.

次の表のようになっている場合, 平日をどのように設定しても, 高橋君の予定のどれかが平日になってしまいます.

あるいは, 全ての予定が休日の範囲に収まればよいです.

基本的には, 公式解説どおりです.

$n_{0, 0}$, $n_{0, 1}$, $n_{1, 0}$, $n_{1, 1}$が非負整数であるための条件だけ補足します. $a$, $b$, $c$が整数であることを用いて, 次のように考えることができます.

$n_{0, 0}$が非負である$\Leftrightarrow$ \begin{align} 60 - \frac{a + b + c}{2} \geq 0 \quad \Leftrightarrow \quad a + b + c \leq 120 \end{align}
$n_{0, 0}$が整数である$\Leftrightarrow$ $a + b + c$が$2$の倍数 $\Leftrightarrow$ \begin{align} a + b + c \equiv 0 \ (\mathrm{mod}\ 2) \end{align}
$n_{0, 1}$が非負である$\Leftrightarrow$ \begin{align} \frac{- a + b + c}{2} \geq 0 \quad \Leftrightarrow \quad a \leq b + c \end{align}
$n_{0, 1}$が整数である$\Leftrightarrow$ $- a + b + c$が$2$の倍数 $\Leftrightarrow$ \begin{align} - a + b + c \equiv 0 \ (\mathrm{mod}\ 2) \quad \Leftrightarrow \quad a + b + c \equiv 2a \equiv 0 \ (\mathrm{mod}\ 2) \end{align}
$n_{1, 0}$が非負である$\Leftrightarrow$ \begin{align} \frac{a - b + c}{2} \geq 0 \quad \Leftrightarrow \quad b \leq c + a \end{align}
$n_{1, 0}$が整数である$\Leftrightarrow$ $a - b + c$が$2$の倍数 $\Leftrightarrow$ \begin{align} a - b + c \equiv 0 \ (\mathrm{mod}\ 2) \quad \Leftrightarrow \quad a + b + c \equiv 2b \equiv 0 \ (\mathrm{mod}\ 2) \end{align}
$n_{1, 1}$が非負である$\Leftrightarrow$ \begin{align} \frac{a + b - c}{2} \geq 0 \quad \Leftrightarrow \quad c \leq a + b \end{align}
$n_{1, 1}$が整数である$\Leftrightarrow$ $a + b - c$が$2$の倍数 $\Leftrightarrow$ \begin{align} a + b - c \equiv 0 \ (\mathrm{mod}\ 2) \quad \Leftrightarrow \quad a + b + c \equiv 2c \equiv 0 \ (\mathrm{mod}\ 2) \end{align}

最終的に, $a + b + c \leq 120$, $a + b + c \equiv 0 \ (\mathrm{mod}\ 2)$, $a \leq b + c$, $b \leq c + a$, $c \leq a + b$にまとめることができます.

あるいは, ユーザー解説のようにも実装することができます. $X$と$Y$のビットを試しに立ててみて, $X$や$Y$のpopcountが目標数ちょうどに達したかを確かめてみる方法です.

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