結果
| 問題 |
No.3202 Periodic Alternating Subsequence
|
| ユーザー |
 navel_tos
|
| 提出日時 | 2025-07-24 13:22:35 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 272 ms / 2,000 ms |
| コード長 | 17,240 bytes |
| コンパイル時間 | 292 ms |
| コンパイル使用メモリ | 82,072 KB |
| 実行使用メモリ | 78,548 KB |
| 最終ジャッジ日時 | 2025-07-24 13:22:42 |
| 合計ジャッジ時間 | 7,099 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 24 |
ソースコード
#yukicoder contest 473 第1回 生成AI作問コンテスト
'''
#A
S = input().split()
print(''.join(Si[0].upper() for Si in S))
#B
N = int(input())
names = [input().split() for _ in range(N)]
#この問題AtCoderで見たな･･･？ 名前を座標圧縮
S = []
for Si, Ti in names:
S.append(Si)
S.append(Ti)
back = None
S = [back := Si for Si in sorted(S) if back != Si]
import bisect
names = [(bisect.bisect_left(S, Si), bisect.bisect_left(S, Ti)) for Si, Ti in names]
n = len(S)
C = [0] * n
for Si, Ti in names:
C[Si] += 1
C[Ti] += 1
print('Yes' if all(C[Si] == 1 or C[Ti] == 1 for Si, Ti in names) else 'No')
#C
import bisect
N = int(input())
A = list(map(int, input().split()))
back = None
B = [back := Ai for Ai in sorted(A) if back != Ai]
C = [0] * ( n := len(B) )
for Ai in A:
C[ bisect.bisect_left(B, Ai) ] += 1
for _ in range( Q := int(input()) ):
Xi, Ki = map(int, input().split())
print('Yes' if 0 <= ( i := bisect.bisect_left(B, Xi) ) < n and
B[i] == Xi and C[i] >= Ki else 'No')
#D
#どうしよっかな SegTree使っていい？
#Segment Tree
class SegmentTree:
def __init__(self, N, identity_e, node_f):
self._N, self._size, self._e, self._f = N, 1 << N.bit_length(), identity_e, node_f
self._node = [self._e for _ in range(self._size << 1)]
def build(self, A):
assert len(A) == self._N, 'array too large'
for i, v in enumerate(A, start = self._size): self._node[i] = v
for i in range(self._size - 1, 0, -1):
self._node[i] = self._f( self._node[i << 1], self._node[i << 1 | 1] )
def update(self, i, v):
self._node[i := i + self._size] = v
while (i := i >> 1) != 0:
self._node[i] = self._f( self._node[i << 1], self._node[i << 1 | 1] )
def fold(self, Lt, Rt):
if not 0 <= Lt < Rt <= self._N: return self._e
Lt, Rt, vL, vR = Lt | self._size, Rt + self._size, self._e, self._e
while Lt < Rt:
if Lt & 1: vL = self._f( vL, self._node[Lt] ); Lt += 1
if Rt & 1: Rt -= 1; vR = self._f( self._node[Rt], vR )
Lt >>= 1; Rt >>= 1
return self._f( vL, vR )
ST = SegmentTree( Q := int(input()), 0, max )
Rt = 0
for _ in range(Q):
Ti, Xi = map(int, input().split())
match Ti:
case 1:
ST.update(Rt, Xi)
Rt += 1
case 2:
Lt = Rt - Xi
print(ST.fold(Lt, Rt))
#E
#複雑だな 鍵を持っていない状態を0としたいから･･･
#通路を0 鍵を1 ～ 9 扉を11 ～ 19 壁を20 に対応させればいいかな
H, W, M = map(int, input().split())
l = W.bit_length()
B = bytearray(H + 1 << l)
for i in range( len(B) ): B[i] = 20
for h in range(H):
for w, Shw in enumerate(input().rstrip()):
i = h << l | w
if Shw == '.': B[i] = 0
elif Shw == '#': B[i] = 20
elif Shw == 'S': B[i] = 0; st = i
elif Shw == 'G': B[i] = 0; gl = i
elif Shw in '123456789': B[i] = int(Shw)
elif Shw in 'abcdefghi': B[i] = 11 + ord(Shw) - ord('a')
else: assert False
#DP[i][f]: 現在値がi、鍵がfとなるような最短経路
m = M.bit_length()
DP = [10 ** 9] * (len(B) << m)
DP[st << m | 0] = 0
maskm = ~ ( - 1 << m )
Q, R = [], [st << m | 0]
dist = -1
while R:
Q, R = R, Q
dist += 1
while Q:
x = Q.pop()
if DP[x] < dist: continue
DP[x] = dist
i, f = x >> m, x & maskm
for t in -1, 1, 1 << l, -1 << l:
if B[j := i + t] == 20: continue
if B[j] == 0: g = f
elif 1 <= B[j] <= 9: g = B[j]
elif 11 <= B[j] <= 19:
if f != B[j] - 10: continue
else: g = f
if DP[j << m | g] > dist + 1:
DP[j << m | g] = dist + 1
R.append(j << m | g)
ans = min(DP[gl << m | f] for f in range(M + 1))
print(ans if ans != 10 ** 9 else -1)
#F
#UnionFind
class UnionFind:
def __init__(self, N: int): self._parent = [-1] * N
def find(self, Vi: int):
Pi = Vi #2個目のwhileは parent[Vi], Vi の順で並列代入すること
while self._parent[Pi] >= 0: Pi = self._parent[Pi]
while Pi != Vi: self._parent[Vi], Vi = Pi, self._parent[Vi]
return Pi
def unite(self, Ui: int, Vi: int):
if ( Ui := self.find(Ui) ) == ( Vi := self.find(Vi) ): return False
if self._parent[Ui] > self._parent[Vi]: Ui, Vi = Vi, Ui
self._parent[Ui] += self._parent[Vi]; self._parent[Vi] = Ui
return True
def same(self, Ui: int, Vi: int): return self.find(Ui) == self.find(Vi)
def size(self, Vi: int): return - self._parent[ self.find(Vi) ]
#入力受取
N, M = map(int, input().split())
edges = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]
Q = int(input())
B = [int(input()) - 1 for _ in range(Q)]
UF = UnionFind(N)
bloken = bytearray(M)
for Bi in B: bloken[Bi] = 1
for i, (Ui, Vi) in enumerate(edges):
if not bloken[i]: UF.unite(Ui, Vi)
del bloken
cnt = N * (N - 1) >> 1
for i in range(N):
if i == UF.find(i): cnt -= UF.size(i) * (UF.size(i) - 1) >> 1
ans = [0] * Q
ans[-1] = cnt
for i in range(Q - 1, -1, -1):
Ui, Vi = edges[Bi := B[i]]
if not UF.same(Ui, Vi):
sizeUi, sizeVi = UF.size(Ui), UF.size(Vi)
cnt -= sizeUi * sizeVi
UF.unite(Ui, Vi)
if i:
ans[i - 1] = cnt
print(*ans, sep = '\n')
#G
#最大流(Dinic法 stack DFS) 配列を完全一次元化
#Reference: https://atcoder.jp/contests/abc285/submissions/42876297
class maxflow:
\'''
燃やす埋める: S → A/B → G, S → Aを切るならS → Bも切る は A → B(inf)
最小流量制限: A → B(Lt ～ Rt)
A → B(Rt - Lt), St2 → B(Lt), A → Gl2(Lt) の辺を代わりに張る。
St2 → Gl2, St2 → Gl, St → Gl2, St → Gl の順に流し、St2, Gl2の辺がcap = 0ならOK
---
G[now]: (頂点nowに起始する辺番号)の二次元配列を回避し、定数倍高速化を目指します。
順辺の個数は self.M で取得できます。
\'''
def __init__(self, N: int, inf = '4 * 10 ** 18'):
#E[i << 1], E[i << 1 | 1]: i番目の順辺のnow, nxt
#C[i]: cap
#P[i]: post : 辺番号iの起始をnowとしたとき、nowの前の辺番号
# 二次元配列との対比: G[now] = [･･･, P[i], i ･･･]のように、iの前の辺がP[i]
#B[now]: base : 頂点nowのイテレート開始辺 len(G[now]) == 0の場合、B[now] = -1
self.N, self.M = N, 0
self.inf = max( 0, inf ) if type(inf) != str else 4 * 10 ** 18
self._E, self._C, self._P, self._B, self._A = [], [], [], [-1] * N, [-1] * N
self._D, self._F, self._L, self._Q = [N] * N, [0] * N, [0] * N, [0] * N
#最大流計算の主要部
def _calc(self, St, Gl, permissible_error, flow_limit):
#D[now]: D[St]からの最短距離
#F[now]: flow, L[now]: leak 頂点nowに流入したフロー・流出が確定したフロー
#queue, stack: 同一配列を参照 BFSではdequeの代用 DFSでは非再帰化に用いる
#A[now]: arrow : 頂点nowがちょうど今見ている辺番号 A[now] == -1はStopIteration
N, E, C, P, B, A = self.N, self._E, self._C, self._P, self._B, self._A
D, F, L, queue, stack = self._D, self._F, self._L, self._Q, self._Q
flow_limit = max( 0, flow_limit ) if type(flow_limit) != str else self.inf
pe, flow = max( 0, permissible_error ), 0
#Dual-Primal step
while flow_limit > flow:
#Phase 1. BFS
for now in range(N): D[now] = N #初期化
D[St], queue[ Rt := 0 ] = 0, St
for Lt, now in enumerate( queue ):
A[now], x = B[now], D[now] + 1 #BFS出現辺のみA[now]を初期化
if ( i := B[now] ) != -1: #出次数が0の場合はB[now] == -1となる
while i != -1:
if C[i] > pe and D[ nxt := E[i ^ 1] ] > x:
D[nxt], queue[ Rt := Rt + 1 ] = x, nxt
i = P[i]
if Lt == Rt or now == Gl: break
if D[Gl] == N: break #BFSで到達不可能
#Phase 2. St ← Gl方向にDFS
F[Gl], L[Gl], stack[ d := 0 ] = flow_limit - flow, 0, Gl
while True: #F, Lの初期化は入りがけに行う
if ( now := stack[d] ) == Gl and F[Gl] == L[Gl]: return flow + L[Gl]
if now == St or F[now] == L[now]:
#(St側) now → back (Gl側) に流量 F[now] := 届いた分全部 を流す
back, f = stack[ d := d - 1 ], F[now]
C[ i := A[back] ] += f; C[i ^ 1] -= f; L[back] += f; continue
#(St側) nxt → now → back (Gl側) と流したい 残容量のある逆辺を探す
x = D[now] - 1
while ( i := A[now] ) != -1:
#DFS成功時は辺番号を変えず潜る 失敗時と帰りがけに辺番号を上げる
if x == D[ nxt := E[i ^ 1] ] and ( r_cap := C[i ^ 1] ) > pe:
F[nxt], L[nxt] = min( F[now] - L[now], r_cap ), 0
stack[ d := d + 1 ] = nxt; break
else: A[now] = P[i]
else: #帰りがけの処理
assert A[now] == -1
if now == Gl: flow += L[now]; break #pop Glの代用
#(St側) now → back (Gl側) に流量 L[now] := now以降で流した量 を流す
back = stack[ d := d - 1 ]
C[ i := A[back] ] += ( f := L[now] )
C[i ^ 1] -= f; L[back] += f; A[back] = P[i]
return flow
#辺の追加・取得
def add_edge(self, From: int, To: int, cap):
assert From in range(self.N) and To in range(self.N) and 0 <= cap
self._P.append( i := len(self._E) ); self._E.append(From); self._C.append(cap)
self._P.append( j := len(self._E) ); self._E.append( To ); self._C.append( 0 )
self._B[From], self._P[i] = self._P[i], self._B[From]
self._B[ To ], self._P[j] = self._P[j], self._B[ To ]; self.M += 1
def get_edge(self, i: int): #i番目の順辺の now, nxt, cap(順辺), rev_cap(逆辺)
assert i in range( self.M )
return self._E[i << 1], self._E[i << 1 | 1], self._C[i << 1], self._C[i << 1 | 1]
#最大流を計算 許容誤差: 残余容量がper_error以下の辺は容量0とみなす
def calc(self, start: int, goal: int, permissible_error = 0, flow_limit = 'infinity'):
assert start in range(self.N) and goal in range(self.N) and start != goal
return self._calc(start, goal, permissible_error, flow_limit)
#辺容量がすべて整数の場合に限り、O(NMlogC)で解ける
def calc_int(self, start: int, goal: int, max_capacity: int = 'infinity'):
assert start in range(self.N) and goal in range(self.N) and start != goal
m = max_capacity if type(max_capacity) != str else int( self.inf )
ans, logm = 0, max( 0, round(m) ).bit_length()
for e in range( logm, -1, -1 ): ans += self.calc( start, goal, (1 << e) - 1 )
return ans
#入力受取
N = int(input())
P = list(map(int, input().split()))
M = int(input())
terms = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]
K = int(input())
combs = [None] * K
for k in range(K):
Ai, Bi, Si = map(int, input().split())
combs[k] = (Ai - 1, Bi - 1, Si)
#燃やす埋める問題に帰着したい
#St側を「採用」 Gl側を「あきらめる」にしよう
#単独事業: すべての利益を先に得ておくと、すべてを罰金で処理できる
#依存関係: St → A を諦めるなら St → B も諦める、はA → B(inf)
# なので Ui → Vi(inf) を張る
#シナジー: うまい辺の張り方が思いつかない･･･
# 利益を先に計上しておいて、Ai, Bi → シナジー頂点(inf) を張る？
MF = maxflow(N + K + 2)
ans = 0
St, Gl = N + K, N + K + 1
for i, Pi in enumerate(P):
if Pi >= 0:
ans += Pi
MF.add_edge(i, Gl, Pi)
else:
MF.add_edge(St, i, abs(Pi))
for Ui, Vi in terms:
MF.add_edge(Ui, Vi, MF.inf)
for k, (Ai, Bi, Si) in enumerate(combs, start = N):
ans += Si
MF.add_edge(k, Gl, Si)
MF.add_edge(Ai, k, MF.inf)
MF.add_edge(Bi, k, MF.inf)
print(ans - MF.calc_int(St, Gl))
'''
#H
#行列累乗 1行N列の行列は [ [1, 2, ...] ] と二重括弧に変換し、演算はすべて非破壊的
class matrix_pow:
def __init__(self, MOD = 998244353): self.MOD = MOD
def eye(self, N: int): #単位行列
return [ [1 if i == j else 0 for j in range(N)] for i in range(N) ]
def add(self, A, B): #行列の加算
if isinstance( A[0], int ): A = [ A ]
if isinstance( B[0], int ): B = [ B ]
assert len(A) == len(B) and len(A[0]) == len(B[0]), 'not same size'
G = [[] for _ in range( len(A) )]
for h in range( len(G) ):
G[h] = [0] * max( len(A[h]), len(B[h]) )
for w in range( len(A[h]) ): G[h][w] = A[h][w] % self.MOD
for w in range( len(B[h]) ): G[h][w] = (G[h][w] + B[h][w]) % self.MOD
return G
def mul(self, A, B): #行列の積算 H行X列 * X行W列 = H行W列
if isinstance( A[0], int ): A = [ A ]
if isinstance( B[0], int ): B = [ B ]
assert len(A[0]) == len(B), 'cannnot calcurate'
G = [[0] * max( len(Bi) for Bi in B ) for _ in range( len(A) )]
for h in range( len(G) ):
for w, n in enumerate( G[h] ):
for x in range( len(A[0]) ): n += A[h][x] * B[x][w] % self.MOD
G[h][w] = n % self.MOD #最後にまとめて除算
return G
def doubling_mul(self, A, t): #A ^ tを計算
if isinstance( A[0], int ): A = [ A ]
assert all( len(Ai) == len(A) for Ai in A ) and t >= 0, 'cannot calcurate'
N, M = len(A), self.MOD
G, B, C = self.eye(N), [Ai[:] for Ai in A], [[0] * N for _ in range(N)]
while True:
if t & 1: #if t & 1: G = self.mul(G, B)
for h in range(N):
for w in range(N):
C[h][w] = sum( G[h][x] * B[x][w] % M for x in range(N) ) % M
G, C = C, G
if (t := t >> 1) == 0: break
for h in range(N): #B = self.mul(B, B)
for w in range(N):
C[h][w] = sum( B[h][x] * B[x][w] % M for x in range(N) ) % M
B, C = C, B
return G
#入力受取
T = bytearray(int(Ti) for Ti in input().rstrip())
K = int(input())
MOD = 10 ** 9 + 7
def brute(T, K):
ans = 0
newT = T * K
n = len(newT)
for S in range(1 << n):
U = []
for i in range(n):
if S >> i & 1: U.append(newT[i])
if all(U[k] != U[k + 1] for k in range(len(U) - 1)):
ans += len(U) ** 2
return ans
#まずは愚直なDPを考える
#DP[i][s][f]: i文字目まで見て、最後に採用した文字がs、赤玉を入れた個数がf個の場合の数
def brute_2(T, K):
newT = T * K
n = len(newT)
DP = [[[0] * 3 for _ in range(2)] for _ in range(n + 1)]
DP[0][0][0] = DP[0][1][0] = 1
for i, Ti in enumerate(newT):
for s in range(2):
for f in range(3):
DP[i + 1][s][f] += DP[i][s][f]
if Ti == 0:
DP[i + 1][Ti][0] += DP[i][1][0]
DP[i + 1][Ti][1] += 2 * DP[i][1][0] + DP[i][1][1]
DP[i + 1][Ti][2] += DP[i][1][0] + DP[i][1][1] + DP[i][1][2]
else:
DP[i + 1][Ti][0] += DP[i][Ti ^ 1][0]
DP[i + 1][Ti][1] += 2 * DP[i][Ti ^ 1][0] + DP[i][Ti ^ 1][1]
DP[i + 1][Ti][2] += DP[i][Ti ^ 1][0] + DP[i][Ti ^ 1][1] + DP[i][Ti ^ 1][2]
for s in range(2):
for f in range(2):
DP[i + 1][s][f] %= MOD
return sum(DP[-1][s][2] for s in range(2)) % MOD
#合ってそう なので1周期あたりの遷移を構築する
def make_grid(T):
#DP[s][t]: s → t の遷移 mod 10 ** 9 + 7
#状態は f << 1 | Ti で表せば6状態になるはず
DP = []
for st in range(6):
dp = [[0] * 2 for _ in range(3)]
ndp = [[0] * 2 for _ in range(3)]
dp[st >> 1][st & 1] = 1
for Ti in T:
for f in range(3):
for s in range(2): ndp[f][s] = dp[f][s]
ndp[0][Ti] += dp[0][Ti ^ 1]
ndp[1][Ti] += dp[0][Ti ^ 1] * 2 + dp[1][Ti ^ 1]
ndp[2][Ti] += dp[0][Ti ^ 1] + dp[1][Ti ^ 1] + dp[2][Ti ^ 1]
ndp[0][Ti] %= MOD
ndp[1][Ti] %= MOD
ndp[2][Ti] %= MOD
dp, ndp = ndp, dp
DP.append([dp[gl >> 1][gl & 1] for gl in range(6)])
return DP
def solve(T, K):
MP = matrix_pow(MOD)
DP = make_grid(T)
DP = MP.doubling_mul(DP, K)
ans = [[1, 1, 0, 0, 0, 0]]
ans = MP.mul(ans, DP)[0]
return ( ans[2 << 1 | 0] + ans[2 << 1 | 1] ) % MOD
print(solve(T, K))