コンテンツにスキップ

全探索

タグ「全探索」の記事 7 件

ABC482 B - Blank Bingo

5×55 \times 5 のマス目があり、いくつかのマスに印が付いています(o が印あり、. が印なし)。縦・横・斜めのいずれか一列の 55 マスすべてに印が付いた状態(ビンゴ)にするために、追加で付ける印の個数の最小値を求める問題です。

ある一列でビンゴにするには、その列で印が付いていないマスすべてに印を付ける必要があり、それで十分です。なので、各列について . の個数を数え、その最小値が答えです。

調べる列は、横 55 本・縦 55 本・斜め 22 本の計 1212 本です。

Python
S = [input() for i in range(5)]
l = S.copy()
for i in range(5):
l.append("".join(S[j][i] for j in range(5)))
l.append("".join(S[j][j] for j in range(5)))
l.append("".join(S[j][4 - j] for j in range(5)))
print(min(i.count(".") for i in l))

l に 1212 本の列を文字列として集めています。横の列は SiS_i そのもの、縦の列は各行の ii 文字目をつなげたもの、斜めの列は (j,j)(j, j) と (j,4−j)(j, 4 - j) のマスをつなげたものです(0 始まり)。

ShareOJ Programming Contest vol.1 D - Integers and Operators

整数のカード A1,…,ANA_1, \dots, A_N と、+ か ^(XOR)が書かれた演算子のカード NN 枚があります。x=0x = 0 から始めて、整数と演算子のカードを 1 枚ずつ選んで xx を更新することを NN 回繰り返します。最後の xx としてありうる最大値と最小値を求める問題です。N≤8N \le 8 です。

N≤8N \le 8 と小さいので、カードの使い方をすべて試します。

ii 回目に使う整数のカードと演算子のカードを決めれば、手続きが 1 通りに決まります。つまり、整数のカードの並べ方と演算子のカードの並べ方の組をすべて試せばよいです。

ただし、そのままでは 8!×8!≈1.6×1098! \times 8! \approx 1.6 \times 10^9 通りになり、間に合いません。演算子のカードには + と ^ の 2 種類しかないので、並べ方を記号の列として見ると重複がたくさんあります。重複を除くと、+ が cc 枚なら (Nc)≤(84)=70\binom{N}{c} \le \binom{8}{4} = 70 通りです。全体では 8!×70≈2.8×1068! \times 70 \approx 2.8 \times 10^6 通りになり、1 通りあたり NN 回の計算で済みます。

Python
from itertools import permutations
N = int(input())
A = list(map(int, input().split()))
op = input().split()
l = []
for p in permutations(op):
l.append(p)
l = list(set(l))
ans0 = 10**18
ans1 = -(10**18)
for t in l:
for p in permutations(A):
x = 0
for i, c in zip(t, p):
if i == "+":
x += c
else:
x ^= c
ans0 = min(ans0, x)
ans1 = max(ans1, x)
print(ans1, ans0)

演算子の並べ方を set に入れて重複を除き、l にしています。ans1 が最大値、ans0 が最小値です。

ABC479 C - Bento Packing

NN 個のおかずがあり、ii 個目のおいしさは AiA_i、体積は BiB_i です。体積の合計が WW 以下になるようにおかずを選ぶとき、おいしさの合計の最大値を求める問題です。1 つも選ばなくてもかまいません(1≤N≤201 \le N \le 20、1≤W,Ai,Bi≤1091 \le W, A_i, B_i \le 10^9)。

N≤20N \le 20 と小さいので、おかずの選び方 2N2^N 通りをすべて調べられます。それぞれについて体積の合計とおいしさの合計を求め、体積の合計が WW 以下のもののうち、おいしさの合計の最大値が答えです。

選び方は、00 以上 2N2^N 未満の整数 ii で表します。ii を 2 進数で書いたとき下から jj 桁目が 11 なら jj 個目のおかずを選ぶ、と決めれば、ii を 00 から 2N−12^N - 1 まで動かすことですべての選び方を 1 回ずつ調べられます。計算量は O(2NN)O(2^N N) です。

WW や BiB_i が大きいので、体積を添字にするナップサック DP は使えません。

