PythonでJOI難易度6を埋める #22

B - 古本屋 (Books)

DPDPDPDPDPDPDPDPDPDP．
DPで解く．ジャンルごとに売る本を決めるとき，同じジャンルの中で高いものから売った方が合計買取額は大きくなる．そこで，ジャンルごとに降順でsortし，買取ボーナスも含めた値段で累積和を取る．ジャンルの累積和をとするとき，の番目は，]]]] + となる．
ここまできたら，後はDPで解ける．]]=番目のジャンルまでで，合計冊になるように本を売ったときの最大の買取金額とする．このDPはナップサックDPの重さが冊数になったものなので，同じ要領で解ける．

from sys import stdin
input = stdin.readline
inf = float('inf')

n, k = map(int, input().strip().split())
books = [list(map(int, input().strip().split())) for _ in range(n)]

genre = [[] for _ in range(10)]
for i in range(n):
    genre[books[i][1] -1].append(books[i][0])

cnt_genre = 0
cnt_books = 0
for i in range(10):
    if len(genre[i]) != 0:
        cnt_genre += 1
        genre[i].sort(reverse = True)
        cnt_books = max(len(genre[i]), cnt_books)

csum_genre = [[] for _ in range(cnt_genre)]
for i in range(10):
    if len(genre[i]) == 0:
        continue
    for j in range(len(genre[i])):
        if j == 0:
            csum_genre[i].append(genre[i][j])
        else:
            csum_genre[i].append(genre[i][j] + csum_genre[i][-1] + 2 * j)

dp = [[0 for _ in range(max(cnt_books, k) + 1)] for _ in range(cnt_genre)]

for i in range(1, len(csum_genre[0]) + 1):
    dp[0][i] = csum_genre[0][i - 1]

for i in range(1, cnt_genre):
    length = len(csum_genre[i])
    for j in range(max(cnt_books, k) + 1): #ジャンルiまででj冊売る
        tmp = -inf
        if j == 0:
            dp[i][j] = 0
            continue
        if length - j >= 0:
            for l in range(j): #ジャンルiをl冊まで売る(0 <= l <= j) l+1冊売却
                tmp = max(dp[i - 1][j - l - 1] + csum_genre[i][l], tmp)
        else:
            for l in range(length):
                tmp = max(dp[i - 1][j - l - 1] + csum_genre[i][l], tmp)
        dp[i][j] = max(dp[i - 1][j], tmp, dp[i][j])
print(dp[-1][k])

PythonでJOI難易度6を埋める #21

anagram - アナグラム (Anagram)

計算自体は数学でも見る問題だが，実装が破滅したので，こちらを参考に

from collections import Counter
from math import factorial
from sys import stdin
input = stdin.readline

s = list(input().strip())

def comb(x):
    cal = factorial(len(x))
    for i in Counter(x).values():
        cal //= factorial(i) #同じ文字が複数個，存在するならその数の階乗で割る

    return cal

ans = 0
for i, j in enumerate(s):
    used = set()
    for k, l in enumerate(s[i:], start = i):
        if (l < j) and (l not in used):
            ans += comb(s[i: k] + s[k + 1:]) #k番目を除いた順列
            used.add(l)

print(ans + 1) #自分よりも前にans個あるので+1

PythonでJOI難易度6を埋める #20

D - JOI国のお散歩事情 (Walking in JOI Kingdom)

それぞれの国民が他の国民と会い，おしゃべりを始める点を調べる．番目の国民をとする．が東向きに進むとき，よりも東にいて，に一番近い西に進む国民をとすると，十分な時間があれば，二人はとなる．ただし，東に進む国民は，西側から調べていくと更新がうまくできないので，東側からもう一度調べる．もちろん，自分の進行方向に自分と逆向きに進む国民がいなければ，その国民は最初の座標から時間だけ動く．
全ての国民がおしゃべりを始める点が分かれば，与えられた時間で到達可能ならその座標を，到達不可能なら，最初の座標+を出力すればよい．

from bisect import bisect_left
from sys import stdin
input = stdin.readline

n, t, q = map(int, input().strip().split())
nation = [list(map(int, input().strip().split())) for _ in range(n)]
query = [int(input().strip()) for _ in range(q)]

index_left = []
index_right = []

for i in range(n):
    if nation[i][1] == 1:
        index_right.append(i)
    else:
        index_left.append(i)

state = []
length_l = len(index_left)
length_r = len(index_right)
inf = float('inf')

