<Pythonコード付き>Aランク解きたい人超必見！！Aランク問題全てを考察から解法まで超丁寧に解説

0. はじめに

みんなでAランク問題を解こう！ハッピー！

気を取り直して、簡単な自己紹介をします。

• 高校生
• 記事投稿時AtCoder緑(989) -> yuuDot
• 競技プログラミングをメインにプログラミングをしている
• 2月ごろに始めたときはif, for, whileなどがわかるくらい（continue ?, def ? なんすかそれ、みたいな感じでした）
• Qiita初投稿。不備などあったら是非教えてください。

今回は競技プログラミングをしていなかった頃の自分にもわかるくらい、丁寧に自分の考え方などを書いていこうと思います。
少しでもアルゴリズム、プログラミングのすばらしさを知っていただければ幸いです。

さあ、行こう！

1. Aランク問題の個人的な印象

今回全5問のAランク問題をすべて解いてみたところ、完全に典型的な処理を適用するものと、考察を行い、それに適したアルゴリズムを適用するものの二つに分かれていると感じました。

典型的なもの

• お菓子の詰め合わせ
• じゃんけんの手の出し方
• 本の整理

やや考察が必要なもの

• ハノイの塔
• 山折り谷折り

あくまで個人的な感想です

やり方さえ知っていれば典型的なものはすぐに解けると思います。
しかし、考察が必要なものは典型を知っていることに加え、観察、ひらめきが必要になるので、典型から解くことをお勧めします。

それでは実際に解いていきましょう！

2. 考察および回答

問題は公開されているので、そちらをご覧ください。

また、記事中で$O(N)$のように書いてあるときがありますが、これは計算量を表したものです。例えば、$O(N^2) = 10^6$ のように書いていたら、このプログラムは$10^6$回の計算を行う必要があるということです。
Pythonで単純な計算なら、1秒あたり$10^7$程度行えると考えれば大丈夫です。詳しくはこちら、けんちょんさんのとっても素晴らしい記事で解説されているので、時間がある方はこちらもご覧ください。絶対に見るべきです。

1, お菓子の詰め合わせ

題意としては、「たくさんの種類のお菓子をできるだけ目標金額に近づけて買ってね、種類たくさんが優先だよ」というものです。
今回はお菓子の数Nは最大で N=20であるため、すべての組み合わせ（選ぶ、選ばない）を試しても、その組み合わせは、$2^{20} = 1048576$ 通りであり、さらに買ったお菓子の合計金額を計算するパートは$O(N)$で行えるため、大まかな計算量は$2×10^6$程度であると見積もられ、この問題に対しては十分高速に解くことができます。

また、選ぶ、選ばないのように状態が二通りである場合によく用いられる典型的全探索（すべて試す）アルゴリズムであるbit全探索を使います。

例えばN = 3であるとき、

0	1	2	3	4	5	6	7
0	1	0	1	0	1	0	1	$2^0$
0	0	1	1	0	0	1	1	$2^1$
0	0	0	0	1	1	1	1	$2^2$

このように0~7までの8個の数字を利用し、0の部分を選ばない、1の部分を選ぶとすれば、すべての組み合わせが列挙できていることがわかります。このことを応用したものがbit全探索と呼ばれる手法です。二進数表記の演算にはbit演算が便利なので、これを機に調べてみましょう！

以上の考察より次の回答が得られます。

回答例 (クリックして開く)

n, x = map(int, input().split())
price = [int(input()) for _ in range(n)]

# 最大の購入できるお菓子の数
mx_buy = 0
# 最小のお釣り
mn_change = float("INF")

for mask in range(1 << n):
    price_sum = 0
    buy = 0
    for i in range(n):
        # mask(0, 1, ... 2**n - 1)を2進数であらわしたとき、i bit目が1であるかどうか判定
        if (mask >> i) & 1:
            price_sum += price[i]
            buy += 1

    change = x - price_sum
    # お釣りが正（お菓子を買える）は絶対条件でさらに、
    #「今までで一番多くのお菓子を買える」または「同じ量買えるが、お釣りが小さい」とき、答えを更新
    if change >= 0 and (mx_buy < buy or (mx_buy == buy and mn_change > change)):
        mx_buy = max(mx_buy, buy)
        mn_change = change

print(mn_change)

2. じゃんけんの手の出し方