Python
N, W = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N)]
ans = 0
for i in range(1 << N):
a = 0
b = 0
for j in range(N):
if (i >> j) & 1:
a += AB[j][0]
b += AB[j][1]
if b <= W:
ans = max(ans, a)
print(ans)

(i >> j) & 1 で、ii の下から jj 桁目(0 始まり)が 11 かどうか、つまり jj 個目のおかずを選ぶかどうかを調べています。a がおいしさの合計、b が体積の合計です。i = 0 は何も選ばない場合にあたり、このとき a = 0 なので、ans の初期値 00 と同じです。

DOJ Beginner Contest 6 C - Dadas Is Short

NN 人が左から一列に並んでいて、ii 番目の人の身長は HiH_i です。ダダスは 11 番目の人です。

ダダスを含む連続した区間 [L,R][L, R] のうち、区間内でダダスの身長がほかの全員より真に高いものの個数を求める問題です。NN の総和は 3×1053 \times 10^5 以下です。

ダダスは 11 番目なので、区間は必ず L=1L = 1 です。数えるのは、H2,…,HRH_2, \dots, H_R がすべて H1H_1 より小さくなるような RR の個数です。

左から見ていき、Hi≥H1H_i \ge H_1 となる最初の ii を探します。条件を満たす RR は 1,2,…,i−11, 2, \dots, i - 1 の i−1i - 1 個です。そのような ii がなければ、R=1,…,NR = 1, \dots, N のすべてが条件を満たすので、答えは NN です。

Python
for _ in range(int(input())):
N = int(input())
H = list(map(int, input().split()))
for i in range(1, N):
if H[i] >= H[0]:
print(i)
break
else:
print(N)

コードは 0-indexed なので、H[i] >= H[0] となる最初の i がそのまま答えの i−1i - 1 にあたります。for 文の else は、break せずにループを終えたときに実行されます。

SamCoding Round 7 (Div. 2) D - Perfect Number

各桁の和が 1010 になる正の整数を「完全数」と呼びます(19,28,37,…19, 28, 37, \ldots)。小さい方から kk 番目の完全数を求める問題です(1≤k≤1051 \le k \le 10^5)。

完全数を小さい順にすべて列挙し、kk 番目を出力します。

m=r+1m = r + 1 桁の完全数は、1010 個の玉と rr 本の仕切りを一列に並べたものと対応させられます。仕切りで区切られた r+1r + 1 個の区間に入っている玉の個数を、上の桁から順に並べたものが各桁の数字です。

たとえば r=2r = 2 で、1212 マスの列のうち位置 3,73, 7(00 始まり)に仕切りを置くと、各区間の玉の個数は 3,3,43, 3, 4 なので 334334 を表します。

ただし、次の 2 つに注意します。

  • 最上位の桁は 11 以上: 位置 00 に仕切りを置かなければよいので、仕切りの位置は 1,…,9+r1, \ldots, 9 + r から選びます。
  • 各桁は 99 以下: 区間に玉が 1010 個入る並べ方は数字として不正なので除きます。

桁数が少ないほど小さいので、r=1,2,…r = 1, 2, \ldots の順に列挙します。桁数が同じなら、仕切りの位置を辞書順に並べたものが数の小さい順と一致します。仕切りの位置が前にあるほど、上の桁が小さくなるからです。

r+1r + 1 桁の完全数は (9+rr)−1\binom{9 + r}{r} - 1 個あり、1111 桁(r=10r = 10)までで 184745184745 個になります。10510^5 個を超えるので、r≤10r \le 10 まで列挙すれば十分です。

Python
from itertools import combinations
ans = []
for r in range(1, 11):
for c in combinations(range(1, 10 + r), r=r):
t = 0
l = []
for x in c:
l.append(x - t)
t = x + 1
l.append(10 + r - t)
if 10 in l:
continue
ans.append(int("".join(map(str, l))))
K = int(input())
print(ans[K - 1])

combinations で仕切りの位置 c を辞書順に列挙しています。t は直前の仕切りの次の位置で、x - t が仕切りの間にある玉の個数、つまりその桁の数字です。最後の区間は列の長さ 10 + r までの玉の個数です。

