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

# 問題
https://atcoder.jp/contests/abc299/tasks/abc299_d

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


# 解法手順1

1. 変数lを1（文字列の先頭）、rをN（文字列の末尾）に初期化する。

2. lがr-1より小さい間、以下の処理を繰り返す:
   a. もしl == r-1なら、答えが見つかったので、lを出力して終了する。
   b. 中間点mを(l+r) // 2で計算する。
   c. m番目の文字について質問する。
   d. 回答が0なら、探索範囲を右半分に絞り、l = mとする。
   e. 回答が1なら、探索範囲を左半分に絞り、r = mとする。

3. ループが終了したら、lが0から1に変わる位置となるので、それを出力する。



# ACコード1
```python:ac.py
def io_func():
    # 文字列の長さNを入力として受け取る
    N = int(input())
    return N

def solve(N):
    # 探索範囲の左端を1に初期化
    left = 1
    # 探索範囲の右端をNに初期化
    right = N

    while left < right:
        # 左端と右端が隣り合っている場合、答えが見つかったので出力して終了
        if left == right - 1:
            print(f"! {left}")
            exit()

        # 中間点を計算
        mid = (left + right) // 2

        # 中間点の文字について質問
        print(f"? {mid}")
        # 回答を受け取る
        response = int(input())

        # 回答に応じて探索範囲を更新
        if response == 0:
            # 0の場合、左端を中間点に移動
            left = mid
        else:
            # 1の場合、右端を中間点に移動
            right = mid

    # ループが終了したら、leftが0から1に変わる位置となるので出力
    print(f"! {left}")

# メイン処理
N = io_func()
solve(N)

###
# N: 文字列の長さ
# left: 探索範囲の左端
# right: 探索範囲の右端
# mid: 探索範囲の中間点
# response: 質問に対する回答（0または1）

# 1. io_func関数:
#    - 標準入力から文字列の長さNを受け取る
# 2. solve関数:
#    - 二分探索を用いて0から1に変わる位置を特定する
#    - while文を使用して探索範囲を徐々に絞り込む
#    - 左端と右端が隣り合った時点で答えが見つかったとみなす
#    - 質問の回答に応じて探索範囲を更新する
#    - 最終的に特定された位置を出力する
# 3. メイン処理:
#    - io_func関数を呼び出してNを取得
#    - solve関数を呼び出して問題を解く

```
## オブジェクト指向版1
```python:ac_object.py
import logging
from abc import ABC, abstractmethod

def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
    formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
    
    file_handler = logging.FileHandler('program_trace.log')
    file_handler.setFormatter(formatter)
    logger.addHandler(file_handler)
    
    return logger

# 入力を処理するインターフェース
class InputProcessor(ABC):
    @abstractmethod
    def get_input(self):
        pass

# 標準入力を処理するクラス
class StandardInputProcessor(InputProcessor):
    def get_input(self):
        return int(input())

# 出力を処理するインターフェース
class OutputProcessor(ABC):
    @abstractmethod
    def output(self, message):
        pass

# 標準出力を処理するクラス
class StandardOutputProcessor(OutputProcessor):
    def output(self, message):
        print(message)

# 二分探索を行うクラス
class BinarySearchSolver:
    def __init__(self, input_processor: InputProcessor, output_processor: OutputProcessor, debug_mode: bool):
        self.input_processor = input_processor
        self.output_processor = output_processor
        self.logger = setup_logger(debug_mode)

    def solve(self, N):
        self.logger.debug(f"探索開始: 文字列の長さ N = {N}")
        left = 1
        right = N

        while left < right:
            self.logger.debug(f"現在の探索範囲: left = {left}, right = {right}")
            
            if left == right - 1:
                self.output_processor.output(f"! {left}")
                self.logger.debug(f"解が見つかりました: {left}")
                return

            mid = (left + right) // 2
            self.logger.debug(f"中間点: mid = {mid}")

            self.output_processor.output(f"? {mid}")
            response = self.input_processor.get_input()
            self.logger.debug(f"質問への回答: response = {response}")

            if response == 0:
                left = mid
                self.logger.debug("左端を中間点に移動")
            else:
                right = mid
                self.logger.debug("右端を中間点に移動")

        self.output_processor.output(f"! {left}")
        self.logger.debug(f"最終的な解: {left}")

# メイン処理を行うクラス
class MainProcessor:
    def __init__(self, input_processor: InputProcessor, solver: BinarySearchSolver):
        self.input_processor = input_processor
        self.solver = solver

    def process(self):
        N = self.input_processor.get_input()
        self.solver.solve(N)

# メイン処理
if __name__ == "__main__":
    debug_mode = False  # デバッグモードを有効にする場合はTrueに設定
    input_processor = StandardInputProcessor()
    output_processor = StandardOutputProcessor()
    solver = BinarySearchSolver(input_processor, output_processor, debug_mode)
    main_processor = MainProcessor(input_processor, solver)
    main_processor.process()
```

