見出し画像

【ABC346】緑コーダーの競プロ参加記録 #8.5

igasu_7

その日のうちに記事を投稿することに挑戦してみます。
今回は解説というより感想です。

AtCoder Beginner Contest 346。使用言語はPythonです。


A問題 - Adjacent Product

コンテスト中の提出
https://atcoder.jp/contests/abc346/submissions/51546007

問題文にそのまま従いました。

""""""
N = int(input())
A = list(map(int, input().split()))
B = []
for i in range(N - 1):
    B.append(A[i] * A[i + 1])
print(*B)


B問題 - Piano

コンテスト中の提出
https://atcoder.jp/contests/abc346/submissions/51551602

むずかしいです。
よく分からないので、'wbwbwwbwbwbw' を適当に100個くらい連結して、長さ$${W + B}$$の区間を全探索しました。

公式解説を読んではじめて mod の発想に気付く。

""""""
from collections import Counter
W, B = map(int, input().split())
S = 'wbwbwwbwbwbw' * 100
N = len(S)
ans = 'No'
for i in range(N - (W + B)):
    t = S[i : i + (W + B)]
    cnt = Counter(t)
    if cnt['w'] == W and cnt['b'] == B:
        ans = 'Yes'
        break
print(ans)

C問題 - Σ

コンテスト中の提出
https://atcoder.jp/contests/abc346/submissions/51555790

「$${A}$$の中に一度も現れない数」を全探索するのは$${O(K)}$$となり 2 sec に間に合いません。

「$${1}$$から$${K}$$までの総和」を求める公式があり$${O(1)}$$で求められるので、「$${A}$$に含まれる整数」を引けばいいのかなという流れ。

""""""
N, K = map(int, input().split())
A = set(map(int, input().split()))
ans = K * (K + 1) // 2
ans -= sum(a for a in A if a <= K)
print(ans)


D問題 - Gomamayo Sequence

コンテスト中の提出
https://atcoder.jp/contests/abc346/submissions/51571298

「良い文字列」の条件は「$${i}$$文字目と$${i + 1}$$文字目が一致するようなものがちょうど$${1}$$つ存在する。」とのことなので、これを全探索するのかなというところからスタート。

そうすると、$${S_iS_{i+1}}$$を '00' にするのか '11' にするのかで2パターン考えられます。
また '1' と '0' を交互に並べるとき、端っこの1文字が決まれば文字列は一意に決まります。

よって、$${S_i}$$を含む左側と、$${S_{i+1}}$$を含む右側それぞれについて「1' と '0' が交互に並ぶ文字列」にするためのコストが分かればよさそう。

「隣り合う文字が異なる」ことと「$${S_i}$$の文字を変えるときにコスト$${C_i}$$がかかる」ことを考えてDPの遷移とします。

""""""
N = int(input())
S = "#" + input()
C = [0] + list(map(int, input().split()))

L = [[0] * 2 for _ in range(N + 2)]
R = [[0] * 2 for _ in range(N + 2)]
for i in range(1, N + 1):
    if S[i] == '0':
        L[i][0] = L[i - 1][1]
        L[i][1] = L[i - 1][0] + C[i]
    else:
        L[i][0] = L[i - 1][1] + C[i]
        L[i][1] = L[i - 1][0]
for i in reversed(range(1, N + 1)):
    if S[i] == '0':
        R[i][0] = R[i + 1][1]
        R[i][1] = R[i + 1][0] + C[i]
    else:
        R[i][0] = R[i + 1][1] + C[i]
        R[i][1] = R[i + 1][0]
ans = 1 << 60
for i in range(1, N):
    ans = min(ans, L[i][0] + R[i + 1][0])
    ans = min(ans, L[i][1] + R[i + 1][1])
print(ans)


E問題 - Paint

コンテスト中の提出
https://atcoder.jp/contests/abc346/submissions/51590178

ふつうにやると、上書きされる色の管理が大変。

発想を逆転して、操作を後ろの方から進めていくとします。
そうすると「上書き」ではなく「塗られてないマスのみを塗る」という挙動になります。

つまり、これまでに塗られた列の数を$${c}$$とすると、ある行を塗るときその色の個数は$${W - c}$$個増えます。列を塗るときも同様です。

はじめ全てのマスが色$${0}$$で塗られているのが地味にめんどくさいですね。

"""
逆から見ていく
"""
H, W, M = map(int, input().split())
Query = [tuple(map(int, input().split())) for _ in range(M)]
r, c = 0, 0
p = 2 * (10 ** 5)
Color = [0] * (p + 1)
used_R = [0] * (p + 1)
used_C = [0] * (p + 1)
other = H * W
for i in reversed(range(M)):
    t, a, x = Query[i]
    if t == 1:
        if not used_R[a]:
            used_R[a] = True
            r += 1
            Color[x] += W - c
            other -= W - c
    else:
        if not used_C[a]:
            used_C[a] = True
            c += 1
            Color[x] += H - r
            other -= H - r
Color[0] += other
ans = []
for i in range(p + 1):
    if Color[i] == 0:
        continue
    ans.append((i, Color[i]))
print(len(ans))
for a in ans:
    print(*a)


F問題 - SSttrriinngg in StringString

upsolve
https://atcoder.jp/contests/abc346/submissions/51639021

解けなかったけど方針は合ってた！　嬉しいような悔しいような。

from string import ascii_lowercase
from bisect import bisect_right
def invalid(S, T):
    ss = set(S)
    tt = set(T)
    for c in ascii_lowercase:
        if not c in ss and c in tt:
            return True
    return False

def solve(x):
    cnt = 1
    curr = -1
    for t in T:
        """ 現在位置 curr 以降にある最初の文字 c は何個目？ """
        c = ord(t) - ord('a')
        j = bisect_right(A[c], curr)
        
        """ x 個の文字 c を使うために文字列 S をいくつ追加する？ """
        k = len(A[c])
        p = min(x, k - j)       #  文字列 S を追加せずに使える分
        q = max(0, x - p) // k  #  文字列 S を追加する個数
        r = max(0, x - p) % k   #  まだ足りない分
        if j + p + r - 1 >= k:
            q += 1
        j = (j + p + r - 1) % k
        
        """ パラメータの更新 """
        cnt += q
        curr = A[c][j]
        if cnt > N:
            return False
    return cnt <= N

N = int(input())
S = input()
T = input()

if invalid(S, T):
    print(0)
    exit()

A = [[] for _ in range(26)]
for i, s in enumerate(S):
    c = ord(s) - ord('a')
    A[c].append(i)

ok, ng = 0, 1 << 60
while ng - ok > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok)

あとがき

その日のうちに記事を作るのは、たいへん！
従来の記事はたぶん後日あがります。あがらないかもしれません。

普段はこれよりボリュームのある解説記事を書いています。
こちらもよろしくお願いします。


いいなと思ったら応援しよう！