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 299_D問題

Posted at

問題

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

一覧ページ

解法手順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

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

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

オブジェクト指向版1で書くメリット

拡張性と再利用性

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()

テスト容易性

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()
0
0
0

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?