7
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

paiza×Qiita記事投稿キャンペーンに参加しました.
関連リポジトリは,以下になります.

ここでは,Rank A, B問題の解答と簡単な解説を公開します.
言語はPythonを選択しました.結果は以下のようになりました.

Rank A

お菓子の詰め合わせ

school_hiking.py
from itertools import combinations

N, X = map(int, input().split())
a = [int(input()) for _ in range(N)]

for r in range(N):
    b = [X - sum(c) for c in combinations(a, N - r) if X >= sum(c)]
    if b:
        print(min(b))
        break

itertoolscombinationsを利用します.
N - r種類のお菓子を購入した時の合計金額sum(c)を全パターン求めます.
合計金額sum(c)X以下の場合のみ,お菓子購入後のお釣りX - sum(c)を求めます.
お釣りの出る買い方があった場合,最小のお釣りを出力します.

購入するお菓子の種類をNから1つずつ減らしながら検証するのがポイントです.

じゃんけんの手の出し方

janken.py
N, M = map(int, input().split())
s = input()
a = [s.count(x) for x in "GCP"]

max_wins = 0
for p in range(N):        # パーの数
    c = (M - p * 5) // 2  # チョキの数
    g = N - p - c         # グーの数
    if g >= 0 and p * 5 + c * 2 == M:
        max_wins = max(max_wins, sum(map(min, [p, g, c], a)))

print(max_wins)

相手が出したグー,チョキ,パーの回数をカウントし,aに格納します.
そして,パーを0回出す場合からN回出す場合まで,結果を検討します.

パーの数pが決まると自動的にチョキの数cとグーの数gも決まります.
ただし,グーの数がマイナスになったり,指の合計本数がMにならない可能性があります.
グー,チョキ,パーの回数が適切な場合,相手に勝利した回数を求め,それを他の結果と比較することで,じゃんけんで勝つ回数の最大値max_winsが求められます.

パーで相手に勝つ回数は,min(自分が出したパーの回数, 相手が出したグーの回数)です.
グー,チョキで勝つ回数も同様に,相手が出したチョキとパーの回数の考慮が必要です.

ハノイの塔

hanoi.py
def h(n, a, b, c, move):  # ハノイの塔の再帰関数
    if n > 0:
        h(n - 1, a, c, b, move)
        move.append((a, b))  # 移動を記録
        h(n - 1, c, b, a, move)

n, t = map(int, input().split())
move = []  # 移動記録用のリスト
h(n, 0, 2, 1, move)

poles = [list(range(n, 0, -1)), [], []]
for a, b in move[:t]:  # 円盤をt回動かす
    poles[b].append(poles[a].pop())

for x in poles:
        print(*x or "-")

再帰関数を利用し,問題を解き終えるまでの全移動工程を記録します.
そして,円盤をt回動かし,その時の状態を出力します.

山折り谷折り

origami.py
v = []
for _ in range(int(input())):
    v += [0] + [1^i for i in v[::-1]]
print(*v, sep="")

紙を折る回数が1回増えると,既存の折り目に0逆順で反転した折り目が追加されます.
pythonでは,べき乗に**を使うことを思い出してください.
^は,XOR=排他的論理和を表し,1^0⇒11^1⇒0になります.
ちなみに,~は,ビット単位の補数を計算するため,~0⇒-1~1⇒-2になります.

本の整理

book_sort.py
input()  # 不要な入力を捨てる
x = [int(x) - 1 for x in input().split()]

count = 0
for i in range(len(x)):
    while x[i] != i:
        x[x[i]], x[i] = x[i], x[x[i]]
        count += 1
print(count)

問題文に忠実な入れ替え(ソート)を実装すると,テストでタイムアウトが発生します.
そのため,同じ出力(入れ替え回数)になる,より高速な入れ替え法を利用しています.

Rank B

名刺バインダー管理

name_card.py
n, m = map(int, input().split())
a, b = divmod(m - 1, 2 * n)
print(2 * n * a + 2 * n - b)

関数divmodは,割り算の商aと余りbを同時に取得できます.
a0,1,...の値を取り,b0~5のいずれかの値を取ります.

