Codeforces Round #785 (Div.2)

https://codeforces.com/contest/1673

Dashboard - Codeforces Round #785 (Div. 2) - Codeforces

기쁘다. 4솔이 잘 돼서 코포 의욕이 마구 생긴다!

다음 목표는 1시간 안에 4솔 가볍게 하기 + 남은 1시간 안에 2E 솔브.

 

A (00:04)

짝수면 알파벳의 합. 홀수면 한쪽 끝의 알파벳 한 개만 빼고 합 비교하기

28줄부터 보면 된다.

import sys, math
import heapq
 
 
 
from collections import deque
from bisect import bisect_left, bisect_right
 
input = sys.stdin.readline
 
hqp = heapq.heappop
hqs = heapq.heappush
 
 
# input
def ip(): return int(input())
def sp(): return str(input().rstrip())
 
 
def mip(): return map(int, input().split())
def msp(): return map(str, input().split().rstrip())
 
 
def lmip(): return list(map(int, input().split()))
def lmsp(): return list(map(str, input().split()))
 
 
############ Main! #############
 
for ttt in range(ip()):
    s = sp()
    if len(s) % 2 == 0:
        ans = 0
        for i in s:
            ans += ord(i) - ord('a') + 1
        print("Alice", ans)
    else:
        n = len(s)
        now = 0
        for i in range(1, n):
            now += ord(s[i]) - ord('a') + 1
        ans = now - (ord(s[0]) - ord('a') + 1)
        now = 0
        for i in range(n - 1):
            now += ord(s[i]) - ord('a') + 1
        ans = max(ans, now - (ord(s[n - 1]) - ord('a') + 1))
        if ans < 0:
            print("Bob", -ans)
        else:
            print("Alice", ans)
 
######## Praise greedev ########

 

B (00:14)

어떤 알파벳이 두번 이상 등장하지 않는 최대 길이의 문자열을 맨 왼쪽에서 찾으면 된다. 그리고 그 문자열이 반복되는 형태라면 YES.

28줄부터 보면 된다.

 

import sys, math
import heapq
 
 
 
from collections import deque
from bisect import bisect_left, bisect_right
 
input = sys.stdin.readline
 
hqp = heapq.heappop
hqs = heapq.heappush
 
 
# input
def ip(): return int(input())
def sp(): return str(input().rstrip())
 
 
def mip(): return map(int, input().split())
def msp(): return map(str, input().split().rstrip())
 
 
def lmip(): return list(map(int, input().split()))
def lmsp(): return list(map(str, input().split()))
 
 
############ Main! #############
 
def f(ch):
    return ord(ch) - ord('a')
 
for ttt in range(ip()):
    s = sp()
    c = [False for _ in range(26)]
    t = ""
    for i in range(len(s)):
        if c[f(s[i])]:
            break
        t += s[i]
        c[f(s[i])] = True
    fl = True
    for i in range(len(s)):
        if s[i] != t[i % len(t)]:
            fl = False
    print("YES" if fl else "NO")
 
######## Praise greedev ########

 

C (00:27)

모르면 안된다. 난 구현에서 실수해서 찾느라 5분은 걸린 것 같다

https://www.acmicpc.net/problem/2293

28줄부터 보면 된다.

import sys, math
import heapq
 
 
 
from collections import deque
from bisect import bisect_left, bisect_right
 
input = sys.stdin.readline
 
hqp = heapq.heappop
hqs = heapq.heappush
 
 
# input
def ip(): return int(input())
def sp(): return str(input().rstrip())
 
 
def mip(): return map(int, input().split())
def msp(): return map(str, input().split().rstrip())
 
 
def lmip(): return list(map(int, input().split()))
def lmsp(): return list(map(str, input().split()))
 
 
############ Main! #############
 
MOD = 10 ** 9 + 7
 
def isit(s):
    for i in range(len(s)):
        if s[i] != s[-i - 1]:
            return False
    return True
 
p = []
for i in range(1, 40001):
    if isit(str(i)):
        p.append(i)
 
dp = [0 for _ in range(40001)]
dp[0] = 1
for i in p:
    for j in range(i, 40001):
        dp[j] += dp[j - i]
        dp[j] %= MOD
 
for ttt in range(ip()):
    n = ip()
    print(dp[n] % MOD)
 
######## Praise greedev ########

 

D (01:36)

일단, 답이 0인 경우를 찾아보자.

수열 b, c의 공차를 각각 \(d_b, d_c\) 라고 하면,

\(d_c \mod d_b > 0\)인 경우

\((c_1 - b_1) \mod d_b > 0\)인 경우

\(c_n > b_n\) 또는 \(c_1 < b_1\)인 경우

 

이 경우들을 제외하면 적어도 하나의 답이 존재한다.

 

이제, 답이 무수히 많을 조건을 찾아보자.

\(c_{n + 1} = b_i\)를 만족하는 \(i\)가 수열 b의 최대 길이 y보다 클 때

\(c_0 = b_i\)를 만족하는 \(i\)가 1보다 작을 때

 

거의 다 왔다. 특이 케이스를 다 걸러냈으니, 이제 답의 개수를 세면 된다. 수열 a의 공차 \(d_a\)에 대해, \(lcm(d_a, d_b) = d_c\)를 만족하는 \(d_a\)를 찾으면 된다. 공차가 \(d_a\)일 때 가능한 수열 a의 개수는 \((d_c / d_a)^2\)가 된다.

 

\(lcm(d_a, d_b) = d_c\)이므로, \(d_a\)는 \(d_c\)의 약수여야 한다. \(d_c\)의 약수 중 하나를 \(k\)라고 할 때, \(d_a = k * d_c / d_b\)로 두고 풀면 된다.

 

37줄부터 보면 된다.

import sys, math
import heapq
 
 
 
from collections import deque
from bisect import bisect_left, bisect_right
 
input = sys.stdin.readline
 
hqp = heapq.heappop
hqs = heapq.heappush
 
 
# input
def ip(): return int(input())
def sp(): return str(input().rstrip())
 
 
def mip(): return map(int, input().split())
def msp(): return map(str, input().split().rstrip())
 
 
def lmip(): return list(map(int, input().split()))
def lmsp(): return list(map(str, input().split()))
 
 
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
 
 
def lcm(x, y):
    return x * y // gcd(x, y)
 
############ Main! #############
 
MOD = 10 ** 9 + 7
 
def b_n(x):
    return b + (x - 1) * d_b
 
def c_n(x):
    return c + (x - 1) * d_c
 
for ttt in range(ip()):
    b, d_b, y = mip()
    c, d_c, z = mip()
 
    if d_c % d_b or (c - b) % d_b or c_n(z) > b_n(y) or c < b:
        print(0)
        continue
 
    i = (c_n(z + 1) - b) // d_b + 1
    j = (c_n(0) - b) // d_b + 1
    if i > y or j < 1:
        print(-1)
        continue
    factor = []
    for i in range(1, round(d_c ** 0.5) + 1):
        if d_c % i == 0:
            factor.append(i)
 
    for i in range(len(factor)):
        if factor[i] * factor[i] == d_c:
            continue
        factor.append(d_c // factor[i])
    ans = 0
    for i in factor:
        if d_b % i == 0:
            d_a = d_c // d_b * i
            if lcm(d_a, d_b) != d_c:
                continue
            ans += ((d_c // d_a) ** 2) % MOD
            ans %= MOD
 
    print(ans % MOD)
 
 
######## Praise greedev ########

 

딥2 AB가 요즘들어 좋지 않은 문제들이 많았는데, 이번 라운드는 정말 좋은 문제가 나왔다.