LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@o_chan_t(おー ちゃん)

【競技プログラミング】AtCoder Beginner Contest 197_C問題

Last updated at Posted at 2024-12-07

問題

要約

  1. 長さNの数列Aが与えられる。

  2. この数列を1つ以上の空でない連続した区間に分ける。

  3. 各区間内の数のビット単位ORを計算する。

  4. 得られた全ての値のビット単位XORを計算する。

  5. 上記の手順で得られる最小値を求める。

変数情報：

  • N: 数列の長さ
  • A: 与えられる数列

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

一覧ページ

独り言

この問題、難しいよね？って見てみたらdiff:809か・・・
AtCoder197のD問題より絶対難しいと思うんだけどなぁ
「C問題」というメタ読みから、力技で解けるはずというアプローチでした。

アプローチ

  1. 数列の分割方法を全て列挙する。
  2. 各分割方法に対して、区間ごとのビット単位ORを計算し、その結果のビット単位XORを求める。
  3. 全ての分割方法の中で最小の結果を見つける。

解法手順

  1. 入力として数列の長さNと数列Aを受け取る。
  2. Nが1の場合、A[0]をそのまま出力して終了する。
  3. itertools.productを使用して、N-1個の0または1からなる全ての組み合わせを生成する。これは分割位置を表す。
  4. 各分割方法に対して以下の処理を行う：
    a. 現在の区間の結果をA[0]で初期化する。
    b. 数列を順に走査し、分割位置（1）に達するまでビット単位ORを計算する。
    c. 分割位置に達したら、それまでの結果をリストに保存し、次の区間の計算を開始する。
    d. 全ての区間の計算が終わったら、保存された結果のビット単位XORを計算する。
  5. 全ての分割方法の中で最小の結果を記録する。
  6. 最小の結果を出力する。

ACコード

ac.py

from itertools import product
import sys

def sub_solve(A, B):
    # 分割位置を表すリストBの合計が0でない場合（少なくとも1つの分割がある場合）
    if sum(B) != 0:
        result = A[0]  # 現在の区間の結果をA[0]で初期化
        li = []  # 各区間の結果を保存するリスト
        for i in range(N-1):
            if B[i] == 0:
                # 分割位置でない場合、ビット単位ORを計算
                result = result | A[i+1]
            elif B[i] == 1:
                # 分割位置の場合、これまでの結果をリストに追加し、新しい区間を開始
                li.append(result)
                result = A[i+1]
        li.append(result)  # 最後の区間の結果をリストに追加
        
        # 全ての区間の結果に対してビット単位XORを計算
        ans = li[0]
        for j in range(1, len(li)):
            ans = ans ^ li[j]
        
        return ans
    else:
        # 分割がない場合（全ての要素が1つの区間）、大きな値を返す
        return 10**9

def solve(A):
    # 最終的な最小値を保持する変数を初期化
    finalans = 10**9

    # 全ての可能な分割方法に対してループ
    for B in product(range(2), repeat=N-1):
        # 各分割方法に対して計算し、最小値を更新
        finalans = min(finalans, sub_solve(A, B))

    # 最小値を出力
    print(finalans)

if __name__=="__main__":
    # 数列の長さNを入力として受け取る
    N = int(input())
    # 数列Aを入力として受け取る
    A = list(map(int, input().split()))

    # Nが1の場合、A[0]をそのまま出力して終了
    if N == 1:
        print(A[0])
        sys.exit()
    solve(A)

# 変数の意味：
# - N: 数列の長さ
# - A: 入力された数列
# - B: 分割位置を表す0と1の列
# - result: 現在の区間のビット単位ORの結果
# - li: 各区間のビット単位ORの結果を保存するリスト
# - ans: 各区間の結果のビット単位XORの結果
# - finalans: 全ての分割方法の中での最小値

改修版ACコード

ac.py
from itertools import product
import sys

def calc_or_and_xor(A, B):
    # 分割位置毎にビット単位ORし、その結果をXORする
    or_value = A[0]
    xor_result = 0
    for i in range(1, len(A)):
        if B[i-1] == 0:
            or_value |= A[i]
        else:
            xor_result ^= or_value
            or_value = A[i]
    xor_result ^= or_value  # 最後の区間の結果をXOR
    return xor_result

def sub_solve(A, B):
    # 分割位置を表すリストBの合計が0でない場合（少なくとも1つの分割がある場合）
    if sum(B) != 0:
        return calc_or_and_xor(A, B)
    else:
        # 分割がない場合（全ての要素が1つの区間）、大きな値を返す
        return 10**9

