どうもこんにちは！
今週はAとCの2完でした。
B問題は全探索でよさそうと思ったものの点対称の判定がうまく作れず途中で諦めました。。
そのぶんD問題にかけたんですがTLEを解消できずでした。
振り返りとしてはあんまりなので、B問題は解説見て作ったコードを記載します。。
問題と公式の解説のリンク
問題は以下のリンクから。
A - 455 -
問題
与えられた3つの整数A,B,CがAとBは異なりかつBとCは同じかを判定する問題。
考え方とコード
if文使って判定しました。
a,b,c = map(int,input().split())
if a != b and b == c:
print("Yes")
else:
print("No")
B - Spiral Galaxy -
問題
H行W列のグリッドが与えられ、各マスは白か黒に塗られているとします。
このグリッド内の長方形領域でかつ点対称に塗られている個数を出力する問題。
考え方とコード
(h1,w1)から(h2,w2)までのマスが条件を満たすかを判定するときに、以下の条件を満たせばよいとなります。
- 1 <= h1 <= h2 <= H
- 1 <= w1 <= w2 <= W
- h1 <= i <= h2 かつ w1 <= j <= w2を満たすすべての整数i,jにおいて、マス(i,j)とマス(h1+h2-i,w1+w2-j)が同じ色
h,wの最大が10と大きくないので、これを全探索で実装すればOKです。
なお自分が解けなかった理由は条件を満たさないi,jが出てきたときにその(h1,h2,w1,w2)の組み合わせを無視しなければならないんですが、マスのif文判定でcontinueにしただけだったためです。我ながら残念な見落としでした。。
h,w = map(int,input().split())
g = [input() for _ in range(h)]
ans = 0
for h1 in range(h):
for h2 in range(h1+1,h+1):
for w1 in range(w):
for w2 in range(w1+1,w+1):
flag = True
for i in range(h1,h2):
for j in range(w1,w2):
if g[i][j] != g[h1+h2-i-1][w1+w2-j-1]:
flag = False
if flag:
ans += 1
print(ans)
C - Vanish -
問題
n個の要素の整数列と整数kが与えられます。任意の整数を1つ選んで、整数列の中からその整数を0に置き換えることをk回行うとしたとき、最終的な整数列Aの各要素の和の最小値を出力する問題。
考え方とコード
整数とリスト内のその整数の出現回数との積が大きい順にk個削除したときが、最終的な合計の最小値となります。
pythonではCounterを使ってリスト内の数字をkey、その出現回数をvalueとした辞書を作れるので、これを使ってkeyを数字とその出現回数の積が大きい順にソートしたリストを作り、先頭k個分のkeyを削除する数字とします。
あとは整数列を順番に見て削除しない整数を加算すれば答えとなります。
from collections import Counter
n,k = map(int,input().split())
a = [int(x) for x in input().split()]
#ある数字を消したときに合計値から引かれる値が大きい順にソート
d = Counter(a)
d_sort = sorted(d.items(),key=lambda x:x[0]*x[1],reverse=True)
#数字の種類がk個より小さい場合もケアが必要
v = set()
d_setl = len(set(d.keys()))
for i in range(min(k,d_setl)):
v.add(d_sort[i][0])
ans = 0
for i in range(n):
if a[i] not in v:
ans += a[i]
print(ans)
ではでは。