ABC190 C - Bowls and Dishes
タイプ
- 全探索（bit全探索）
- ライブラリ
- set()
解説
工夫して解く全探索問題。
問題文が少し理解しにくいと思うが、いってしまえばこうだ。
「C, Dのどちらかを選んで組み合わせた4つの数が、各A, Bの条件にどれだけ当てはまるか」ということだ。
これでもわかりにくいと思うので、サンプル入力を参考にして解説していく。
4 4
1 2
1 3
2 4
3 4
4
3 4
1 2
2 4
2 4
入力の部分の解説は省く。
問題はfor balls in product(*choice)からである。
まず、*はかんたんにいうと、大枠の括弧を外す操作である。
例えば、このときのchoiceは、[(3, 4), (1, 2), (2, 4), (2, 4)]である。つまり、*choiceは、(3, 4) (1, 2) (2, 4) (2, 4)となる。
次に、product()。これは事前にfrom itertools import productしなければならない。この操作をすると全組み合わせを試すことができる。
例えば、product(*choice)と書くと、各タプルのインデックス0の値を持ってくるので、(3, 1, 2, 2)となる。このように(3, 1, 2, 4)、(3, 1, 4, 2)、(3, 1, 4, 4)...と後ろから一つずつ値を変えていく。
これらをballsに入れていくわけだが、次の操作としてset()で重複をなくしておく。
そして、condにいれたAとBのそれぞれの値がset(balls)のなかにあるかを確認する。このときAとBどちらの値もset(balls)に存在して、初めて条件を満たす。つまり、コードではA in balls and B in ballsと書ける。条件を満たした数だけsum()して、cntに代入。これをループで回していくので、条件を満たしている数が多いものを随時更新するために、if ans < cnt:が必要である。
回答例
# 全探索
from itertools import product
N, M = map(int, input().split())
cond = []
choice = []
# 皿A, 皿B
for _ in range(M):
A, B = map(int, input().split())
cond.append((A, B))
# K人
K = int(input())
# 皿C, 皿D
for _ in range(K):
C, D = map(int, input().split())
choice.append((C, D))
ans = 0
# *choice -> ( , ) ( , ) ( , ) ( , )
# 各タプルからどちらかをとりだしballsに代入
for balls in product(*choice):
# set()で重複を削除
balls = set(balls)
# set(balls)の中で、A,B両方の値が存在したら条件を満たしているので、1カウント
cnt = sum(A in balls and B in balls for A, B in cond)
# 条件を満たしているものが、多いものをansに更新
if ans < cnt:
ans = cnt
print(ans)
ABC191 C - Digital Graffiti
タイプ
- 全探索
- 二次元配列
解説
問題を見てもらった方は分かる通り、「サンプル数少なすぎ問題」。
少し例を出すと、
.....
.###.
.###.
.###.
.....
これは四角形。
.....
.###.
.###.
.##..
.....
右下が欠けたこれは、六角形。
「ん？六角形？」と思うかもしれないが、みなさんが想像している蜂の巣のような六角形ではない。「角が６つあるもの」を今回は六角形とよんでいる。「じゃあ、#にも角があるじゃないか」というと元も子もないが。
そんなわけで、こういう定義で話を進めていく。
これを求めるには全探索して角を求めることが必要である。ここで角の条件とは、2×2を縦横シフトさせ、4ブロック中 1 or 3 ブロックがあれば、角となります。
4ブロック中1ブロックが角とはなにか。
たとえば、最初のサンプルでいえば次のようになる。
# 2×2
..
.#
# 右下'#'の左上が角
2番目のサンプルでいえば次のようになる。
# 2×2
##
#.
# 右上'#'の右下が角
このように2×2のブロックでシフトさせていき、角の数を数える。
まず、tableに高さHだけ文字列（ . or # ）を追加。
これを行と列についてforループ。2×2のブロックを二次元配列で調査し、'#'の数に応じて、先程述べたようにansに1を加える。
回答例
# 全探索
H, W = map(int, input().split())
table = []
for _ in range(H):
S = input()
table.append(S)
ans = 0
for row in range(H-1):
for col in range(W-1):
A = [''] * 4
A[0] = table[row][col]
A[1] = table[row+1][col]
A[2] = table[row][col+1]
A[3] = table[row+1][col+1]
if A.count('#') == 1 or A.count('#') == 3:
ans += 1
print(ans)
ABC192 C - Kaprekar Number
タイプ
- 関数（def( )）
解説
問題文のとおりにやれば解ける問題。
注意点は、int(''.join(sorted(s)))。文字列をソートすると勝手に昇順に並び替えてくれる。
これをansにいれて、K回ループを回せばよい。
回答例
# 関数
def func(x):
s = str(x)
g1 = int(''.join(sorted(s, reverse=True)))
g2 = int(''.join(sorted(s)))
return g1 - g2
N, K = map(int, input().split())
ans = N
for _ in range(K):
ans = func(ans)
print(ans)
ABC193 C - Unexpressed
タイプ
- 全探索（細工あり）
- set()
解説
1以上N以下の整数のうち、2以上の整数a, bを用いて$a^b$とあらわせないものはいくつあるか。
あらわせないものが、あらわせるものよりも圧倒的に多いので、Nからあらわせるものを引いた値を出力すれば良い。
また、全探索する数はNの1/2乗に書き換える。なぜなら、bが2以上で結局forで2乗するので、それ以上の探索が必要ないからである。
forでaを+1ずつ回し、whileで毎回aかけてあげることで、$a^b$が実装される。
set()を使っているのは、値が重複しないようにするためである。今回探したいのは、1以上N以下の整数なので、追加する値は重複してはならない。つまり、set()で管理している。
回答例
N = int(input())
sq = int(10**5)
S = set()
for a in range(2, sq + 1):
cur = a ** 2
while cur <= N:
S.add(cur)
cur *= a
print(N - len(S))
ABC194 C - Squared Error
タイプ
- 制約を活用
from collections import Counter
解説
そのまま計算すると、$O(N^2)$でTLEになる。
この数列の特徴は、「2乗しているので結果が変わらない」ということである。
したがって、各数字が何回でるかをカウントしてあげるだけでいい。
制約は、$|A_i|<=200$より、-200~200の401種類。
Counter(A)でどの数がどのくらいあるのかを辞書型で保存する。これをcntに代入して、組み合わせたい数字xとyを、cnt[x]とcnt[y]でどのくらいの数があるか探す。
(x - y)**2で同じ数がでるので、これが何通りずつあるかを数え上げて、totalにいれる。
これをx <= y <= 200となるように、forループを回す。
回答例
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
cnt = Counter(A)
ans = 0
for x in range(-200, 200+1):
for y in range(x+1, 200+1):
xcnt = cnt[x]
ycnt = cnt[y]
total = xcnt * ycnt * (x - y) ** 2
ans += total
print(ans)
編集後記
これから190番台から下ってC問題の解説記事を出していきますので、お見逃しなく.
＜参考文献＞
- https://qiita.com/u2dayo
- https://atcoder.jp/home