✨
【競技プログラミング】AtCoder Beginner Contest 197_C問題
問題
要約
- 長さNの数列Aが与えられます。
- この数列を1つ以上の空でない連続した区間に分けます。
- 各区間内の数のビット単位ORを計算します。
- 得られた全ての値のビット単位XORを計算します。
- 上記の手順で得られる最小値を求めます。
N: 数列の長さ
A: 与えられる数列
既存投稿一覧ページへのリンク
アプローチ
ビット全探索を用いて、数列の全ての可能な分割パターンを生成し、各パターンに対してXORの結果を計算し、その中から最小値を求める。
解法手順
-
入力を受け取り、数列の長さNと数列A自体を取得する。
-
最小値を保持する変数ansを無限大で初期化する。
-
0から2^(N-1)-1までの全ての数Xに対して以下の処理を行う：
a. Xを(N-1)ビットの2進数と見なし、これを分割のパターンとして使用する。
b. 1のビットが立っている位置で数列を分割すると考える。 -
各分割パターンに対して：
a. 現在の区間のOR結果を保持する変数nowを0で初期化する。
b. XORの結果を保持する変数cntを0で初期化する。
c. 数列Aの各要素に対して：- nowとその要素のORを取る。
- もし分割点なら（対応するビットが1なら）：
- cntとnowのXORを取る。
- nowを0にリセットする。
-
得られたcntとansを比較し、小さい方をansに保存する。
-
全てのパターンを試した後、ansを出力する。
ACコード
ac.py
def io_func():
# 標準入力から数列の長さNと数列Aを取得
N = int(input())
A = list(map(int, input().split()))
return N, A
def solve(N, A):
# 最小値を保持する変数ansを無限大で初期化
ans = float("inf")
# 0から2^(N-1)-1までの全ての数Xに対して処理を行う
for X in range(1 << (N-1)):
# Xに2^(N-1)を加えて、N桁の2進数にする
s = X + (1 << (N-1))
# XORの結果を保持する変数cntを0で初期化
cnt = 0
# 現在の区間のOR結果を保持する変数nowを0で初期化
now = 0
# 数列Aの各要素に対して処理を行う
for i, a in enumerate(A):
# nowとその要素のORを取る
now |= a
# もし分割点なら（対応するビットが1なら）
if (s >> i) & 1:
# cntとnowのXORを取る
cnt ^= now
# nowを0にリセットする
now = 0
# 得られたcntとansを比較し、小さい方をansに保存
ans = min(ans, cnt)
# 最小値ansを返す
return ans
# メイン処理
def main():
N, A = io_func()
result = solve(N, A)
print(result)
if __name__ == "__main__":
main()
###
# N: 数列の長さ
# A: 入力された数列
# ans: 最小のXOR値を保持する変数
# X: ビット全探索のための変数
# s: 分割パターンを表す2進数
# cnt: 各分割パターンにおけるXORの結果
# now: 現在の区間のOR結果
# 1. io_func関数:
# - 標準入力から数列の長さNと数列Aを取得する
# 2. solve関数:
# - ビット全探索を用いて、全ての可能な分割パターンを生成
# - 各パターンに対してXORの結果を計算
# - 最小のXOR値を求める
# 3. main関数:
# - io_func関数を呼び出して入力を取得
# - solve関数を呼び出して結果を計算
# - 結果を出力
覚書
長さ4の数列 A = [1, 2, 3, 4] を考えてみる。
数列を区間に分ける
この数列を1つ以上の連続した区間に分けることができる
- [1, 2, 3, 4] (1つの区間)
- [1], [2, 3, 4] (2つの区間)
- [1, 2], [3, 4] (2つの区間)
- [1, 2, 3], [4] (2つの区間)
- [1], [2], [3, 4] (3つの区間)
- [1], [2, 3], [4] (3つの区間)
- [1, 2], [3], [4] (3つの区間)
- [1], [2], [3], [4] (4つの区間)
各区間でORを計算
各区間内の数のビット単位ORを計算する。
- [1, 2, 3, 4] → 1 OR 2 OR 3 OR 4 = 7
- [1], [2, 3, 4] → 1, (2 OR 3 OR 4) = 1, 7
- [1, 2], [3, 4] → (1 OR 2), (3 OR 4) = 3, 7
区間のOR結果のXORを計算
OR計算で得られた結果のビット単位XORを計算する。
- [1, 2, 3, 4] → 7
- [1], [2, 3, 4] → 1 XOR 7 = 6
- [1, 2], [3, 4] → 3 XOR 7 = 4
最小値を求める
すべての可能な分け方について、区間のOR結果のXORを計算の結果の中から最小値を求める。
Discussion