paiza×Qiita記事投稿キャンペーンに参加しました.
関連リポジトリは,以下になります.
ここでは,Rank A, B問題の解答と簡単な解説を公開します.
言語はPythonを選択しました.結果は以下のようになりました.
Rank A
お菓子の詰め合わせ
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
itertools
のcombinations
を利用します.
N - r
種類のお菓子を購入した時の合計金額sum(c)
を全パターン求めます.
合計金額sum(c)
がX
以下の場合のみ,お菓子購入後のお釣りX - sum(c)
を求めます.
お釣りの出る買い方があった場合,最小のお釣りを出力します.
購入するお菓子の種類をN
から1つずつ減らしながら検証するのがポイントです.
じゃんけんの手の出し方
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(自分が出したパーの回数, 相手が出したグーの回数)
です.
グー,チョキで勝つ回数も同様に,相手が出したチョキとパーの回数の考慮が必要です.
ハノイの塔
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
回動かし,その時の状態を出力します.
山折り谷折り
v = []
for _ in range(int(input())):
v += [0] + [1^i for i in v[::-1]]
print(*v, sep="")
紙を折る回数が1回増えると,既存の折り目に0
と逆順で反転した折り目
が追加されます.
pythonでは,べき乗に**
を使うことを思い出してください.
^
は,XOR=排他的論理和を表し,1^0⇒1
,1^1⇒0
になります.
ちなみに,~
は,ビット単位の補数を計算するため,~0⇒-1
,~1⇒-2
になります.
本の整理
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
名刺バインダー管理
n, m = map(int, input().split())
a, b = divmod(m - 1, 2 * n)
print(2 * n * a + 2 * n - b)
関数divmod
は,割り算の商a
と余りb
を同時に取得できます.
a
は0,1,...
の値を取り,b
は0~5
のいずれかの値を取ります.
番号m
の名刺は,a+1
毎目のファイルのb+1
番目に存在します.
番号m
の名刺の裏側は,a+1
毎目のファイルの2*n-b
番目です.
番号m
の名刺,その裏側の名刺の番号は,2*n*a + 2*n-b
になります.
長テーブルのうなぎ屋
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
に保存するだけです.
集合y
とc
に重複がない = 集合y
とc
の積集合が空です.
y |= c
= y = y | c
で,y
とc
の和集合でy
を更新します.
みんなでしりとり
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
で接続し,ルールに従っているか否かで分岐が発生します.
分岐内では,必要に応じてc
,y
,i
を更新します.
最後に,参加者リストy
の長さとその中身を出力します.
神経衰弱
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プリンタ
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は,考えさせられる問題が多く,難しかったです.
プログラム実装前に解法を複数検討する必要がある,そんな問題が多かった印象です.
問題の本質を理解して,コンパクトに解答できたと思います.
関連記事