第二回日本最強プログラマー学生選手権 D - Nowhere P【Python】

https://atcoder.jp/contests/jsc2021/tasks/jsc2021_d

AtCoder ProblemsでDifficulty: 743、Solve Probability: 35%でした。

解けませんでした。
ユーザー解説

blog.hamayanhamayan.com

がわかりやすかったです。
先頭が1~1-Pで次の数字を考えるとたしかにそれまでの和がPの倍数になるものが1つあるようです。

MOD = 10 ** 9 + 7

N, P = map(int, input().split())
ans = (P - 1) * pow((P - 2), (N - 1), MOD)
print(ans % MOD)

AtCoder Beginner Contest 149 D - Prediction and Restriction【Python】

https://atcoder.jp/contests/abc149/tasks/abc149_d

AtCoder ProblemsでDifficulty: 719、Solve Probability: 37%でした。

K回より前は単純に勝てる手を出し、 K回以降は現在勝てる手をK回前に出していなければその手を出し、K回前に出していた場合は残りの2つの手の内、K回後に勝てる方の手は使わないようにすると、最大の得点が得られると考え解くことができました。

下記はかなり冗長なコードとなっています。

N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = list(input())
h = []
ans = 0
for i in range(N):
    # 相手の手
    v = T[i]
    # K回以降は、現在勝てる手をK回前に出していなければその手を出し、
    # K回前に出していた場合は、K回後に勝てる方の手は使わない
    if i-K >= 0:
        # K回前に出した手
        pre_h = h[i-K]
        if v == 'r':
            if pre_h != 'p':
                ans += P
                h.append('p')
            else:
                if i+K < N:
                    next_v = T[i+K]
                    if next_v == 's':
                        h.append('s')
                    elif next_v == 'p':
                        h.append('r')
                    else:
                        h.append('s')
                # K回後のじゃんけんが行わなければ何でも良い
                else:
                    h.append('s')
        elif v == 's':
            if pre_h != 'r':
                ans += R
                h.append('r')
            else:
                if i+K < N:
                    next_v = T[i+K]
                    if next_v == 'r':
                        h.append('s')
                    elif next_v == 'p':
                        h.append('p')
                    else:
                        h.append('s')
                else:
                    h.append('s')
        elif v == 'p':
            if pre_h != 's':
                ans += S
                h.append('s')
            else:
                if i+K < N:
                    next_v = T[i+K]
                    if next_v == 'r':
                        h.append('r')
                    elif next_v == 's':
                        h.append('p')
                    else:
                        h.append('r')
                else:
                    h.append('r')
    # K回より前は単純に勝てる手を選ぶ
    else:
        if v == 'r':
            h.append('p')
            ans += P
        elif v == 's':
            h.append('r')
            ans += R
        elif v == 'p':
            h.append('s')
            ans += S
print(ans)

AtCoder Beginner Contest 215 D - Coprime 2【Python】

https://atcoder.jp/contests/abc215/tasks/abc215_d

AtCoder ProblemsでDifficulty: 736、Solve Probability: 35%でした。

正数列Aを素因数分解して各素因数を一つの集合に管理し、エラトステネスのふるいを少し変えて各素因数の倍数であるものをふるい落としていくようにしたところ解くことができました。
algo-method.com

algo-method.com

N, M = map(int, input().split())
A = list(map(int, input().split()))

res = set()
def prime_factorize(N):

    # √N まで試し割っていく
    for p in range(2, N):
        # p * p <= N の範囲でよい
        if p * p > N:
            break

        # N が p で割り切れないならばスキップ
        if N % p != 0:
            continue

        # N の素因数 p に対する指数を求める
        e = 0
        while N % p == 0:

            # N を p で割る
            N //= p

        # 答えに追加
        res.add(p)

    # 素数が最後に残ることがありうる
    if N != 1:
        res.add(N)

for i in range(N):
    prime_factorize(A[i])

def edit_Eratosthenes(N):
    # テーブル
    isprime = [True] * (N+1)

    # 0を予めふるい落としておく
    isprime[0] = False

    # ふるい　pはAの各素因数
    for p in sorted(list(res)):
        # すでにp の倍数であるものはスキップする
        if not isprime[p]:
            continue

        # p の倍数からラベルを剥奪
        q = p# * 2
        while q <= N:
            isprime[q] = False
            q += p

    return isprime

res2 = edit_Eratosthenes(10**5)

print(sum(res2[:M+1]))
for i in range(1, M + 1):
    if res2[i]:
        print(i)

ZONeエナジー プログラミングコンテスト “HELLO SPACE” D - 宇宙人からのメッセージ【Python】

https://atcoder.jp/contests/zone2021/tasks/zone2021_d

AtCoder ProblemsでDifficulty: 719、Solve Probability: 37%でした。

Rごとに文字列を分けるとすると反転させた回数（右に何個Rがあるか）が偶数か奇数か2つのリストに分けて、奇数であればリストの順番と各要素（文字列）の順番を逆にし、2つのリストを連結しました。
連続する2つの文字列を削除する操作についてはdequeを使い解くことができました。
解説を見たところ反転の操作についてもdequeを使い、反転状態のときは先頭に文字列を追加していき、最終的に反転状態のときは全体を反転するというとても簡潔な解法でした。

from collections import deque
S = input()

