2019-01-07

209AC - ABC107C: Candles

競プロ

ABC107-C (300 points)

問題

数直線上に置かれた $N$ 本のろうそくのうち, $K$ 本に火を付けるのに必要な最小の時間を求める.

原点からスタート, 左右に速度 $1$ で移動可能
$1 \leq N \leq 10^5$
$1 \leq K \leq N$
$|x_i| \leq 10^8$
$x_1 < x_2 < \ldots < x_N$
入力は全て整数

方針

最適解の形を想像する.

ろうそくを飛び飛びにつけることはないので, $i$ 本目から $i + K - 1$ 本目まで火をつけることを考える.
原点 -> $i$ 本目 -> $i + K - 1$ 本目 or 原点 -> $i + K - 1$ 本目 -> $i$ 本目

# input
n, k = map(int, input().split())
X = list(map(int, input().split()))

# 飛び飛びで塗ることはない -> X[i] ~ X[i + k - 1] を全て塗る
# i = 1, ..., n - k + 1 について所要時間を調べる
# 原点 -> X[i] -> X[i + k - 1] or 原点 -> X[i + k - 1] -> X[i]
D = []
for i in range(n - k + 1):
    t1 = abs(X[i]) + (X[i + k - 1] - X[i])
    t2 = abs(X[i + k - 1]) + (X[i + k - 1] - X[i])
    D.append(min(t1, t2))

print(min(D))

2018-12-06

205AC - ABC042C: Iroha's Obsession

競プロ

ABC042-C (300 points)

問題

$N$ 以上の整数のうち, $D = \{ d_1, \ldots, d_k \}$ を含まない最小の整数を求める.

$1 \leq N \leq 10000$
$\leq k \leq 10$
$0 \leq d_1 < d_2 < \ldots < d_k \leq 9$
$\{ d_1, d_2, \ldots, d_k \} \neq \{ 1, 2, 3, 4, 5, 6, 7, 8, 9 \}$
入力は全て整数

方針

素直にやると...

置換が必要な桁のうち, 最大のものを求める.
その桁より上で置換可能（ $D$ に含まれない数で置換してより大きい数にすることが可能）な桁を求める.
置換する.

問題をそのまま実装するとよりスッキリ（issubset)

# input
n, k = map(int, input().split())
D = list(map(int, input().split()))

N = [int(x) for x in list(str(n))]
D_inv = sorted(list(set(range(10)) - set(D)))

m = len(N) + 1 # 置換する桁
for i in range(len(N)):
    if N[i] in D:
        m = i
        break

if m == len(N) + 1:
    print(n)
    exit()

n = len(N) + 1 # 置換可能な桁 
for i in range(m + 1):
    if N[i] < D_inv[len(D_inv) - 1]:
        n = i

ans = 0
if n == len(N) + 1: # 置換可能な桁がない場合
    if D_inv[0] == 0:
        ans += D_inv[1] * (10 ** len(N))
    else:
        ans += D_inv[0] * (10 ** len(N))
    for i in range(len(N)):
        ans += D_inv[0] * (10 ** (len(N) - 1 - i))
else:
    for i in range(len(N)):
        if i < n:
            ans += N[i] * (10 ** (len(N) - 1 - i))
        if i == n: 
            for j in D_inv:
                if j > N[i]:
                    ans += j * (10 ** (len(N) - 1 - i))
                    break
        if i > n:
            ans += D_inv[0] * (10 ** (len(N) - 1 - i))
print(ans)

# input
n, k = map(int, input().split())
D = input().split()
D_inv = set([str(i) for i in range(10)]) - set(D)

ans = n
while not set(list(str(ans))).issubset(D_inv):
    ans += 1
print(ans)

2018-12-05

203AC - ABC043C - Be Together

競プロ

ABC043-C (200 points)

問題

$N$ 個の整数 $a_1, \ldots, a_N$ に対して, $\sum (x - a_i)^2$ を最小化する整数 $x$ を求める.

$1 \leq N \leq 100$
$-100 \leq a_i \leq 100$
入力は全て整数

方針

目的関数 $f(x) = \sum (x - a_i)^2$ を微分すると $f'(x) = 2 (Nx - \sum a_i)$ となるので, $f(x)$ は下に凸な関数であり, $x = \frac{1}{N} \sum a_i$ で最小値を取る. $x$ は整数なので, この近くの整数だけ調べれば良い.

# input
n = int(input())
A = list(map(int, input().split()))

ans1 = sum(A) // n + (sum(A) % n != 0)
ans2 = ans1 - 1

cost1 = 0
cost2 = 0

for i in range(n):
    cost1 += (A[i] - ans1) ** 2
    cost2 += (A[i] - ans2) ** 2

print(min(cost1, cost2))

2018-11-29

200AC - ABC044C: Tak and Cards

競プロ数え上げ

ABC044-C (300 points)

問題

数字が書かれた $N$ 枚のカードの中から $1$ 枚以上選び, 選んだカードに書かれた整数の平均を $A$ にする選び方の総数を求める.

$1 \leq N \leq 50$
$1 \leq A \leq 50$
$1 \leq x_i \leq 50$
入力は全て整数

