🐈

【競技プログラミング】AtCoder Beginner Contest 162_D問題

に公開
競技プログラミング
tech

問題

https://atcoder.jp/contests/abc162/tasks/abc162_d

要約

長さNの文字列Sが与えられる。
Sは'R'、'G'、'B'のみで構成されている。

以下の2つの条件を同時に満たす組(i, j, k)の数を求める

  1. Si ≠ Sj かつ Si ≠ Sk かつ Sj ≠ Sk
    （つまり、i番目、j番目、k番目の文字がすべて異なる）

  2. j - i ≠ k - j
    （つまり、iとjの間の距離がjとkの間の距離と異なる）

ただし、1 ≤ i < j < k ≤ N を満たす必要があります。

  • N: 文字列Sの長さ
  • S: 'R'、'G'、'B'のみからなる文字列
  • i, j, k: 文字列Sの位置を示すインデックス（1-indexed）

既存投稿一覧ページへのリンク

一覧ページ

アプローチ

全ての可能な組み合わせの数から、条件を満たさない組み合わせの数を引くことで解を求める。

解法手順

  1. 入力された文字列Sを走査し、R、G、Bの出現回数をカウントする。
  2. 同時に、文字列Sを数値に変換した配列Snを作成する（R=1, G=2, B=3）。
  3. 全ての可能な組み合わせの数（R * G * B）を計算する。
  4. 文字列Sの各位置（start）から始めて、異なる間隔（diff）で3つの文字を選ぶ全てのパターンを調べる。
  5. 選んだ3つの文字が全て異なる場合、それは等間隔に並んでいる異なる3色の組み合わせなので、カウントする。
  6. 全ての可能な組み合わせの数から、等間隔に並んでいる異なる3色の組み合わせの数を引いた結果を出力する。

ACコード

ac.py
def io_func():
    # 入力を受け取る
    N = input()  # 文字列の長さ（この問題では使用しない）
    S = input()  # 入力文字列
    return S

def solve(S):
    # R, G, Bの出現回数をカウントし、数値に変換した配列Snを作成
    Sn = []
    R, G, B = 0, 0, 0
    for char in S:
        if char == 'R':
            R += 1
            Sn.append(1)
        elif char == 'G':
            G += 1
            Sn.append(2)
        else:  # 'B'の場合
            B += 1
            Sn.append(3)

    # 等間隔に並んでいる異なる3色の組み合わせをカウント
    count = 0
    for start in range(len(S)):
        for diff in range(1, (len(S) - start + 1) // 2):
            # 3つの文字が全て異なる場合、カウントを増やす
            if (Sn[start] - Sn[start+diff]) * (Sn[start+diff] - Sn[start+(2*diff)]) * (Sn[start] - Sn[start+(2*diff)]) != 0:
                count += 1

    # 結果を計算して返す
    result = R * G * B - count
    return str(result)

if __name__=="__main__":
    # メイン処理
    S = io_func()
    print(solve(S))

###
# N: 入力文字列の長さ（この問題では使用しない）
# S: 入力文字列
# Sn: 文字列Sを数値に変換した配列（R=1, G=2, B=3）
# R, G, B: それぞれの色の出現回数
# count: 等間隔に並んでいる異なる3色の組み合わせの数
# start: 文字列Sの開始位置
# diff: 等間隔の間隔

# 1. io_func()関数で入力を受け取る
# 2. solve()関数で主な処理を行う
#    a. 文字列Sを走査し、R, G, Bの出現回数をカウントする
#    b. 同時に、文字列Sを数値に変換した配列Snを作成する
#    c. 文字列Sの各位置(start)から始めて、異なる間隔(diff)で3つの文字を選ぶ全てのパターンを調べる
#    d. 選んだ3つの文字が全て異なる場合、countを増やす
#    e. 全ての可能な組み合わせの数(R * G * B)からcountを引いた結果を返す
# 3. 結果を出力する

Discussion