番号mの名刺は,a+1毎目のファイルのb+1番目に存在します.
番号mの名刺の裏側は,a+1毎目のファイルの2*n-b番目です.
番号mの名刺,その裏側の名刺の番号は,2*n*a + 2*n-bになります.

長テーブルのうなぎ屋

long_table.py
f = lambda: map(int, input().split())
n, m = f()

y = set()  # 客がいる座席の集合
for _ in range(m):
    a, b = f()
    c = {(b + i) % n for i in range(a)}
    if not y & c:  # 集合yとcに重複がない
        y |= c  # yにcを追加(yとcの和集合でyを更新)

print(len(y))

入力から複数の数字を取り出す処理が2箇所で登場するため,最初に関数fを定義します.
客がいる座席の集合y と 新規の客が座りたい座席の集合c の2つがあると考えます.
あとは,2つの集合の積集合を確認し,それが空なら2つの和集合をyに保存するだけです.

集合ycに重複がない = 集合ycの積集合が空です.
y |= cy = y | cで,ycの和集合でyを更新します.

みんなでしりとり

word_chain.py
N, K, M = map(int, input().split())
a = {input() for _ in range(K)}  # 単語集
b = set()  # 発言集
c = ""  # 直前の人の発言の最後の文字

y = list(range(1, N + 1))  # 参加者リスト
i = 0  # 手番
for _ in range(M):
    x = input()
    if x not in a or (c and x[0] != c) or x in b or x[-1] == "z":
        y.pop(i)
        c = ""
    else:
        i += 1
        c = x[-1]

    b.add(x)
    if i >= len(y):
        i = 0

print(len(y))
print(*y, sep="\n")

まず,単語集a,発言集b,最後の文字cを用意します.
そして,参加者リストyと手番iも用意します.

ループの中では,発言集bへの単語の追加,次の手番iの確認が共通処理になります.
4つのしりとりのルールはorで接続し,ルールに従っているか否かで分岐が発生します.
分岐内では,必要に応じてcyiを更新します.

最後に,参加者リストyの長さとその中身を出力します.

神経衰弱

concentration.py
f = lambda: list(map(int, input().split()))
H, W, N = f()
a = [f() for _ in range(H)]
f()  # 不要な入力を捨てる

b = [0] * N  # 各プレイヤーの所持トランプ枚数
i = 0  # 手番
while sum(b) < H * W:
    s, t, r, u = f()
    if a[s - 1][t - 1] == a[r - 1][u - 1]:
        b[i] += 2
    else:
        i = (i + 1) % N

print(*b, sep='\n')

入力から複数の数字を取り出す処理が4箇所で登場するため,最初に関数fを定義します.
4行目のf()は,不要な入力を最小文字数で捨てています.
ここでは,「与えられた回数ループする」ではなく,「プレイヤーが取ったカードの枚数が場に存在したカードの枚数と等しくなるまでループする」と考えるのが適切です.

ユーザーがめくった2枚のトランプを確認し,内容が同じであれば所持トランプを2増やし,内容が異なれば手番を次の人に移動します.
これを繰り返し,最後に各プレイヤーの所持トランプ枚数を出力します.

3Dプリンタ

display_3d_printer.py
def get_row(x: int) -> str:
    row = list(input())
    for _ in range(x):
        for i, c in enumerate(input()):
            if c == "#":
                row[i] = "#"
    return "".join(row)

x, _, z = map(int, input().split())
rows = [get_row(x) for _ in range(z)]
print(*rows[::-1], sep="\n")

ネストが深くなるので,出力1行分を計算する処理を関数get_rowとして切り分けます.
まず,入力に合わせてz=1のケースから順番に,関数get_rowでデータを処理します.
そして,処理したデータを逆順で出力します.

関数get_rowでは,最初の入力行rowを基準として,新しい入力行と比較をします.
入力行のi番目に"#"があれば,row[i]"#"で更新します.
X行ごとに出現する区切り記号"--"も,他の入力行と同様に処理をします.
"--"は不要な入力ですが,特殊な処理も不要です.

終わりに

Rank A, Bは,考えさせられる問題が多く,難しかったです.
プログラム実装前に解法を複数検討する必要がある,そんな問題が多かった印象です.
問題の本質を理解して,コンパクトに解答できたと思います.

関連記事

7
1
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
7
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?