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 011_C問題

Posted at

問題

要約

  1. 最初に数字 N が与えられる。

  2. プレイヤーは1, 2, 3の中から好きな数字を選び、Nから引き算を行う。

  3. この引き算の処理は最大100回まで行うことができる。

  4. 目標は、最終的に数字を0にすること。

  5. 3つのNG数字が与えられており、計算途中でこれらの数字になってはいけない。一時的にでもNG数字になった場合、ゲームは失敗となる。

プレイヤーは、与えられたNとNG数字を考慮しながら、0にたどり着けるかどうかを判断する。

目標達成が可能な場合は「YES」、不可能な場合は「NO」を出力する。

変数情報

  • N: 最初に与えられる数字
  • NG数字: 3つ与えられる、計算途中でなってはいけない数字

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

一覧ページ

アプローチ

動的計画法（DP）を使用して最小の手数で目標に到達できるかどうかを判断する

解法手順

  1. 入力を受け取る：

    • 初期値Nを整数として読み込む
    • 3つのNG数字を整数として読み込み、リストに格納する

  2. DPテーブルを初期化する：

    • サイズN+1の配列を作成し、全ての要素を非常に大きな値（ここでは10^10）で初期化する
    • DP[i]は、iという数字に到達するための最小の手数を表す
    • DP[0]を0に設定する（0に到達するのに必要な手数は0）

  3. DPテーブルを埋める：

    • 1からNまでの各数字iについて以下を行う：
      • iがNG数字の場合はスキップする
      • i-1, i-2, i-3（それぞれが0以上の場合）のDP値の最小値を求める
      • 最小値が見つかった場合、DP[i]をその値+1と10^10の小さい方に設定する

  4. 結果を判定する：

    • DP[N]が100以下であれば「YES」を出力する（100回以内の操作で0に到達可能）
    • そうでなければ「NO」を出力する（0に到達不可能、または100回を超える操作が必要）

ACコード

ac.py
def io_func():
    # 目標の数値Nを入力として受け取る
    n = int(input())
    # 3つのNG数字を入力として受け取り、リストに格納する
    ng = [int(input()) for _ in range(3)]
    return n, ng

def solve(n, ng):
    # 無限大を表す値を設定
    inf = 10 ** 10
    # 動的計画法のためのリストを初期化（長さN+1、全ての要素をinfで初期化）
    dp = [inf for _ in range(n + 1)]
    # 開始点（0）の手数を0に設定
    dp[0] = 0
    
    # 1からNまでの各数字について処理を行う
    for i in range(1, n + 1):
        # 現在の数字がNG数字の場合、スキップする
        if i in ng:
            continue
        # 到達可能な最小手数を格納する変数を初期化
        tmp = inf
        # i-1, i-2, i-3の中で到達可能な数字の最小手数を探す
        for j in range(1, 4):
            if i - j < 0:
                continue
            tmp = min(tmp, dp[i - j])
        # 到達可能な場合、手数を更新する（ただし100以下の場合のみ）
        if tmp != inf:
            dp[i] = min(tmp + 1, inf)
    
    # 最終的にNに到達可能かどうかを判断し、結果を出力する
    if dp[-1] <= 100:
        print("YES")
    else:
        print("NO")

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

###
# n: 目標の数値
# ng: NG数字のリスト
# inf: 無限大を表す値
# dp: 各数字に到達するための最小手数を格納するリスト
# tmp: 一時的に最小手数を格納する変数

# 1. io_func関数で入力を受け取る
#    - 目標の数値nと3つのNG数字を入力として受け取る
# 2. solve関数で主な処理を行う
#    - 動的計画法のためのdpリストを初期化
#    - 1からnまでの各数字について以下の処理を行う
#      a. NG数字の場合はスキップ
#      b. NG数字でない場合、i-1, i-2, i-3の中で到達可能な数字の最小手数に1を加えた値を計算
#      c. 計算した値が100以下の場合、その値をdp[i]に格納
#    - 最終的にdp[n]が100以下であれば"YES"を、そうでなければ"NO"を出力
# 3. メイン処理でio_func関数とsolve関数を呼び出す

数学的帰納法による証明

n=0の確認

dp[0] = 0 と初期化されていうる。
開始点（0）に到達するための手数が0であることを表す。
基底ケースは正しく設定されています。

帰納仮定

k ≥ 0 に対して、0 ≤ i ≤ k のすべての i について dp[i] が正しく計算されていると仮定する。
ここで、dp[i] は数字 i に到達するための最小手数を表す。

n = k + 1の証明

k + 1 が NG 数字の場合：

コード内の条件分岐 if i in ng: continue により、dp[k+1] は更新されず、inf のままとなる。
NG 数字には到達できないことを正しく表現している。

