[Python] ABC473 A~Fざっくり解説
(今回は解法が思いつきやすい方だった気がします。方針はすぐ立てられるものが殆どでしたが、何故か酒を煽っていたのでA~E完で頭が回らなくなって断念♡(後半になるほどWAで引っかかりまくって笑ってました) そんな人による解説です。参考になれば幸いです。)
A - Second Half Sum (問題)
配列長が偶数の整数列が与えられるので、後半部分の総和を求めるだけです。
N = int(input())
A = list(map(int, input().split()))
print(sum(A[N//2::]))B - Old Maid (問題)
高橋君が持っている任意の整数が書かれているカード枚のうち、
[1]書かれている数字の被っているカードがない
[2]書かれている数字の被っているカードが奇数枚ある
の2通りの場合で、書かれている整数の値を足し合わせるだけです。
バケットの問題として解く、もしくは検索がのsetを用意して、被りがあればsetから消す、なければ入れるを繰り返してsumを取れば解けます。
//setを使った解法
N = int(input())
A = list(map(int, input().split()))
pool = set()
for i in A:
if not i in pool:
pool.add(i)
else:
pool.discard(i)
print(sum(pool))//バケットとして解く
N = int(input())
A = list(map(int, input().split()))
bucket = [0 for _ in range(100)]
for i in A:
bucket[i-1] += 1
ans = 0
for i in range(100):
if bucket[i] % 2 != 0:
ans += i+1
print(ans)C - Change Schools (問題)
これもバケット問題として解いて間に合います。
(問題の性質がB問と似ているので苦戦することなく解けた人が多いのではと思います)
N, K = map(int, input().split())
bucket = [0 for _ in range(K)]
max_c = 0
for i in map(int, input().split()):
bucket[i-1] += 1
max_c = max(max_c, bucket[i-1])
ans = 0
for i in bucket:
if max_c <= i+1:
ans += 1
print(ans)D - Coefficient Stair (問題)
非負整数からなる長さの列がある。この数列の各インデックスと各要素を掛け合わせた総和がとなり得る数列の要素を辞書順で小さい方から出力する問題です。
辞書順で小さい方からという指定がされているので、数列のインデックスの小さいものから取り得る要素の最小値を0から決めつけて再帰を回していけば良いです。
※print(*A)と書くとTLEするので注意
def findA(i, k, A):
if i == N-1:
if(K-k) % N == 0:
A[i] = (K-k)//N
print(' '.join(str(a) for a in A))
return
for x in range(0, (K-k)//(i+1)+1):
A[i] = x
findA(i+1, k+x*(i+1), A)
N, K = map(int, input().split())
A = [0 for _ in range(N)]
findA(0, 0, A)E - K-Divisible Subarrays (問題)
個人的にこのような問題はパッと見何をすればいいか分からないことが多いのですが、なんとなくDPのような気がしました。
区切った配列の和がとなるように沢山区切ってその最大値を求める問題ですが、どのように丁度Kで割り切れる配列を作るのかで時間がかかりました。
まず配列の頭から累積和を取り、そのの値を記録します。そして同じの値を取るなら、その両端で区切った配列の総和は確かにKで割り切れます。
累積和のmodK配列はとなる
modK配列に含まれる要素のうち一番多い値(今回は0)で、区切る左の値が0、かつ0を1つ含むように配列を区切るときスコアが最大値になる。
つまり、のスコア3が最大値。
ただ配列の左側に、配列の右側にが多く存在する場合、途中で乗り換えて分割した方がスコアが高くなるのは自明。
これをコードに落とし込めばいいので、
[1] 累積和を取りながらmodK配列を作る
[2]配列におけるスコア最大値をとして、となるにおいて、modKがと等しくなる点を数えて仮スコアを出し、が最大値であればに更新する。
dpを行なっているときに毎回の最大値を求め直すのは無駄なので、キーをmodKの値としたmax_vで管理しています。
N, K = map(int, input().split())
k = []
sum = 0
for i in map(int, input().split()):
sum += i
k.append(sum % K)
dp = [0 for _ in range(N+1)]
max_v = {}
count = {}
count[0] = 1
max_v[0] = 0
for i in range(N):
b_j1 = count.get(k[i], 0)
if k[i] in max_v:
opt = max_v[k[i]] + b_j1
dp[i+1] = max(dp[i], opt)
else:
dp[i+1] = dp[i]
max_v[k[i]] = max(max_v.get(k[i], float('-inf')), dp[i+1] - b_j1)
count[k[i]] = b_j1 + 1
print(dp[N])Fも軽く解きたかったですが、無理そうです。
ではまたABC474で。
F - A/AB Insertion
遅延セグ木なんてまだ知らない人間が通りますよ。
調べてみるとなんと知っていればそこまで難しくない問題のようです。というか典型的な遅延セグ木の区間和の問題みたいですね。
遅延セグ木とは…
根に配列を持ち、末端の葉には配列の要素単体が格納されています。これを二分木の要領で葉から根の前までを順に足し合わせていくと根の配列になります。(ここまではセグ木)
末端の葉の要素に変更が生じた場合、本来であればすぐに上に伝えて更新し直す所を、更新する必要が出てくるまでこのような変更があったことだけを記録して後回しにする方法です。
セグ木が区間和、区間最大・最小値を求めるのに強いデータ構造で、更新があるため遅延セグ木という方法が最適になるようです。
そして遅延セグ木の実装にはかなり長いコードを書く必要があるわけですが、atCorder ライブラリの中に使っても大丈夫なチートコードがあるみたいです。
Pythonの遅延セグメントツリーのチートシート【AtCoder】 #Python3 - Qiita
ということで軽く考察。
まずA,ABで組み合わせて特定の文字列を作れるか否かを判定しなければならないですが、これはAを+1、Bを-1とした時にその総和が0以上である必要があります。これは文字を組み立てる途中にも適用されることなので、セグ木で組み立てていくときに出来上がるすべての文字列に対して0以上が成り立てばよいです。また文字列の左端がBの場合は省きます。
つまりセグ木でA,Bをそれぞれ1,-1として入れてその総和を管理、またその最小値も記録します。そして末端の葉が変更されたら一旦先延ばしにする遅延セグ木にすることで効率的に求めることが出来るという事です。
それで実装してみたのがこちら。
from atcoder.lazysegtree import LazySegTree
import sys
INF = 1 << 30
ID = None
def op(ele1, ele2):
sum1, min1 = ele1
sum2, min2 = ele2
return (sum1 + sum2, min(min1, sum1 + min2))
e = (0, INF)
def mapping(func, ele):
if func == ID:
return ele
if func == 1:
return (1, 1)
else:
return (-1, -1)
def composition(func_upper, func_lower):
if func_upper == ID:
return func_lower
else:
return func_upper
id_ = ID
input = sys.stdin.readline
N = int(input())
S = input()
s = []
for i in S:
if i == "A":
s.append((1, 1))
else:
s.append((-1, -1))
seg = LazySegTree(op, e, mapping, composition, id_, s)
Q = int(input())
for _ in range(Q):
q = input().split()
if int(q[0]) == 1:
idx = int(q[1]) - 1
char = q[2]
val = 1 if char == "A" else -1
seg.apply(idx, idx + 1, val)
elif int(q[0]) == 2:
l = int(q[1]) - 1
r = int(q[2])
total_sum, min_pref = seg.prod(l, r)
print("Yes" if total_sum >= 0 and min_pref >= 0 else "No")ただPythonでは、タプルで処理するのが時間がかかる?らしく(定数倍がそもそも大きい)これに工夫しないとTLEになってしまいます。正直どうしたらいいのか分からないですね…また解決したら書きます。
解決しました。普通に勘違いして謎の遅延セグ木を実装していました。
区間加算かつ区間最小値を取ってこれる遅延セグ木で解けばいいので、別にタプルを使わずに書けますね。
以下実装コードです。(pypyで出すとTLEしません、てか前のコードもpypyだったらTLEしないやんけ~~~泣 無駄に2通り作った人になりました。)
from atcoder.lazysegtree import LazySegTree
INF = 1 << 63
def op(ele1, ele2):
return min(ele1, ele2)
def mapping(func, ele):
return func + ele
def composition(func_upper, func_lower):
return func_upper + func_lower
e = INF
id_ = 0
# TODO (初期リストlst)
seg = LazySegTree(op, e, mapping, composition, id_, lst)
N = int(input())
S = input()
s = []
for i in S:
if i == "A":
s.append(1)
else:
s.append(-1)
Q = int(input())
for _ in range(Q):
q = list(input().split())
if q[0] == "1":
i = int(q[1]) - 1
if S[i] == q[2] : continue
if q[2] == "A":
seg.apply(i, N, 2)
else:
seg.apply(i, N, -2)
S[i] = q[2]
else:
l = int(q[1]) - 1
r = int(q[2])
m = 0
if l > 0 : m = ls.get(l-1)
print("No" if seg.prod(l, r) < m else "Yes)
一応いろんな人の回答を見漁って書いたのがこのコードなので、自分が書いたとは言いにくいのですが、こちらの方がシンプルにまとまっていて良いですね。最小値を区間で求めて、A,Bの置き換えを2の加算減算で実装するのは思いつかなかったので良い学びになりました。
ではまたABC474で。