for i in range(n):
    if i == 0:
        if nation[i][1] == 1:
            index = bisect_left(index_left, i)
            if index == length_l:
                state.append(inf)
            else:
                ave = (nation[index_left[index]][0] + nation[i][0]) // 2
                state.append(ave)
        if nation[i][1] == 2:
            index = bisect_left(index_right, i)
            if index == 0:
                state.append(-inf)
            else:
                ave = (nation[index_right[index - 1]][0] + nation[i][0]) // 2
                state.append(ave)
    if i != 0:
        if nation[i][1] == 1:
            index = bisect_left(index_left, i)
            if index == length_l:
                state.append(inf)
            else:
                ave = (nation[index_left[index]][0] + nation[i][0]) // 2
                state.append(ave)
        if nation[i][1] == 2:
            if nation[i][1] == nation[i - 1][1]:
                state.append(state[-1])
                continue
            index = bisect_left(index_right, i)
            if index == 0:
                state.append(-inf)
            else:
                ave = (nation[index_right[index - 1]][0] + nation[i][0]) // 2
                state.append(ave)

for i in reversed(range(n - 1)):
    if nation[i][1] == nation[i + 1][1] == 1:
        state[i] = state[i + 1]

for i in range(q):
    if state[query[i] - 1] == inf:
        print(nation[query[i] - 1][0] + t)
    elif state[query[i] - 1] == inf:
        print(nation[query[i] - 1][0] - t)
    elif abs(state[query[i] - 1] - nation[query[i] - 1][0]) <= t:
        print(state[query[i] - 1])
    else:
        if nation[query[i] - 1][1] == 1:
            print(nation[query[i] - 1][0] + t)
        if nation[query[i]  -1][1] == 2:
            print(nation[query[i] - 1][0] - t)

PythonでJOI難易度6を埋める #19

H - JOIOJI

まず，各文字の個数で累積和を取る．それぞれの累積和をcsum_j, o ,i とする．区間(i, j)で J, O, I の個数が同じになるとき，csum_j[ j ] - csum_j[ i ] = csum_o[ j ] - csum_o[ i ] = csum_i[ j ] - csum[ i ]となる．
上式を，
csum_j[ j ] - csum_j[ i ] = csum_o[ j ] -csum_o[ i ]，csum_j[ j ] - csum_j[ i ] = csum[ j ] - csum[ i ]
に分けて考えると，
csum_j[ j ] - csum_o[ j ] = csum_j[ i ] - csum_o[ i ]，csum_j[ j ] - csum[ j ] = csum_j[ i ] -csum[ i ]
と変形できる．なので，条件を満たすのは，
csum_j[ j ] - csum_o[ j ] = csum_j[ i ] - csum_o[ i ]，csum_j[ j ] - csum[ j ] = csum_j[ i ] -csum_[ i ]
をともに満たすとき．累積和の差をべつの配列として，同じ値どうしのindexの差の最大値を取ればよい．参考にした記事

from sys import stdin
from collections import defaultdict
input = stdin.readline

n = int(input().strip())
s = input().strip()

#各文字の個数の累積和をとる
csum_j = [0]
csum_o = [0]
csum_i = [0]
for i in range(n):
    if s[i] == 'J':
        csum_j.append(csum_j[-1] + 1)
        csum_o.append(csum_o[-1])
        csum_i.append(csum_i[-1])
    if s[i] == 'O':
        csum_j.append(csum_j[-1])
        csum_o.append(csum_o[-1] + 1)
        csum_i.append(csum_i[-1])
    if s[i] == 'I':
        csum_j.append(csum_j[-1])
        csum_o.append(csum_o[-1])
        csum_i.append(csum_i[-1] + 1)

jo = [j - o for j, o in zip(csum_j, csum_o)] #Jの個数=Oの個数
ji = [j - i for j, i in zip(csum_j, csum_i)] #Jの個数=Iの個数

dic = defaultdict(list)
for i, (jo, ji) in enumerate(zip(jo, ji)):
    dic[(jo, ji)].append(i)

ans = 0
for i in dic.values():
    ans = max(i[-1] - i[0], ans)
print(ans)
print(dic)

PythonでJOI難易度6を埋める #18

A - オレンジの出荷 (Oranges)

DP．dp[i]を番目までのオレンジを詰めるための最小のcostとして，計算する．

参考にした記事オレンジの出荷 (Oranges) - ia7ck-competitive-programming

from sys import stdin
input = stdin.readline