題意は「相手の出す手がすべてわかっているとき、指定された本数しか指を出せないときには最大で何勝できるか」というものです。
私は、この問題を見た瞬間にDP(動的計画法)だ！ と思いました。(DPではない回答も記載しています。DPは飛ばしていただいても構いません。）

動的計画法とは、簡単に言うとN回目までの答えがわかっているとき、N+1回目の答えはすぐに出せる時に使える手法です。

今回の問題に対しての具体的な操作は次の通りです。（細かい部分は省略しているのでコードを見てください。）

1. DPという二次元リスト(リストの中にリストがあるもの)を作りすべての値を-1にする。
   $DP[i][j] = i回目のじゃんけんで、指の合計がjであるとき達成できる最大の勝利数$と定義する。
2. $DP[0][0] = 0$(0回のじゃんけん、すなわち、じゃんけんをしていないときは出している指は0で、勝利数は0しかありえないため)とする。
3. $i = 0$の時の動作を示します。$j = 0, 1, ..., m$とし、現在、相手の手はパーであるとします。
   もし$DP[i][j] ≠-1$であるとき、次の操作をする
   • グーを出すと勝てない、指は出していないため、$DP[i + 1][j] = DP[i][j]$とする。
   • チョキを出すと勝つ、指は二本出しているため、$DP[i + 1][j + 2] = DP[i][j] + 1$とする
   • パーを出すと勝てない、指は五本出しているため、$DP[i + 1][j + 5] = DP[i][j]$とする
4. $i = 0, 1, 2, ..., n - 1$まで3.の操作を繰り返す。(リストの範囲外に行かないように注意！）

簡略化のためDPを更新するときにmaxはとっていませんが、maxを必ず取ってください(大きいほうの値を採用してください）。
$DP[i][12] = 3, DP[i][15] = 1$などのとき、$DP[i + 1][15]$などを小さいほうの値で上書きしないよう注意してください。

$i = 0, 1, 2, ..., n - 1$のループの中でそれぞれ、 $j = 0, 1, ..., m$ のループをするため、計算量は$O(NM) = 5×10^6$となり十分高速です。

以上のものを実装したものがこちらです。

回答例（クリックして開く）

n, m = map(int, input().split())
s = input()

# dpテーブルを初期化
dp = [[-1] * (m + 1) for _ in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for j in range(m + 1):
        # 到達不可能でないならば計算する
        if dp[i][j] != -1:
            if s[i] == "G":
                # 範囲外に行かないように事前にチェックする
                if j + 5 <= m:
                    dp[i + 1][j + 5] = max(dp[i + 1][j + 5], dp[i][j] + 1)
                if j + 2 <= m:
                    dp[i + 1][j + 2] = max(dp[i + 1][j + 2], dp[i][j])
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

            elif s[i] == "C":
                if j + 5 <= m:
                    dp[i + 1][j + 5] = max(dp[i + 1][j + 5], dp[i][j])
                if j + 2 <= m:
                    dp[i + 1][j + 2] = max(dp[i + 1][j + 2], dp[i][j])
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + 1)

            elif s[i] == "P":
                if j + 5 <= m:
                    dp[i + 1][j + 5] = max(dp[i + 1][j + 5], dp[i][j])
                if j + 2 <= m:
                    dp[i + 1][j + 2] = max(dp[i + 1][j + 2], dp[i][j] + 1)
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

# n回のじゃんけんが終わり、m本の指を出すときの最大値がdp[n][m]となる
print(dp[n][m])

また、次のようなアルゴリズムでもこの問題を解くことができます。公式解説と同じです。

1. 相手の出す手を事前に数えておく
2. 出す指の本数の合計は$2×(チョキを出す回数) + 5×(パーを出す回数)$と求められ、残りはグーを出したことにしてよい。
3. よって、チョキ（またはパー）を$0, 1, 2,...$回出したとき、パー（またはチョキ）は何回出すことができるかを求め、それによって何回勝つことができるか求められれば良い。

それを実装したのが次のコードです。

回答例（クリックして開く）

n, m = map(int, input().split())
s = input()

# 敵がグー、チョキ、パーそれぞれ何回出しているか求める
cnt = {"G": 0, "C": 0, "P": 0}
for i in s:
    cnt[i] += 1

ans = 0
# m = 0であるときに正しく計算できるようにループの範囲をm + 1にする。
for i in range(m + 1):
    # パーだけで出す指の本数を超えると、これ以上のところで題意が満たされることはない
    if i * 5 > m:
        break
        
    # パーを出すのはi回
    p = i
    # パーをi回出したとき、目標の指の本数にできるか判定
    if (m - 5 * p) % 2 != 0:
        continue
        
    # チョキを出す回数
    c = (m - 5 * p) // 2
    
    # グーを出す回数
    g = n - p - c
    # グーを出す回数が負であったら処理を飛ばす（n = 4, m = 20でi = 0のときなど）
    if g < 0:
        continue

    # 答えを更新
    # グー、チョキ、パーそれぞれで最大の勝てる数を求める
    ans = max(ans, min(cnt["C"], g) + min(cnt["P"], c) + min(cnt["G"], p))

print(ans)

3.本の整理

題意は「左から$1...N$番目の本が本$1...N$でないなら$N$番目の本と本$N$を入れ替える。何回入れ替えることになるか」というものです。
言われたとおりに操作をしようとすると、すべての本を左から順に見るのに$O(N)$、交換すべき本を探すのに$O(N)$かかってしまい、全体で$O(N^2) = 10^{10}$になり、実行制限時間には間に合いません。
そこでどちらかの$O(N)$を削減することを考えます。具体的には交換すべき本を探す時間を短縮し$O(1)$にします。
そのためには本$N$が本棚のどこにあるか、という情報を持つ連想配列$pos$（Pythonでいう辞書)を用意し、それを更新していくことを考えます。

それを実装したのが次のコードです。

回答例（クリックして開く）

n = int(input())
a = list(map(int, input().split()))
# 値が扱いずらいので0-indexedに直す
na = [i - 1 for i in a]
# 0はここにあるよ、1はここにあるよ...という辞書を作成
pos = {val: index for index, val in enumerate(na)}
# 答え、入れ替えるたびに加算していく
ans = 0

for i in range(n):
    # 今見ている本の番号と、場所が一致しないとき
    if na[i] != i:
        # 入れ替える本の場所を取得
        change_pos = pos[i]
        # 入れ替える
        na[i], na[change_pos] = na[change_pos], na[i]

        # 入れ替えた二つの本の場所を更新(na[i]は二度とつかわないから更新しなくてもよい)
        pos[na[i]] = i
        pos[na[change_pos]] = change_pos
        
        # 入れ替えたので答えを+1
        ans += 1

print(ans)

Pythonの記法では、val1, val2 = val2, val1のようにすると、おそらく$O(1)$で入れ替えることができます。（たしか参照元を入れ替えるだけなので早い)

4.ハノイの塔

題意は「ハノイの塔を最善手でプレイするとき、$t$ターン目の盤面はどのようになっているか」というものです。
よって、ハノイの塔を最善手で実際に動かすプログラムを作ればこの問題に正解できそうだというのがわかります。

結論として、ハノイの塔は再帰を使って解くことができます。
再帰とはある関数の中でその関数自身を呼び出すことです。あまりイメージが付かないと思うので具体的に説明をします。

ハノイの塔は以下の手順で最短クリアできることが知られています。

一番下の円盤の数字を$N$とし、その上に$N-1, N- 2, ..., 1$の円盤が乗っている状態のことを塔と呼びます。動かしたい塔の高さをlv、どこの杭から動かすかをmove_from、どこの杭に動かしたいかをmove_to、もう一つの中継に使う杭をotherとします。ここで、杭を左から順に0, 1, 2と番号を付け、円盤のことをdiskと呼びます。

lv = 1の場合を考えます。この場合は明らかに1枚の円盤diskを杭move_fromから杭move_toに動かすだけです。

lv = n (n ≧ 2)の場合を考えます。このとき、一番下を除いたlv = n - 1の塔をotherに動かしたのち、一番下のdiskをmove_fromからmove_toに動かし、otherにある塔lv n - 1の塔をmove_toに動かせばいいことがわかります。

この処理を行うときに再帰を用います。lv = n - 1の塔を動かすにはlv = n - 2の塔を動かし、そのためにはlv = n - 3の塔を動かし、そのためには...と続くようなイメージです。

$n = 3$のときのプログラムの動作イメージ（クリックして開く）

便宜上、hanoiを動作する関数とし、hanoi Nと番号を付けて区別します。

• hanoi 1(lv = 3, from = 0, to = 2, other = 1)
  • hanoi 2(lv = 2, from = 0, to = 1, other = 2)
    • hanoi 3(lv = 1, from = 0, to = 2, other = 1)
      • hanoi 4(lv = 0, from = 0, to = 1, other = 2)
      • 4は何も起きない
    • 3 が実行される
      • hanoi 5(lv = 0, from = 1, to = 2, other = 0)
      • 5は何も起きない
  • 2 が実行される
  • hanoi 6(lv = 1, from = 2, to = 1, other = 0)
    • hanoi 7(lv = 0, from = 2, to = 0, other = 1)
    • 7は何も起きない
  • 6 が実行される
    • hanoi 8(lv = 0, from = 0, to = 1, other = 2)
    • 8は何も起きない
• 1 が実行される
• hanoi 9(lv = 2, from = 1, to = 2, other = 0)
  • hanoi 10(lv = 1, from = 1, to = 0, other = 2)
    • hanoi 11(lv = 0, from = 1, to = 2, other = 0)
    • 11は何も起きない
  • 10 が実行される
    • hanoi 12(lv = 0, from = 2, to = 0, other = 1)
    • 12は何も起きない
  • 9 が実行される
  • hanoi 13(lv = 1, from = 0, to = 2, other = 1)
    • hanoi 14(lv = 0, from = 0, to = 1, other = 2)
    • 14は何も起きない
  • 13 が実行される
    • hanoi 15(lv = 0, from = 1, to = 2, other = 0)
    • 15は何も起きない

手作業で頭こんがらがりながら書いてたけど、コード書いたんだから、printで数値出力させれば一発だったのは秘密です

以上のことを実装すれば次のコードになります。

回答例（クリックして開く）

@shiracamus(しらかみゅ)さんの指摘で引数を減らせました(グローバルのリストを直接操作しても問題なかった)。ありがとうございます！

# 再帰的に処理することで、lv = n の塔を動かすことができる関数
def solve_hanoi(lv, move_from, move_to, other, cnt):
    if lv > 0:
        # cntを更新、lv = nより小さい上に乗っているdiskをいったん使ってない杭に動かしたい
        cnt = solve_hanoi(lv - 1, move_from, other, move_to, cnt)
        # 一番下の円盤をmove_toに移動させる
        disk = hanoi[move_from].pop()
        hanoi[move_to].append(disk)
        # 移動したので、手数のカウントを一つ増やす
        cnt += 1
        # 指定された手数なら答えを出力してプログラムを終了
        if cnt == t:
            for val in hanoi:
                if val:
                    print(*val)
                else:
                    print("-")
            exit()

        # cntを更新、otherに動かしたlv = n - 1の塔を、move_toにある大きさがlvのdisk上に動かしたい
        cnt = solve_hanoi(lv - 1, other, move_to, move_from, cnt)

    # cntを更新するためにcntをreturn
    return cnt


n, t = map(int, input().split())
# リストの更新は末尾をいじるのが早いから、一番小さい円盤をリストの末尾にする
hanoi = [[i for i in range(n, 0, -1)], [], []]
cnt = 0
# 円盤n枚を、一番左の杭(0)から、一番右の杭(2)に動かす、中継の杭は(1)
solve_hanoi(n, 0, 2, 1, cnt)

あまり美しくない？回答例（クリックして開く）

競プロとかの範囲では十分だと思います。global宣言をして、さらに引数を削減！

def solve_hanoi(lv, move_from, move_to, other):
    global cnt
    if lv > 0:
        solve_hanoi(lv - 1, move_from, other, move_to)
        
        disk = hanoi[move_from].pop()
        hanoi[move_to].append(disk)
        cnt += 1
        
        if cnt == t:
            for val in hanoi:
                if val:
                    print(*val)
                else:
                    print("-")
            exit()

        solve_hanoi(lv - 1, other, move_to, move_from)


n, t = map(int, input().split())
hanoi = [[i for i in range(n, 0, -1)], [], []]
cnt = 0
solve_hanoi(n, 0, 2, 1)

5.山折り谷折り

いよいよ最後の問題です。題意は「十分大きな紙があり、常に折り目が右に来るように半分に折っていく。$N$回折った後に紙を開くと、すべての折り目について、一番左から順番に山折りか谷折りどちらであるか」というものです。
問題文を読んだとき、自分は全くイメージが付かなかったので、家にあるその辺の紙で実験をしました。

実験の結果として、答えの長さは$2^n - 1$である。山折りになるか谷折りになるかは、表で折られたか、裏でおられたかに依存する、ということを得られました。
以上のことから、実際に紙が表向きであるか、裏向きであるかを管理しながらシミュレーションすることで、この問題に正解できると考えました。
それを実装したコードが次のものになります。(後半に想定解の解説もあります）

回答例（クリックして開く）

n = int(input())

# 折り目の数は2**n - 1個なので答えを格納するリストを作成
ans = [-1] * (2**n - 1)


# lstには開いたとき折り目が何番目にあるかの数字を格納
def do(lst, is_flip):
    length = len(lst)
    # 中心の位置(折り目が付く位置)
    center = length // 2

    # is_flipがTrueなら表向き、Falseなら裏向き(逆が良かったかも)
    # 表向きなら、折ったら谷折り、裏なら山折りで答えのリストを更新
    if is_flip[center]:
        ans[lst[center]] = 0
    else:
        ans[lst[center]] = 1

    # これ以上折らない
    if length == 1:
        return

    # リストを前半、後半に分割
    before_lst = lst[:center]
    # 紙の右側は左右反転するため、リストを反転させる
    after_lst = lst[center + 1 :][::-1]
    before_is_flip = is_flip[:center]
    # after_is_flipの中身はすべて同じなため、左右反転してもしなくてもよい
    after_is_flip = is_flip[center + 1 :][::-1]

    # 裏返すからTrueとFalseを反転
    for i in range(len(after_is_flip)):
        after_is_flip[i] = not after_is_flip[i]

    # 前半と後半それぞれさらに実行
    do(before_lst, before_is_flip)
    do(after_lst, after_is_flip)


# 最初は0 ~ (2**n - 1) - 1までが順番に並んでいる、すべて表向き
do([i for i in range(2**n - 1)], [True] * (2**n - 1))
# 答えがintが格納されたリストになっているので、strにしてからjoinする
print("".join(map(str, ans)))

また、想定解としては、まず答えのリストの真ん中を$0$（谷折り）にします。そして分けられた左側について考えます。
重要な考察として、折られた左側はかならず表向きであるため、元の紙を折る問題に帰着してもよいです。
さらに右側については左側と裏表が逆であるため、付く折り目の向きも逆になると考えられます。
また、折り目の番号を$0, 1, 2, ..., n - 1$ とすると、$(0, n - 1), (1, n - 2), ..., (n // 2 - 1, n // 2 + 1), n // 2$、 (// は切り捨て除算) という折り目のペアができ、左半分と右半分で折り目の付く場所は左右反転していることもわかります。
この事実は手元で紙を折って実験することでも観測することができます。

以上のことから、答えを空文字列から始め、$ans = (ansそのもの) + 0 + (ansを逆にしたものの、さらに0と1を逆にしたもの)$と更新していけばよいです。
それを実装したのが次のコードです。

回答例（クリックして開く）

n = int(input())
# 最初は空文字列
ans = ""

for _ in range(n):
    # 答えを更新していく
    # ans[::-1]でansの逆順、translateで文字を置き換える。maketransで置き換える文字を指定する。
    ans += "0" + ans[::-1].translate(str.maketrans("01", "10"))

print(ans)

非常に見やすくわかりやすいコードになりましたね。同じ問題でも様々な解き方があり、方針次第で簡単な問題にも、難しい問題にもなりえるのが競技プログラミングの面白いところだとつくづく思います。

3. 終わりに

ここまで記事を読んでいただきありがとうございます。すべての問題がわかった人も、わからなかった人もいると思います。

しかし、今回はキャンペーン問題ですから解説している人がたくさんいるはずです。

同じ問題に複数の解法があるように、同じ問題にも複数の解説の方法があります。

ぜひ自分に合う解説の人を見つけてみてください。

そして、わかった！の楽しさを味わってください。

競技プログラミング、そしてプログラミングがあなたの人生の中の楽しみや糧になることを心より祈って終わりとさせていただきます。

ここまで読んでいただきありがとうございました！！

追記
8/8、ハノイの塔の回答コードを更新(@shiracamus(しらかみゅ)さん、感謝です！）
8/9、ハノイの塔の解説及びコード内のコメントを修正。より問題文に即したものに、言葉の定義をはっきりとさせた。