桁に 10 があるものを除き、残りを数にして ans に入れていきます。

ABC477 B - Standing Outliers

数直線上に NN 人がいて、人 ii は座標 XiX_i にいます。自分以外のどの人との距離も DD 以上である人の番号を、昇順にすべて出力する問題です(N≤100N \le 100)。

N≤100N \le 100 なので、各人 ii について他の全員との距離 ∣Xi−Xj∣|X_i - X_j| を調べれば O(N2)O(N^2) で間に合います。

ソートを使うと O(Nlog⁡N)O(N \log N) にもなります。座標を昇順に並べると、ある人に最も近い人は並びで両隣のどちらかです。なので、両隣との差がどちらも DD 以上かどうかだけ調べれば十分です。同じ座標の人がいる場合は差が 0<D0 < D になるので、そのまま正しく判定できます。

Python
N, D = map(int, input().split())
X = list(map(int, input().split()))
ans = [i + 1 for i in range(N) if all(abs(X[i] - X[j]) >= D for j in range(N) if i != j)]
print(len(ans))
print(*ans)

全員の組を調べる O(N2)O(N^2) の解法です。

Uiua
≡&p+1⊚&p/+.⍜⍆(⬚1×⊂1.≥⊣:⧈-)∩(⊜⋕⊸≠@ &sc)

∩(⊜⋕⊸≠@ &sc) で 2 行を読み、それぞれ空白区切りの数値の配列にします。

⍜⍆(…) は、XX をソートしてから中の処理をし、結果を元の順番に戻します。中の処理は次のとおりです。

  1. ⧈- で隣り合う座標の差を求めます。
  2. ⊣: で 1 行目の [N,D][N, D] から DD を取り出し、≥ で各差が DD 以上かどうかの 0/1 の列にします。この列の kk 番目は、ソート後の kk 番目と k+1k+1 番目の人の間が離れているかを表します。
  3. ⊂1. で、この列を複製して片方の先頭に 11 を付けます。⬚1× で、もう片方の末尾を 11 で埋めて掛け合わせます。これで各人について「左隣とも右隣とも DD 以上離れているか」が求まります。両端の人は、いない側の隣を 11(離れている)として扱っています。

あとは /+. で人数を数えて &p で出力し、⊚ で 1 になっている位置を取り出して +1 で 1 始まりの番号にし、≡&p で出力しています。番号は 1 行に 1 つずつ出力しますが、AtCoder のジャッジは空白と改行の違いを区別しないので、これで通ります。

ABC478 B - Topping

ii 番目のトッピングは価格 ii、嬉しさ WiW_i です。価格の総和が VV 以下になるように相異なる 3 種類を選ぶとき、嬉しさの総和の最大値を求める問題です(N≤100N \le 100)。

N≤100N \le 100 なので、3 つの組 i<j<ki < j < k を全部試しても (1003)≈1.6×105\binom{100}{3} \approx 1.6 \times 10^5 通りで間に合います。価格の総和 i+j+ki + j + k が VV 以下のものについて、嬉しさの総和の最大値を取ります。

コードでは添字を 00 始まりにしているので、価格の総和は i+j+k+3i + j + k + 3 になります。

Python
from itertools import combinations
N, V = map(int, input().split())
W = list(map(int, input().split()))
ans = 0
for i, j, k in combinations(range(N), r=3):
if i + j + k + 3 > V:
continue
ans = max(ans, W[i] + W[j] + W[k])
print(ans)
Uiua
/↥▽<⊙(+2∩(≡/+⧅<3)⇡):°⊟:∩(⊜⋕⊸≠@ &sc)

∩(⊜⋕⊸≠@ &sc) で 2 行を数値の配列として読み、°⊟ で 1 行目を NN と VV に分けます。⧅<3 で添字が増加する 3 つ組をすべて作り、≡/+ で各組の和を取ります。これを ∩ で添字 ⇡ NN と WW の両方に行い、添字の和(に 22 を足したもの)が VV 未満、つまり価格の総和が VV 以下の組だけを ▽ で残して、/↥ で最大値を取っています。