even = []
odd = []
cur_s = []
R_count = 0
for s in S:
    if s != 'R':
        cur_s.append(s)
    else:
        R_count += 1
        if R_count % 2 == 0:
            even.append(cur_s)
        else:
            odd.append(cur_s)
        cur_s = []

# 最終的に反転した回数が奇数の文字列のリストがodd,偶数の文字列のリストがeven
if R_count % 2 == 0:
    even, odd = odd, even

# Rに関する操作後の文字列を求める
new_odd = []
for sl in odd[::-1]:
    new_odd.append(''.join(sl[::-1]))
new_even = []
for sl in even:
    new_even.append(''.join(sl))

res = list(''.join(new_odd + new_even + cur_s))

# 同じ文字が2つ連続で並んでいたらその2文字を取り除く操作
# 一文字ずつ見ていき、片方のキューの右端ともう一方のキューの左端を比較して
# 同じであれば取り除き、異なれば片方のキューにもう一方のキューの左端を追加する
ans = deque()
res = deque(res)
ans.append('')
while len(res) > 0:
    if ans[-1] == res[0]:
        ans.pop()
        res.popleft()
    else:
        ans.append(res.popleft())
print(''.join(ans))

AtCoder Beginner Contest 169 D - Div Game【Python】

https://atcoder.jp/contests/abc169/tasks/abc169_d

AtCoder ProblemsでDifficulty: 732、Solve Probability: 34%でした。

素因数分解を行い各指数について答えを求めていきました。
1, 2, 3...の累積和[0, 1, 3, 6...]を求め二分探索で各指数が何回操作を行えるかを求めるというややこしいことをしてしまいましたが、
解説を見たところ、シンプルに各指数から1,2,3...を引けるまで引いていきその回数を答えに加算すれば良かったようです。

import bisect

# https://algo-method.com/descriptions/119
# 素因数分解
# 460 = 2^2 x 5 x 23 の場合
# 返り値は [(2, 2), (5, 1), (23, 1)]
def prime_factorize(N):
    # 答えを表す可変長配列
    res = []

    # √N まで試し割っていく
    for p in range(2, N):
        # p * p <= N の範囲でよい
        if p * p > N:
            break

        # N が p で割り切れないならばスキップ
        if N % p != 0:
            continue

        # N の素因数 p に対する指数を求める
        e = 0
        while N % p == 0:
            # 指数を 1 増やす
            e += 1

            # N を p で割る
            N //= p

        # 答えに追加
        res.append((p, e))

    # 素数が最後に残ることがありうる
    if N != 1:
        res.append((N, 1))

    return res

N = int(input())

a = [i for i in range(1, 50)]
sum_a = [0]
for i in range(1, 50):
    sum_a.append(sum_a[i-1] + a[i-1])

pf = prime_factorize(N)
ans = 0
for p, e in pf:
    ans += bisect.bisect_right(sum_a, e) - 1

print(ans)

AtCoder Beginner Contest 177 D - Friends【Python】

https://atcoder.jp/contests/abc177/tasks/abc177_d

AtCoder ProblemsでDifficulty: 732、Solve Probability: 34%でした。

Union-Findで友達同士であるものをグループとし、すべてのグループのメンバーの最大値が答えになりました。

from collections import defaultdict

class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
 
    def Find(self,x):
        stack=[]
        while self.parents[x]>=0:
            stack.append(x)
            x=self.parents[x]
        for y in stack:
            self.parents[y]=x
        return x
 
    def Union(self,x,y):
        x=self.Find(x)
        y=self.Find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
 
    def Size(self,x):
        return -self.parents[self.Find(x)]
 
    def Same(self,x,y):
        return self.Find(x)==self.Find(y)
 
    def Members(self,x):
        root = self.Find(x)
        return [i for i in range(self.n) if self.Find(i)==root]
 
    def Roots(self):
        return [i for i, x in enumerate(self.parents) if x<0]
 
    def Group_Count(self):
        return len(self.Roots())
 
    def All_Group_Members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.Find(member)].append(member)
        return group_members
 
    def __str__(self):
        return '\n'.join(f'{r}: {m}' for r, m in self.All_Group_Members().items())

N, M = map(int, input().split())
 
UF = UnionFind(N)

for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    UF.Union(A, B)

ans = 0
for v in UF.All_Group_Members().values():
    ans = max(ans, len(v))

print(ans)

AtCoder Beginner Contest 190 D - Staircase Sequences【Python】

https://atcoder.jp/contests/abc190/tasks/abc190_d

AtCoder ProblemsでDifficulty: 722、Solve Probability: 35%でした。

解けませんでした。
(A + B)(B - A + 1) = 2NをXY= 2NとしてXYが2Nの約数となることやXYの偶奇が異なるなどということに全く考えが及びませんでした。

# https://algo-method.com/descriptions/84
def calc_divisors(N):
    # 答えを表す集合
    res = []

    # 各整数 i が N の約数かどうかを調べる
    for i in range(1, N + 1):
        # √N で打ち切り
        if i * i > N:
            break
        
        # i が N の約数でない場合はスキップ
        if N % i != 0:
            continue

        # i は約数である
        res.append(i)

        # N ÷ i も約数である (重複に注意)
        if N // i != i:
            res.append(N // i)

    # 約数を小さい順に並び替えて出力
    res.sort()
    return res

N = int(input())

D = calc_divisors(2 * N)
ans = 0
for x in D:
    y = (2 * N) // x
    if (x - y) % 2 == 1:
        ans += 1
print(ans)