💡
【競技プログラミング】AtCoder Beginner Contest 011_C問題

2024/12/23に公開
 趣旨AtCoderの問題は、同じ問題でも別解があるし、過去に解けた問題も改めて挑戦すると解き方が分からなくなることが、私には多々あります。

そういうときは、何回も挑戦することで、何度もやっていけば自然とパターンが身につくので、それを目指して投稿したいと思います。

個人的に、一番「良い！」って思った解放を最終的にはストックして皆様に公開できればと思っております。

基本的には、Qiita投稿とは別のコードになっていると思います。（解法は同じかもしれませんが、、、）

 問題https://atcoder.jp/contests/abc011/tasks/abc011_3

 要約最初に数字N が与えられる。
プレイヤーは1, 2, 3の中から好きな数字を選び、Nから引き算を行う。
この引き算の処理は最大100回まで行うことができる。
ゲームの目標は、最終的に数字を0にすること。
3つのNG数字が与えられ、計算途中でこれらの数字になってはいけない。一時的にでもNG数字になった場合、ゲームは失敗となる。
NG数字がNと同じ場合も失敗となる。
プレイヤーの課題は、このゲームが目標達成可能かどうかを判断する。
目標達成可能な場合は「YES」
目標達成不可能な場合は「NO」
N: 最初に与えられる数字
NG数字: 3つ与えられる、計算途中でなってはいけない数字

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

 過去の回答Qiita(2024年12月15日)

 アプローチ貪欲法を用いて最適な引き算の手順を見つける

 解法手順Nを入力として受け取る。
3つのNG数字を入力として受け取り、リストに格納する。
NG数字のリストをソートする。
NがNG数字のリストに含まれているかチェックし、含まれていれば「NO」を出力して終了する。
変数kを0で初期化する（kは引いた数の合計を表す）。
最大100回のループを開始する：

a. k+3がNG数字でなければ、kに3を加える。

b. そうでなく、k+2がNG数字でなければ、kに2を加える。

c. そうでなく、k+1がNG数字でなければ、kに1を加える。

d. 上記のいずれも実行できない場合、ループを終了する。

e. kがN以上になったらループを終了する。
ループが正常に終了した（100回未満で終了した）場合は「YES」を出力する。
そうでない場合は「NO」を出力する。

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

def solve(n, lst):
    # 最大試行回数を設定
    r = 100
    
    # NG数字のリストをソートする
    lst.sort()
    
    # NがNG数字のリストに含まれているかチェック
    if n in lst:
        print("NO")
    else:
        # 引いた数の合計を表す変数kを初期化
        k = 0
        
        # 最大100回のループを開始
        while r > 0:
            # k+3がNG数字でなければ、kに3を加える
            if k+3 not in lst:
                k += 3
            # k+2がNG数字でなければ、kに2を加える
            elif k+2 not in lst:
                k += 2
            # k+1がNG数字でなければ、kに1を加える
            elif k+1 not in lst:
                k += 1
            # 上記のいずれも実行できない場合、ループを終了
            else:
                r = 1
            
            # kがN以上になったらループを終了
            if n <= k:
                break
            else:
                r -= 1
        
        # ループが正常に終了した場合は"YES"を出力、そうでない場合は"NO"を出力
        if r > 0:
            print("YES")
        else:
            print("NO")

# メイン処理
n, lst = io_func()
solve(n, lst)

###
# n: 目標の数
# lst: NG数字のリスト
# r: 残りの試行回数
# k: 現在までに引いた数の合計

# 1. io_func関数で入力を受け取る
#    - 目標の数nを入力として受け取る
#    - 3つのNG数字を入力として受け取り、リストlstに格納する
# 2. solve関数で主な処理を行う
#    - 最大試行回数rを100に設定
#    - NG数字のリストlstをソートする
#    - nがlstに含まれているかチェックし、含まれていれば"NO"を出力して終了
#    - 引いた数の合計kを0で初期化
#    - 最大100回のループを開始:
#      - k+3, k+2, k+1の順でNG数字でないかチェックし、可能な最大の数を加える
#      - どの数も加えられない場合、ループを終了
#      - kがn以上になったらループを終了
#      - 試行回数rを1減らす
#    - ループが正常に終了した場合は"YES"を、そうでない場合は"NO"を出力
# 3. メイン処理でio_func関数とsolve関数を呼び出す```
趣旨

問題

要約

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

過去の回答

アプローチ

解法手順

ACコード

Discussion