def solve(A):
    # 最終的な最小値を保持する変数を初期化
    finalans = 10**9

    # 全ての可能な分割方法に対してループ
    for B in product(range(2), repeat=N-1):
        # 各分割方法に対して計算し、最小値を更新
        finalans = min(finalans, sub_solve(A, B))

    # 最小値を出力
    print(finalans)

if __name__=="__main__":
    # 数列の長さNを入力として受け取る
    N = int(input())
    # 数列Aを入力として受け取る
    A = list(map(int, input().split()))

    # Nが1の場合、A[0]をそのまま出力して終了
    if N == 1:
        print(A[0])
        sys.exit()
    solve(A)

yieldで返そうとすると、どうしてもAC出来なかった・・・

速度比較

SpeedCompare.jpg

スピード2割減！shiracamus(しらかみゅ)様。ご教授くださり、ありがとうございました。

机上トレース

入力例01

全ての可能な分割方法に対してループ

  • for B in product(range(2), repeat=N-1):で(0,0), (0,1), (1,0), (1,1)の全パターンを試す

その他周辺知識

ビット演算（論理演算）

result = result | A[i+1]

ans = ans ^ li[j]

ここでは、ビット単位のOR演算（|）とXOR演算（^）が使われている。これらの演算は、2進数表現された整数に対して行われる。

OR演算は、二つの数の各ビットを比較し、どちらかが1であれば結果も1になる演算である。
例えば、5 (101) OR 3 (011) = 7 (111) となる。

XOR演算は、二つの数の各ビットを比較し、異なる場合に1、同じ場合に0となる演算である。
例えば、5 (101) XOR 3 (011) = 6 (110) となる。

これらの演算は、数列の要素を組み合わせて新しい値を生成するために使用されている。

全数探索（組み合わせ）

from itertools import product
...
for B in product(range(2), repeat=N-1):

ここでは、itertools.productを使用して、0と1のすべての組み合わせ（長さN-1）を生成している。
これは、数列Aのすべての可能な分割方法を表現している。

数学的には、これは2^(N-1)個の組み合わせを生成することに相当する。
各要素間に分割を入れるか入れないかの2通りの選択肢があり、それがN-1回あるためである。

最小値

finalans = min(finalans, sub_solve(A, B))

ここでは、すべての分割方法の中から最小の結果を求めている。
min関数は、与えられた引数の中で最小のものを返す。

数学的には、これは以下の式を計算していることに相当する：

$\min_{B \in {0,1}^{N-1}} f(A, B)$

ここで、$f(A, B)$はsub_solve関数で計算される値を表す。

数列と分割

if sum(B) != 0:
    result = A[0]
    li = []
    for i in range(N-1):
        if B[i] == 0:
            result = result | A[i+1]
        elif B[i] == 1:
            li.append(result)
            result = A[i+1]
    li.append(result)

このコードは、数列Aを分割し、各部分に対してOR演算を適用している。
B[i] = 1の場合に分割が行われ、それまでの結果がliリストに追加される。

数学的には、これは数列Aを互いに素な部分数列に分割し、各部分数列の要素にOR演算を適用していることに相当する。

累積演算

ans = li[0]
for j in range(1, len(li)):
    ans = ans ^ li[j]

ここでは、分割された各部分の結果に対して、XOR演算を累積的に適用している。

数学的には、これは以下の式を計算していることに相当する：

$ans = l_1 \oplus l_2 \oplus ... \oplus l_k$

ここで、$l_i$はli[i]の値を、$\oplus$はXOR演算を表す。

sub_solve関数の定義（前半）

def sub_solve(A, B):
    if sum(B) != 0:
        result = A[0]
        li = []
        for i in range(N-1):
            if B[i] == 0:
                result = result | A[i+1]
            elif B[i] == 1:
                li.append(result)
                result = A[i+1]

この関数は、与えられた数列Aと分割位置を示すリストBに基づいて計算を行う。
sum(B) != 0は、少なくとも1つの分割がある場合を意味する。
resultは現在の区間のビット単位ORの結果を保持し、liは各区間の結果を保存するリストである。
|演算子はビット単位ORを行う。例えば、5(二進数:101) | 3(二進数:011) = 7(二進数:111)となる。

