【競技プログラミング】AtCoder Beginner Contest 261_E問題

問題

要約

1. 変数X：初期値Cで初期化される整数値

2. N種類の操作：

   • 操作1 (T_i = 1): X = X and A_i
   • 操作2 (T_i = 2): X = X or A_i
   • 操作3 (T_i = 3): X = X xor A_i

3. 実行手順：
   a) 操作1を実行し、結果を出力
   b) 操作1、2を順に実行し、結果を出力
   c) 操作1、2、3を順に実行し、結果を出力
   d) 最終的に、操作1から操作Nまでを順に実行し、結果を出力

4. 変数情報：

   • X: 操作対象の整数値
   • N: 操作の総数
   • T_i: i番目の操作の種類 (1, 2, または 3)
   • A_i: i番目の操作で使用される整数値
   • C: Xの初期値

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

一覧ページ

アプローチ

ビット演算の性質を利用して、各ビットの状態を追跡する。
0と1の状態を別々に管理し、最終的な結果を合成する。

解法手順

1. 入力値Nと初期値Cを読み取り、変数Xを初期化する。

2. 0のビットマスク（zero）と1のビットマスク（one）を初期化する。

   • zeroは全ビット0で初期化
   • oneは全ビット1（~0）で初期化

3. N回のループを実行し、各操作を処理する。
   a. 操作の種類（T_i）と値（A_i）を読み取る。
   b. 操作の種類に応じてzeroとoneを更新する。

   • AND操作（T_i = 1）の場合：zero &= A_i, one &= A_i
   • OR操作（T_i = 2）の場合：zero |= A_i, one |= A_i
   • XOR操作（T_i = 3）の場合：zero ^= A_i, one ^= A_i
     c. 更新されたzeroとoneを使用してXの値を計算する。
     X = (one & X) | (zero & ~X)
     d. 現在のXの値を出力する。

4. ループが終了したら、最終的なXの値が得られる。

ACコード

ac.py

def io_func():
    # 入力値Nと初期値Cを読み取る
    n, c = map(int, input().split())
    return n, c

def solve(n, c):
    # 変数Xを初期化
    x = c

    # 0のビットマスク（zero）と1のビットマスク（one）を初期化
    zero = 0  # 全ビット0で初期化
    one = ~0  # 全ビット1（~0）で初期化

    # N回のループを実行し、各操作を処理
    for _ in range(n):
        # 操作の種類（T_i）と値（A_i）を読み取る
        t, a = map(int, input().split())

        # 操作の種類に応じてzeroとoneを更新
        if t == 1:  # AND操作
            zero &= a
            one &= a
        elif t == 2:  # OR操作
            zero |= a
            one |= a
        else:  # XOR操作
            zero ^= a
            one ^= a

        # 更新されたzeroとoneを使用してXの値を計算
        x = (one & x) | (zero & ~x)

        # 現在のXの値を出力
        print(x)

if __name__=="__main__":
    # メイン処理
    n, c = io_func()
    solve(n, c)

#############################################
# 変数の意味:
# n: 操作の回数
# c: 初期値
# x: 現在の値
# zero: 0のビットマスク
# one: 1のビットマスク
# t: 操作の種類
# a: 操作の値

# 1. io_func関数:
#    - 標準入力から操作回数nと初期値cを読み取る
#    - 読み取った値を返す
#
# 2. solve関数:
#    - 引数としてnとcを受け取る
#    - xをcで初期化
#    - zeroを0、oneを全ビット1で初期化
#    - n回のループを実行:
#      - 各操作のtとaを読み取る
#      - tに応じてzeroとoneを更新
#      - 新しいxの値を計算
#      - xの値を出力
#
# 3. メイン処理:
#    - io_func関数を呼び出してnとcを取得
#    - solve関数を呼び出して主な処理を実行