全探索入門問題
ABC106 B
ABC122 B
パ研杯2019 C - カラオケ
ABC106 B
制約
N ≤ 200（小さい）
方針（全探索できる！）
1〜N までの奇数について、正の約数の個数を求める
その個数が8個ちょうどならカウント
計算量は十分小さいので全探索でOK
Ruby
# frozen_string_literal: true
# 正の約数の個数を返す関数
def count_divisors(n)
count = 0
(1..n).each do |i|
count += 1 if n % i == 0# i が n の約数かどうかを判定
end
end
n = gets.to_i
ans = 0
(1..n).step(2) do |i| #奇数のみを走査（step(2)で2ずつ増加）
ans += 1 if count_divisors(i) == 8# 約数が8個ならカウント
end
Python
N = int(input())
ans = 0
def count_divisors(n):
count = 0
for i in range(1,n+1):
if n % i == 0:# i が n の約数ならカウント
count += 1
return count
for i in range(1,N+1,2):
if count_divisors(i) == 8:# 約数がちょうど8個ならカウント
ans += 1
print(ans)
ABC122 B
制約確認
S の長さ ≤ 10 -> 部分文字列の数は最大で 10C2 = 45 程度 -> 全探索OK
方針
S のすべての部分文字列を取り出す
その中で「すべての文字が A/C/G/T のいずれか」である文字列だけを対象とする
パ研杯2019 C - カラオケ
制約確認
N, M ともに最大 100
曲の組み合わせは M*(M-1)/2 通り（最大 4950 通り）
全探索でOK
全ての 2 曲の組み合わせ (j, k) を全探索（j < k）
各生徒について max(A[i][j], A[i][k]) を取る
生徒全員分の合計得点を求める
全体の中で最大のものを答えとして出力
計算量：O(M²×N) = 約 10⁴ 程度
Ruby
# frozen_string_literal: true
n,m = gets.split.map(&:to_i)
# 生徒ごとの点数行列（2次元配列）
a = Array.new(n){gets.split.map(&:to_i)}
max_score = 0
# すべての2曲の組み合わせを全探索
(0...m).each do |i|
(i+1...m).each do |j|
total_score = 0
(0...n).each do |k|
total_score += [a[k][i],a[k][j]].max # 各生徒の高得点を加算
end
max_score = [max_score, total_score].max
end
end
puts max_score
Python
N,M = map(int,input().split())
# 点数行列 A[i][j]：生徒 i が曲 j を歌ったときの点数
A = [list(map(int,input().split())) for _ in range(N)]
max_score = 0
# すべての2曲の組み合わせを全探索
for i in range(M):
for j in range(i+1,M):
total_score = 0
for k in range(N):# 各生徒ごとに
total_score += max(A[k][j],A[k][i]) # 高得点の方を加算
max_score = max(max_score, total_score) # 最大値を更新
print(max_score)