AtCoder Beginner Contest 456 参加記録と解答例 (A D問題)

本記事は、AtCoder Beginner Contest 456 (Promotion of AtCoder Career Design DAY) に参加した際の、A〜D問題の復習と解答の備忘録です。コンテスト中に考えた解法の方針や、提出したPythonのコードについて整理しています。

A - Dice

配点 : 100 点

問題文

6 つの面を持つサイコロが 3 個あります。どのサイコロも、面には 1, 2, 3, 4, 5, 6 が書かれています。
これらのサイコロを同時に振ったとき、出た目の合計が X になることはありますか？

制約

• X は 1 以上 20 以下の整数

自分の解答の方針

サイコロ3個の合計値の最小は $1 \times 3 = 3$、最大は $6 \times 3 = 18$ なので、足して 3〜18 だったら OK。

提出したコード

X = int(input())
if 3<=X<=18:
    print("Yes")
else:
    print("No")

---

B - 456

配点 : 200 点

問題文

6 つの面を持つサイコロが 3 個あります。 $i$ 個目のサイコロの $j$ 個目の面には $A_{i,j}$ が書かれています。どのサイコロも、各面が出る確率は $\frac{1}{6}$ です。
これらのサイコロを同時に振ったとき、4, 5, 6 の書かれた目が 1 つずつ出る確率を求めてください。

制約

• $A_{i,j}$ は 1 以上 6 以下の整数

自分の解答の方針

ぱっと見で難しそうに見えて焦った。すべてのパターン（4,5,6の順列）をごり押しで書いた。後で気づいたが、forで全パターン繰り返せばよかった。

提出したコード

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A4 = A.count(4)
A5 = A.count(5)
A6 = A.count(6)
B4 = B.count(4)
B5 = B.count(5)
B6 = B.count(6)
C4 = C.count(4)
C5 = C.count(5)
C6 = C.count(6)
ans1 = A4*B5*C6/6**3
ans2 = A4*B6*C5/6**3
ans3 = A5*B4*C6/6**3
ans4 = A6*B4*C5/6**3
ans5 = A5*B6*C4/6**3
ans6 = A6*B5*C4/6**3
ans = ans1+ans2+ans3+ans4+ans5+ans6
print(ans)

---

C - Not Adjacent

配点 : 300 点

問題文

a, b, c からなる文字列 S が与えられます。
S の空でない部分文字列であって、同じ文字が隣り合わないものの個数を 998244353 で割った余りを求めてください。
ただし、2 つの部分文字列が文字列として一致しても、取り出す位置が異なるならば区別するものとします。

制約

• S は a, b, c からなる長さ 1 以上 3×$10^5$ 以下の文字列

自分の解答の方針

連続して同じ文字が続いていなければ、その個数は $|S|(|S|+1)/2$ となる。
連続に続いている場合、そこを境目として二つの連続してない文字列に分割することで同じように考えられる。
文字列を前から順に見ていくので計算量は $O(|S|)$ で、余裕があるのでとりあえず毎回答えを 998244353 で割っておく。

提出したコード

S = list(input())
ans = 0
len_count = 0
prev_char = "x"
for i in range(len(S)):
    if S[i] == prev_char:
        len_count = 0
    len_count += 1
    ans += len_count
    ans = ans % 998244353
    prev_char = S[i]
print(ans)

---

D - Not Adjacent 2

配点 : 400 点

問題文

a, b, c からなる文字列 S が与えられます。
S の空でない部分列であって、同じ文字が隣り合わないものの個数を 998244353 で割った余りを求めてください。
ただし、2 つの部分列が文字列として一致しても、取り出す位置が異なるならば区別するものとします。

制約

• S は a, b, c からなる長さ 1 以上 3×$10^5$ 以下の文字列

自分の解答の方針

文字が 3 種類しかないので、最後の文字が a, b, c となる部分列の数を保持しておき、文字列を順番に見ながら更新していく。DP のような形で行けそう。C問題同様、毎回 998244353 で割っておけばよさそう。

提出したコード

S = list(input())
A = 0
B = 0
C = 0
for i in range(len(S)):
    if S[i] == "a":
        A += 1+B+C
        A = A % 998244353
    if S[i] == "b":
        B += 1+A+C
        B = B % 998244353
    if S[i] == "c":
        C += 1+A+B
        C = C % 998244353
ans = (A+B+C) % 998244353
print(ans)