188AC - ABC048C: Boxes and Candies

競プロ
ABC048-C (300 points)
問題

それぞれ a_i 個のキャンディが入った箱が N 個並んでいる.
箱に入っているキャンディを食べて, どの隣り合う箱を見ても, それらの箱に入っているキャンディの個数の和が x 以下になるようにするとき, 食べなければならない最小個数を求める.

  • 2 \leq N \leq 10^5
  • 0 \leq a_i \leq 10^9
  • 0 \leq x \leq 10^9
方針

素直に端から順番に条件を満たすように食べていきましょう. 

# input

N, x = map(int, input().split())
a = list(map(int, input().split()))

ans = 0
for i in range(N - 1):
    if a[i] > x:
        ans += a[i] - x
        a[i] = x
    if a[i] + a[i + 1] > x:
        ans += a[i] + a[i + 1] - x
        a[i + 1] -= a[i] + a[i + 1] - x

print(ans)

183AC - ABC106D: AtCoder Express 2

競プロ 累積和
ABC106-D (400 points)
問題

東西に伸びる 1 本の線路沿いに西から順に 1, 2, \ldots, N の N 個の都市が並んでいる.
M 本の列車がそれぞれ都市 L_i と R_i の区間を走っているとき, Q 個の区間 [ \ p_i, \ q_i \ ] , i \in \{ \ 1, 2, \ldots, Q \ \} に完全に含まれる列車の本数をそれぞれ求める.

  • 1 \leq N \leq 500
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq L_i \leq R_i \leq N
  • 1 \leq p_i \leq q_i \leq N
方針
  • 以下の記事に完全にお世話になりました.

http://hama-du-competitive.hatenablog.com/entry/2017/04/22/185540

  • 想定解は二次元累積和. 
# input
N, M, Q = map(int, input().split())
train_query = {} # 対象区間とクエリを一緒にソート
for i in range(M + Q):
    train_query[i] = list(map(int, input().split()))

train_query = sorted(train_query.items(), key=lambda x: x[1][1])
print(train_query)
# 辞書をソートするとリストが返ってくることに注意

StartPoints = [0 for _ in range(N)] # 対象区間の開始位置
ans = [0 for _ in range(Q)] # 各クエリに対する答え

for j in range(M + Q):
    if train_query[j][0] < M: # 対象区間
        StartPoints[train_query[j][1][0] - 1] += 1
    else: # クエリ
        ans[train_query[j][0] - M] = sum(StartPoints[(train_query[j][1][0] - 1):(train_query[j][1][1])])

for i in range(Q):
    print(ans[i])

182AC - ABC106C: To Infinity

競プロ
ABC106-C (300 points)
問題

'1' ~ '9' の数字からなる文字列 S が以下のように変化するとき, 5000 兆日後の文字列の左から K 番目の数を求める.

  • 1 日たつと, 文字列 S の '2' は '22', '3' は '333', \ldots, '9' は '999999999' に置き換わる.
  • 1 \leq |S| \leq 100
  • 1 \leq K \leq 10^{18}
  • 5000 兆日後の文字列の長さは K 以上.
方針
  • 5000 兆日後には '1' 以外の数字は 実質的に無限個並んでいる.
  • S の最初の K 文字の中に, '1' 以外の数字が含まれていれば, そのような数字の中で最初に出てくる数字
  • そうでなければ '1'
# input
S = input()
K = int(input())

for i in range(K):
    if int(S[i]) != 1:
        print(int(S[i]))
        exit()
    elif i == K - 1:
        print(int(S[i]))

177AC - ABC050C: Lining Up

競プロ 10^9+7
ABC050-C (300 points)
問題

以下の条件を満たす N 人の並び方の総数を 10^9 + 7 で割った余りを出力する.

  • 人 i の右側に並んでいる人数と左側に並んでいる人数の差の絶対値は A_i.
  • 1 \leq N \leq 10^5
  • 0 \leq A_i \leq N - 1
方針
  • 人 i の左に並んでいる人数を k とすると, 右に並んでいる人数は k \pm A_i となり, 全員で N 人であることから

\ \ \ \ k = \frac{N \pm A_i - 1}{2}

  • 条件を満たす並び方がゼロになる場合：
  • N と偶奇が同じ A_i が存在（このとき k が整数にならない）.
  • A_1, A_2, \ldots, A_N に 同じ数が 3 つ以上含まれる（ k は 2 通り）.
  • N が奇数のとき, A_1, A_2, \ldots, A_N に 0 が 2 つ以上含まれる.
  • これら以外の場合, A_i = A_j となる 2 人 i, j は左右を入れ替えることが可能なので, 並び方の総数は 2 ^ {\lfloor N / 2 \rfloor} 通り. 
# input
N = int(input())
A = list(map(int, input().split()))

cnt = [0 for i in range(N)]
ans = 1

if N % 2 == 0:
    for i in range(N):
        if A[i] % 2 == 0:
            print(0)
            exit()
        cnt[A[i]] += 1
        if cnt[A[i]] > 2:
            print(0)
            exit()
        if cnt[A[i]] == 1:
            ans = (ans * 2) % (10 ** 9 + 7)
    print(ans)