方針

与えられたカードから $1$ 枚以上選んで作ることのできる和を素直に全て求める.
collections.Counterをうまく使う.
$x_1, \ldots, x_i$ のカードで作ることのできる和の集合を $S_i$ とすると, $x_1, \ldots, x_i, x_{i + 1}$ のカードで作ることのできる和の集合は
$S_{i + 1} = \{ s, x_{i + 1}, s + x_{i + 1} | s \in S_i \}$

import collections

# input
n, a = map(int, input().split())
X = [int(i) - a for i in input().split()]

S = collections.Counter([0, X[0]])
# Xから1枚以上選んで作ることが可能な和:作り方の場合の数
# 初期状態はX = X[0]のときに作ることが可能な和
# 1枚も選ばない＝0:1通り
# X[0]のみ選ぶ＝X[0]:1通り

for i in X[1:]: # 選べるカードを増やしていく (X[0] ~ X[i] から選ぶ)
    S_temp = collections.Counter()
    for s, c in S.items():
        S_temp[s + i] += c # X[0] ~ X[i - 1] で作れる和に X[i] を足す
    S += S_temp

print(S[0] - 1) # 1枚も選ばないのはルール違反

2018-11-25

197AC - ABC045C: Many Formulas

競プロ

ABC045-C (300 points)

問題

$'1'$ 以上 $'9'$ 以下の数字のみからなる文字列 $S$ が与えられ, この文字列の中に $'+'$ を挿入して数式を作り, 和を計算すること考える.
ありうる全ての数式の値を計算し, その合計を求める.

$1 \leq |S| \leq 10$
$S$ に含まれる文字は全て $'1'$ ~ $'9'$ の数字

方針

$S_i$ が $10^{k}$ の位になる場合を考える.

部分列 $S_1, \ldots, S_i$ に $'+'$ を入れる場合の数は $2^{i - 1}$ 通り.
部分列 $S_i, \ldots, S_{i + k}$ には $'+'$ は入らない.
部分列 $S_{i + k}, \ldots, S_N$ に $'+'$ を入れる場合の数は $2^{N - i - k}$ 通り.

# input
l = [int(x) for x in list(input())]

N = len(l)
ans = 0

for i in range(N):
    for k in range(N - i - 1):
        ans += (2 ** i) * (2 ** (N - i - k - 2)) * (10 ** k) * l[i]
    ans += (2 ** i) * (10 ** (N - i - 1)) * l[i]

print(ans)

2018-11-21

194AC - ABC046C: AtCoDeer and Election Report

競プロ

ABC046-C (300 points)

問題

高橋くんと青木くんの二人が出ている選挙で, 二人の得票数の比が表示されている選挙速報を見ている.
$i$ 回目に画面を見たときに表示されている比が $T_i : A_i$ であるとき, $N$ 回目に画面を見たときの投票数として考えられるものの最小値を求める.
ただし, $1$ 回目の画面を見た時点で, 高橋くん, 青木くんはそれぞれ $1$ 票以上を得ており, 得票数が途中で減ることはないものする.

$1 \leq N \leq 1000$
$1 \leq T_i, A_i \leq 1000 (1 \leq i \leq N)$
$T_i$ と $A_i$ は互いに素である. $(1 \leq i \leq N)$
答えは $10^{18}$ 以下である.

方針

以下の条件を満たすように [k = 1, \ldots, N] について考えられる最小の投票数を順番に求めていく.

$1$ 回目の画面を見た時点で, 高橋くん, 青木くんそれぞれ $1$ 票以上を得ている.
$k$ 回目に画面を見たときの高橋くん, 青木くんそれぞれの得票数は $m \times T_k$ , $m \times A_k$ ( $m$ は自然数) でなければならない.
得票数が途中で減ることはない.
math.ceilの挙動でハマる. 未解決.

import math

# input
N = int(input())
TA = [list(map(int, input().split())) for _ in range(N)]


T = 1 # 高橋くんの最小得票数
A = 1 # 青木くんの最小得票数
ans = 2

for i in range(0, N):
    # m = max(math.ceil(T / TA[i][0]), math.ceil(A / TA[i][1]))
    m = max(T // TA[i][0] + (T % TA[i][0] != 0), A // TA[i][1] + (A % TA[i][1] != 0))
    T = TA[i][0] * m
    A = TA[i][1] * m
    ans = T + A

print(ans)

2018-11-20

191AC - ABC047C: 1D Reversi

競プロ

ABC047-C (300 points)

問題

黒と白の石からなる列を, オセロの要領で両端に石を追加していくことで全て同じ色にすることを考える.
このとき必要な石の最小個数を求める.

$1 \leq |S| \leq 10^5$
$S$ に含まれる文字は $'W'$ または $'B'$ である.

方針

黒石と白石の境目を考える. 石を追加で $1$ つ置くと, 境目を $1$ つ消すことができる. 最終的に境目がなくなった状態になれば良いので, 初期状態の境目の数が必要な石の最小数.

# input
S = input()

ans = 0
for i in range(len(S) - 1):
    if S[i + 1] != S[i]:
        ans += 1

print(ans)