### オブジェクト図
![bPBTIiSm3CNl-nIzd4XVO8ZyyKxmGzW3ZB25EkZQqRI2gEzkrtQW9GhRpI3vdUISPHSAu4DSZPWC4CbxkyNmujs4HCxB3o7JSwqnZClUwQx4bwZe4C3EuESJakSOEDRbShUc8cXaLfpLtIqM_Fk0uAVNmPatF2GgMngtOrBV12vGcjjGZO626QSrfkP3VXTBj6_hddvuUOJ57i9pDl8itpDfog.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/21f43e54-ebb9-6d60-e164-36c3255a508c.png)


### オブジェクト指向版1で書くメリット
#### 拡張性と再利用性
```python:ac_object.py
class FileInputProcessor(InputProcessor):
    def __init__(self, filename):
        self.filename = filename

    def get_input(self):
        with open(self.filename, 'r') as f:
            return int(f.readline().strip())

class FileOutputProcessor(OutputProcessor):
    def __init__(self, filename):
        self.filename = filename

    def output(self, message):
        with open(self.filename, 'a') as f:
            f.write(f"{message}\n")

# メイン処理
if __name__ == "__main__":
    debug_mode = True
    input_processor = FileInputProcessor("input.txt")
    output_processor = FileOutputProcessor("output.txt")
    solver = BinarySearchSolver(input_processor, output_processor, debug_mode)
    main_processor = MainProcessor(input_processor, solver)
    main_processor.process()
```

#### テスト容易性
```python:ac_object.py
import unittest
from unittest.mock import MagicMock

class TestBinarySearchSolver(unittest.TestCase):

    def setUp(self):
        # モックの準備
        self.input_processor = MagicMock()
        self.output_processor = MagicMock()
        self.debug_mode = False
        
        # BinarySearchSolverのインスタンスを作成
        self.solver = BinarySearchSolver(self.input_processor, self.output_processor, self.debug_mode)

    def test_solve_finds_correct_value(self):
        self.input_processor.get_input.side_effect = [1, 0, 0, 0, 0]
        N = 10
        
        self.solver.solve(N)
        
        # 最終的な出力が正しいことを確認
        self.output_processor.output.assert_called_with("! 4")

    def test_solve_when_left_equals_right_minus_one(self):
        self.input_processor.get_input.side_effect = [1] 
        N = 2
        
        self.solver.solve(N)
        
        # 最終的な出力が正しいことを確認
        self.output_processor.output.assert_called_with("! 1")

    def test_solve_with_no_response(self):
        self.input_processor.get_input.side_effect = [1, 1, 1]  # 常に右側へ移動する応答
        N = 10
        
        self.solver.solve(N)
        
        # 最終的な出力が正しいことを確認
        self.output_processor.output.assert_called_with("! 1")

if __name__ == '__main__':
    unittest.main()

```