else:
    for i in range(N):
        if A[i] % 2 == 1:
            print(0)
            exit()
        if A[i] > 0:
            cnt[A[i]] += 1
            if cnt[A[i]] > 2:
                print(0)
                exit()
            if cnt[A[i]] == 1:
                ans = (ans * 2) % (10 ** 9 + 7)
        if A[i] == 0:
            cnt[0] += 1
            if cnt[0] > 1:
                print(0)
                exit()
    print(ans)

174AC - ABC104C: All Green

競プロ bit全探索
ABC104-C (300 points)
問題

i \times 100 \ (1 \leq i \leq D) 点の問題がそれぞれ p_i 問, 計 p_1 + p_2 + \ldots + p_D 問の問題が与えられ, 総合スコアを以下のように計算するとき, G 点以上の総合スコアを獲得するために解かなければならない最少の問題数を求める.

  • 基本スコア：解いた問題すべての配点の合計.
  • コンプリートボーナス： 100i 点を付けられた p_i 問の問題すべてを解くと, 基本スコアとは別に c_i 点を獲得.
  • 総合スコア：基本スコアとコンプリートボーナスの合計.
  • 1 \leq D \leq 10
  • 1 \leq p_i \leq 10^2
  • 1 \leq c_i \leq 10^6
  • 100 \leq G
  • 入力は全て整数.
  • c_i, G は全て100の倍数.
  • 総合スコアを G 点以上にすることは可能.
方針
  • 1 \leq D \leq 10 なので, 各点数の問題群について全て解く or 解かないで 2^D ケースを全探索. 
import math

# input
D, G = map(int, input().split())
Problems = [list(map(int, input().split())) for _ in range(D)]

ans = float('inf')

for i in range(1 << D): # bit全探索
    solved = [a for a in range(D)] # 全て解く＝ボーナス点をもらう問題群
    count = 0
    point = 0
    for j in range(D): # 全て解く＝ボーナス点をもらう問題群の点数合計
        if i & (1 << j): # (j + 1) * 100 点の問題を全て解く場合
            count += Problems[j][0]
            point += Problems[j][0] * (j + 1) * 100 + Problems[j][1]
            solved.remove(j) # (j + 1) * 100 点の問題は全て解答済
    if point < G and len(solved) > 0:
        k = max(solved)
        if math.ceil((G - point) / ((k + 1) * 100)) > Problems[k][0] - 1:
            continue
        else:
            count += math.ceil((G - point) / ((k + 1) * 100))
            ans = min(ans, count)
    else:
        ans = min(ans, count)

print(ans)

171AC - ABC051C: Back and Forth

競プロ
ABC51-C (300 points)
問題

2 点 (sx, sy), (tx, ty) 間を, 途中で同じ座標を複数回通らないように 2 往復するとき, 最短経路を求める.

  • -10^3 \leq sx < tx \leq 10^3
  • -10^3 \leq sy < ty \leq 10^3
  • 入力は全て整数.
方針
  • 1 往復目は素直に行けば良い.
  • 2 往復目は, 上下左右に 1 だけ余分に移動すればOK. 
# input
sx, sy, tx, ty = map(int, input().split())

for i in range(ty - sy):
    print('U', end = "")

for i in range(tx - sx):
    print('R', end = "")

for i in range(ty - sy):
    print('D', end = "")

for i in range(tx - sx):
    print('L', end = "")

print('L', end = "")

for i in range(ty - sy + 1):
    print('U', end = "")

for i in range(tx - sx + 1):
    print('R', end = "")

print('D', end = "")

print('R', end = "")

for i in range(ty - sy + 1):
    print('D', end = "")

for i in range(tx - sx + 1):
    print('L', end = "")

165AC - ABC052C: Factors of Factorial

競プロ 素因数分解 10^9+7
ABC052-C (300 points)
問題

整数 N が与えられるとき, N! の正の約数の個数を 10^9 + 7 で割った余りを求める.

  • 1 \leq N \leq 10^3
方針


N = \prod_i p_i^{a_i}

\ \ \ \ であるとき, 約数の個数 d(N) は


d(N) = \prod_i (a_i + 1)

  • modの計算は掛け算の途中でしても良いので, 各素因数についてmodを取りながら約数を数えていく.
参考

sucrose.hatenablog.com
qiita.com

import math

# input
N = int(input())

def prime_factor_table(n):
    table = [0] * (n + 1)
    
    for i in range(2, n + 1):
        if table[i] == 0:
            for j in range(i + i, n + 1, i):
                table[j] = i
    
    return table

def prime_factor(n, prime_factor_table):
    prime_count = dict()

    while prime_factor_table[n] != 0:
        if prime_factor_table[n] in prime_count.keys():
            prime_count[prime_factor_table[n]] += 1
        else:
            prime_count[prime_factor_table[n]] = 1
        n = int(n/prime_factor_table[n])
    if n in prime_count.keys():
        prime_count[n] += 1
    else:
        prime_count[n] = 1
    return prime_count

Ps = dict()
P_1000 = prime_factor_table(1000)
ans = 1

for i in range(2, N + 1):
    P_i = prime_factor(i, P_1000)
    for k in P_i.keys():
        if k in Ps.keys():
            Ps[k] += P_i[k]
        else:
            Ps[k] = P_i[k]

for k in Ps.keys():
    ans = (ans * (Ps[k] + 1)) % (10 ** 9 + 7)

print(ans)