k + 1 が NG 数字でない場合

以下の処理が行われる。

tmp = inf
for j in range(1, 4):
    if i - j < 0:
        continue
    tmp = min(tmp, dp[i - j])
if tmp != inf:
    dp[i] = min(tmp + 1, inf)

この処理は、k+1 に到達する方法として、(k+1)-1, (k+1)-2, (k+1)-3 の中で到達可能な数字からの最小手数に1を加えた値を計算している。
帰納仮定により、dp[k], dp[k-1], dp[k-2] は正しく計算されているため、dp[k+1] も正しく計算されることが保証される。

制約条件の確認

コード内の dp[i] = min(tmp + 1, inf) により、dp[i] の値は常に inf 以下に保たれる。
また、最終的な判定で dp[-1] <= 100 を使用しているため、100手以内で到達可能かどうかが正しく判断されている。

結論

以上の証明により、すべての n ≥ 0 に対して、dp[n] が正しく計算されることが示された。

変数の意味と遷移の説明

  • dp[i]: 数字 i に到達するための最小手数を格納します。

  • tmp: 現在の数字 i に到達するための候補となる最小手数を一時的に保存します。

  • 遷移は、各数字 i について、i-1, i-2, i-3 からの遷移を考慮している。

ループ変数について

  • 外側のループ変数 i は、1から n までの各数字を表す。
  • 内側のループ変数 j は、1, 2, 3 の3つの値を取り、i-j が i に到達する直前の数字の候補となる。

解答に該当する箇所

最終的な解答は、dp[n] の値が100以下であるかどうかで判断される。

この動的計画法が最適解を与える理由

この動的計画法は、各数字に到達するための最小手数を順番に計算している。
各ステップで、それまでに計算された最小手数を利用して次の数字への最小手数を求めているため、最終的に得られる dp[n] は必ず最小手数となる。
また、NG数字への到達を適切に処理し、100手以内という制約も考慮しているため、問題の条件を満たす最適解を与えることが保証される。

思考過程

  1. 各数字に到達するための最小手数を記録する必要がある。
  2. 小さい数字から順に計算していけば、大きい数字の結果を効率的に求められる。
  3. NG数字は避ける必要がある。
  4. 最終的に目標の数字（N）に到達できるかどうかを判断する。

計算量の概算

  • 時間計算量: O(N)
    DPテーブルの各要素を1回ずつ計算するため、Nに比例する。
  • 空間計算量: O(N)
    サイズN+1のDPテーブルを使用するため。

その他周辺知識

数列と漸化式

dp = [inf for _ in range(n + 1)]
dp[0] = 0

ここでは、長さn+1の数列dpを定義している。
dp[i]は、数iに到達するための最小手数を表す。

動的計画法（漸化式の応用）

for i in range(1, n + 1):
    if i in ng:
        continue
    tmp = inf
    for j in range(1, 4):
        if i - j < 0:
            continue
        tmp = min(tmp, dp[i - j])
    if tmp != inf:
        dp[i] = min(tmp + 1, inf)

dp[i] = min(dp[i-1], dp[i-2], dp[i-3]) + 1 (ただし、i ∉ ng かつ i > 0)

この漸化式は、「iに到達するための最小手数は、i-1, i-2, i-3のいずれかから1手で到達できる最小のものに1を加えたもの」という考え方を表現している。

動的計画法による最小ステップ数計算関数

essence.py
def min_steps_to_target(target, forbidden_numbers, max_step=3, max_allowed_steps=100):
    """
    動的計画法を使用して、指定された目標値に到達するための最小ステップ数を計算します。

    Args:
    target (int): 到達すべき目標値
    forbidden_numbers (list): 使用できない数値のリスト
    max_step (int): 1回のステップで進める最大値（デフォルト: 3）
    max_allowed_steps (int): 許容される最大ステップ数（デフォルト: 100）

    Returns:
    int: 目標値に到達するための最小ステップ数。到達不可能な場合は float('inf') を返します。
    """
    inf = float('inf')
    dp = [inf] * (target + 1)
    dp[0] = 0

    for i in range(1, target + 1):
        if i in forbidden_numbers:
            continue
        tmp = inf
        for j in range(1, max_step + 1):
            if i - j < 0:
                continue
            tmp = min(tmp, dp[i - j])
        if tmp != inf:
            dp[i] = min(tmp + 1, inf)

    return dp[target] if dp[target] <= max_allowed_steps else inf

# 使用例
target = 10
forbidden_numbers = [4, 7, 9]
result = min_steps_to_target(target, forbidden_numbers)
print(f"最小ステップ数: {result}")
print(f"到達可能: {'はい' if result != float('inf') else 'いいえ'}")
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?