n, m, k = map(int, input().strip().split())
orange = [int(input().strip()) for _ in range(n)]

inf = float('inf')
dp = [inf for _ in range(n + 1)]
dp[0] = 0
for i in range(1, n + 1): #それぞれのオレンジ
    mx = -inf
    mn = inf
    for j in reversed(range(max(0, i - m), i)): #何個詰めるか
        mx = max(orange[j], mx)
        mn = min(orange[j], mn)
        dp[i] = min(dp[j] + (mx - mn) * (i - j) + k, dp[i])

print(dp[n])

PythonでJOI難易度6を埋める #17

B - スタンプラリー ２ (Collecting Stamps 2)

J は先端に，I は一番後ろに挿入したときに組み合わせは最大になる． O を挿入する場合を考えると，挿入した地点よりも前のJと後ろのIの積だけ増加することが分かります．これは累積和で計算できます．

from sys import stdin
input = stdin.readline

n = int(input().strip())
s = input().strip()

#ここからは先端と一番後ろに J ,I を挿入したときの組み合わせを計算
ans = 0
cnt = 0
cnt_j = [0]
cnt_o = [0]
cnt_i = [0]

s = s + 'I' #実際に結合して数える
for i in reversed(range(n + 1)):
    if s[i] == 'J':
        ans += cnt
        cnt_j.append(ans)
    if s[i] == 'O':
        cnt += cnt_i[-1]
        cnt_o.append(cnt_o[-1] + cnt_i[-1])
    if s[i] == 'I':
        cnt_i.append(cnt_i[-1] + 1)

cnt_j = [0]
cnt_o = [0]
cnt_i = [0]
index_j = []
index_i = []
tmp = 0
cnt = 0

s = s[:-1] #追加した'I'を消去
for i in reversed(range(n)):
    if s[i] == 'J':
        tmp += cnt
        index_j.append(i)
    if s[i] == 'O':
        cnt += cnt_i[-1]
        cnt_o.append(cnt_o[-1] + cnt_i[-1])
    if s[i] == 'I':
        cnt_i.append(cnt_i[-1] + 1)
        index_i.append(i)

ans = max(tmp + cnt_o[-1], ans) #上の二つの場合の大きい方を選択

#ここからは'O'を挿入する場所を考える
count_j = [0]
count_o = [0]
count_i = [0]

for i in range(n):
    if s[i] == 'J':
        count_j.append(count_j[-1] + 1)
        count_o.append(count_o[-1])
        count_i.append(count_i[-1])
    elif s[i] == 'O':
        count_j.append(count_j[-1])
        count_o.append(count_o[-1] + 1)
        count_i.append(count_i[-1])
    elif s[i] == 'I':
        count_j.append(count_j[-1])
        count_o.append(count_o[-1])
        count_i.append(count_i[-1] + 1)

for i in range(1, n): #'O'を挿入する場所
    ans = max(tmp + count_j[i] * (count_i[-1] - count_i[i]), ans)

print(ans)

PythonでJOI難易度6を埋める #16

A - フェーン現象 (Foehn Phenomena)

各地形変動が別々の事象だと誤読．地形を保存する方法が思いつかず終了． 場合分けでバグったせいで，inf時間かかった．参考にした提出

from sys import stdin
input = stdin.readline

n, q, s, t = map(int, input().strip().split())
ele = [int(input().strip()) for _ in range(n + 1)]
query = [list(map(int, input().strip().split())) for _ in range(q)]

diff = [ele[i + 1] - ele[i] for i in range(n)]

tmp = 0
for i in range(n):
    if diff[i] > 0:
        tmp -= s * diff[i]
    else:
        tmp -= t * diff[i]

for i in range(q):
    if diff[query[i][0] - 1] > 0:
        tmp += diff[query[i][0] - 1] * s
    else:
        tmp += diff[query[i][0] - 1] * t
    diff[query[i][0] - 1] += query[i][2]
    if diff[query[i][0] - 1] > 0:
        tmp -= diff[query[i][0] - 1] * s
    else:
        tmp -= diff[query[i][0] - 1] * t
    if query[i][1] < n:
        if diff[query[i][1]] > 0:
            tmp += diff[query[i][1]] * s
        else:
            tmp += diff[query[i][1]] * t
        diff[query[i][1]] -= query[i][2]
        if diff[query[i][1]] > 0:
            tmp -= diff[query[i][1]] * s
        else:
            tmp -= diff[query[i][1]] * t
    print(tmp)

できたこと

• 標高差に注目する