本記事は、AtCoder Beginner Contest 456 (Promotion of AtCoder Career Design DAY) に参加した際の、A〜D問題の復習と解答の備忘録です。コンテスト中に考えた解法の方針や、提出したPythonのコードについて整理しています。 配点 : 100 点 6 つの面を持つサイコロが 3 個あります。どのサイコロも、面には 1, 2, 3, 4, 5, 6 が書かれています。 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") 配点 : 200 点 6 つの面を持つサイコロが 3 個あります。 $i$ 個目のサイコロの $j$ 個目の面には $A_{i,j}$ が書かれています。どのサイコロも、各面が出る確率は $\frac{1}{6}$ です。 $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) 配点 : 300 点 a, b, c からなる文字列 S が与えられます。 S は a, b, c からなる長さ 1 以上 3×$10^5$ 以下の文字列 連続して同じ文字が続いていなければ、その個数は $|S|(|S|+1)/2$ となる。 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) 配点 : 400 点 a, b, c からなる文字列 S が与えられます。 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)