sub_solve関数の定義（後半）

        li.append(result)
        ans = li[0]
        for j in range(1, len(li)):
            ans = ans ^ li[j]
        return ans
    else:
        return 10**9

最後の区間の結果をliに追加し、全ての区間の結果に対してビット単位XORを計算する。
^演算子はビット単位XORを行う。例えば、5(二進数:101) ^ 3(二進数:011) = 6(二進数:110)となる。
分割がない場合（B[i]がすべて0の場合）は、大きな値（10**9）を返す。

solve関数の定義

def solve(A):
    finalans = 10**9
    for B in product(range(2), repeat=N-1):
        finalans = min(finalans, sub_solve(A, B))
    print(finalans)

この関数は、全ての可能な分割方法に対してループを回し、最小値を求める。
product(range(2), repeat=N-1)は、0と1のN-1個の組み合わせをすべて生成する。
例えば、N=4の場合、(0,0,0), (0,0,1), (0,1,0), ..., (1,1,1)のような組み合わせが生成される。

スポット関数

ビット演算を用いた区間の計算

from functools import reduce

def calculate_intervals(values, split_positions):
    """
    与えられた値のリストを、分割位置に基づいて区間に分け、
    各区間内でビット単位ORを計算し、最後に全区間のビット単位XORを計算します。
    ■ 区間ごとの特徴抽出
    各区間内でビット単位ORを計算することで、その区間内に存在するビットパターンの統合が行われます。
    これにより、各区間内で少なくとも1回は立っているビットが特定されます。
    ■ 全体的なパターン検出
    最後に全区間のビット単位XORを計算することで、区間間の差異や類似性を反映した結果が得られます。
    XOR演算は、偶数回出現したビットを消去し、奇数回出現したビットを残す特性があります。
    
    :param values: 計算対象の値のリスト
    :param split_positions: 分割位置を示すブール値のリスト（Trueが分割位置）
    :return: 計算結果
    """
    if not any(split_positions):
        return None  # 分割がない場合はNoneを返す

    result = values[0]
    intervals = []

    for i, (value, split) in enumerate(zip(values[1:], split_positions), 1):
        if not split:
            result |= value
        else:
            intervals.append(result)
            result = value
    intervals.append(result)

    result = 0
    for interval in intervals:
        result ^= interval
    return result

# 使用例
values = [1, 2, 3, 4, 5]
split_positions = [False, True, False, True]
result = calculate_intervals(values, split_positions)
print(result)

すべての分割パターンに対する最小値の計算

calculate_intervals関数は特定の分割パターンに対する計算を行い、find_minimum_split関数はすべての可能な分割パターンを試して最小値を見つけ

from itertools import product
from functools import reduce

def calculate_intervals(values, split_positions):
    """
    与えられた値のリストを、分割位置に基づいて区間に分け、
    各区間内でビット単位ORを計算し、最後に全区間のビット単位XORを計算します。
    ■ 区間ごとの特徴抽出
    各区間内でビット単位ORを計算することで、その区間内に存在するビットパターンの統合が行われます。
    これにより、各区間内で少なくとも1回は立っているビットが特定されます。
    ■ 全体的なパターン検出
    最後に全区間のビット単位XORを計算することで、区間間の差異や類似性を反映した結果が得られます。
    XOR演算は、偶数回出現したビットを消去し、奇数回出現したビットを残す特性があります。
    
    :param values: 計算対象の値のリスト
    :param split_positions: 分割位置を示すブール値のリスト（Trueが分割位置）
    :return: 計算結果
    """
    if not any(split_positions):
        return None  # 分割がない場合はNoneを返す

    result = values[0]
    intervals = []

    for i, (value, split) in enumerate(zip(values[1:], split_positions), 1):
        if not split:
            result |= value
        else:
            intervals.append(result)
            result = value
    intervals.append(result)

    result = 0
    for interval in intervals:
        result ^= interval
    return result

def find_minimum_split(values):
    """
    与えられた値のリストに対して、すべての可能な分割パターンを試し、
    最小の結果を返します。

    :param values: 計算対象の値のリスト
    :return: 最小の計算結果
    """
    n = len(values)
    if n == 1:
        return values[0]

    min_result = float('inf')
    for split in product([False, True], repeat=n-1):
        result = calculate_intervals(values, split)
        if result is not None:
            min_result = min(min_result, result)

    return min_result

# 使用例
values = [1, 2, 3, 4, 5]
min_value = find_minimum_split(values)
print(min_value)
0
0
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?