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

# 問題
https://atcoder.jp/contests/abc380/tasks/abc380_d

# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)

## Before
[AtCoder Beginner Contest 380_C 問題]()

## Next
[AtCoder Beginner Contest 380_E 問題]()

## その他・記事まとめ
[Unity関連 / Qiita](https://qiita.com/o_chan_t/items/0b5ae1e7c45f106082b8)


# 解法手順1

## 操作のパターン分析 (コアアルゴリズム)

### 文字列長の変化パターン
| 操作回数 | 文字列長 | 内部構造 |
|---------|----------|----------|
| 0       | L        | S        |
| 1       | 2L       | S + T    |
| 2       | 4L       | S+T + T'+S' (T'=反転後のT) |
| 3       | 8L       | ...      |

**特性**:  
文字列長は2^m回操作後 → L * 2^m

### 対応位置の逆算法
**クエリK_iの位置を逆順にトレース**:  
操作回数mを逆順に確認し、現在の位置を原始の位置に戻す

**例**:  
操作3回目以降 → 位置が8L超える → 7L以下なら4L部分に存在

---

## 具体的なアルゴリズム実装ステップ

### 必要操作回数の計算
1. **最大クエリ値の決定**: max(K_list)
2. **必要操作回数の計算**:  
```python
   operation_lengths = [len(S)]
   while operation_lengths[-1]  0 else 0
    if current_pos > threshold:
        current_pos -= threshold
        is_flipped = not is_flipped
```

**例**:  
K_i = 12, S長5 → 操作2回後長20 → 12 3 → 5-3=2 → 反転フラグON
   - 2 3 → 4-3=1 → 反転フラグON
3. **元位置1**: "Y" → 反転→ "y"
**結果**: "y"

---


### 操作回数計算部
```python
operation_lengths = [len(S)]
while operation_lengths[-1]  0 else 0
    if current_pos > threshold:
        current_pos -= threshold
        is_flipped = not is_flipped
```
→ 最大操作回数から逆順に位置を減算

### 文字決定部
```python
original_char = S[current_pos - 1]
final_char = original_char.swapcase() if is_flipped else original_char
```
→ 反転フラグで大小文字を切り替え

---

**パターン認識**:  
操作m回後の文字列構造 → 前半m回操作前の文字列と反転部分が交互に配置

**逆トレースの正当性**:  
各操作で文字列がS + T → T' + S' → S' + T' → ... となり、位置の特定が可能

**計算量の最適化**:  
log2(max_K)回の分割 → 1e100回でもlog2(1e100)=~333回で完了




# ACコード1(※提出時はLoggerを削除する必要あり※)
```python:ac.py
import logging

def setup_logger(debug_mode):
    """ロガーをセットアップする関数"""
    logger = logging.getLogger(__name__)
    if not logger.handlers:
        logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
        formatter = logging.Formatter('%(asctime)s - %(levelname)s - %(message)s')
        
        file_handler = logging.FileHandler('solution_trace.log', encoding='utf-8')
        file_handler.setFormatter(formatter)
        logger.addHandler(file_handler)
    
    logger.debug("ロガーセットアップ完了 | デバッグモード: %s", debug_mode)
    return logger

def io_func():
    """入出力処理を担当する関数"""
    S = input().strip()
    Q = int(input())
    K_list = list(map(int, input().split()))
    return S, Q, K_list

def determine_character(S, K_list, logger):
    """文字判定のコアロジックを処理する関数"""
    original_length = len(S)
    max_K = max(K_list) if K_list else 0
    logger.debug("最大K値: %d | 初期文字列長: %d", max_K, original_length)

    # 操作回数と各操作後の文字列長を計算
    operation_lengths = [original_length]
    while operation_lengths[-1] < max_K:
        next_length = operation_lengths[-1] * 2
        operation_lengths.append(next_length)
        logger.debug("操作回数: %d → 文字列長: %d", len(operation_lengths)-1, next_length)

    total_operations = len(operation_lengths) - 1
    logger.debug("必要操作回数確定: %d", total_operations)

    results = []
    for idx, K in enumerate(K_list):
        logger.debug("クエリ %d 処理開始 | K値: %d", idx+1, K)
        current_pos = K
        is_flipped = False

        # 操作を逆順にトレースして位置を特定
        for current_op in range(total_operations, -1, -1):
            threshold = operation_lengths[current_op-1] if current_op > 0 else 0
            logger.debug("操作 %d | 閾値: %d | 現在位置: %d | 反転状態: %s",
                        current_op, threshold, current_pos, is_flipped)

            if current_op == 0:
                break

            if current_pos > threshold:
                current_pos -= threshold
                is_flipped = not is_flipped
                logger.debug("位置更新 → %d | 反転状態 → %s", current_pos, is_flipped)

        # 文字判定と反転処理
        original_char = S[current_pos - 1]
        final_char = original_char.swapcase() if is_flipped else original_char
        logger.debug("決定文字: %s (原文字: %s 反転: %s)",
                    final_char, original_char, is_flipped)

        results.append(final_char)
    
    return results

def solve(logger):
    """メイン処理を担当する関数"""
    S, Q, K_list = io_func()
    logger.debug("入力受取完了 | S: %s | Q: %d | K_list: %s", S, Q, K_list)
    
    results = determine_character(S, K_list, logger)
    print(' '.join(results))
    logger.debug("結果出力完了")

def main():
    """エントリーポイント"""
    logger = setup_logger(debug_mode=False)  # デバッグ時はTrueに変更
    logger.debug("プログラム開始")
    solve(logger)
    logger.debug("プログラム終了")

if __name__ == "__main__":
    main()


```