目次

1. C問題 - Coupon
2. D問題 - 2-variable Function

C問題『Coupon』

問題ページ：C問題 - Coupon

C問題までは、forループとか書ければ、アルゴリズム知らなくても、なんとなく解ける気がする(気がするだけ)。
クーポンの問題、筆者はケチな大阪人なので得意かも(｀・ω・´)
Nはせいぜい $10^5$ なので、時間はなんとかなりそう。

考え方

商品を高いもん順にソートしておく。
まず、商品の値段が0円にならないように、クーポンを使っていく。
クーポンを使った商品の値段は、値引き後の値段に置き換えていく。

場合分け①：途中でクーポンが無くなる場合
クーポンがなくなる時の商品の値段に注意。
商品は値引き後の値段に置き換えられているので、そのまま和を求めれば良い。

商品の値段が0円にならないように、クーポンを使っていくと、まだクーポンが余る場合がある。

場合分け②：いくつかの商品のみが0円になる場合
値引き後の値段が高いもん順に再度ソートする。
値引き後の値段は全てクーポンより安いはずなので、さらにクーポンを使うと0円になる。
クーポンが無くなった時点で、残った商品の値引き後の価格の和を求めれば良い。

場合分け③：全て0円になる場合
余ったクーポンの数が、商品の数より多い時、全て0円になる。

コード

C.py

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

#商品を高いもん順にソート
A.sort(reverse=True)

cnt = 0 #クーポンを使った枚数
ans = 0 #答え(出力)

for i in range(n):
  cnt += A[i]//x #クーポンを使った枚数
  if cnt >= k:
    #場合分け①：途中でクーポンが無くなる場合で、クーポンがなくなる時の商品の値段
    A[i] = A[i]-(k-(cnt-A[i]//x))*x 
    cnt = k #クーポンはk枚以上使えない
    break
  A[i] = A[i]%x #値引き後の値段に置き換え

#場合分け①：途中でクーポンが無くなる場合    
if cnt == k:
  ans = sum(A)

#場合分け②：いくつかの商品のみが0円になる場合
elif cnt < k and k-cnt<n: 
  A.sort(reverse=True) #値引き後の値段が高いもん順にソート
  ans = sum(A[k-cnt:]) #クーポンが無くなった時点で、残った商品の値引き後の価格の和

#場合分け③：全て0円になる場合
else:
  ans = 0
  
print(ans)

D問題『2-variable Function』

問題ページ：D問題 - 2-variable Function

むずい、むずいよぉ、ｳﾜｧｧｧｧｧｧヽ(`Д´)ﾉｧｧｧｧｧｧﾝ!
（2022/04/03追記：公式解説のやり方が天才肌すぎてとても凡人には思いつかなそうだったので、二分探索に変更しました）

考え方

$N$ は10の18乗だけど、$X$ は3次式なので、 $a, b$ は $10^6$ に収まることに気づくのがポイント。
$f(a,b)=a^3+a^2b+ab^2+b^3$ とする。
$a$ を固定すると、$f(a,b)$ は単調増加なので...そう、$b$ は二分探索で探せるヽ(・∀・)ﾉ

$a=0$ から $10^6-1$について、ギリギリ $f(a,b)≧N$ となる $b$ を二分探索で探す。
その最小値が答えになる。

コード

D.py

n = int(input())

#n=0の時はややこしいので場合分けしといた
if n==0:
    print(0)
    exit()

#f(a,b)を定義
def f(a,b):
    return a**3+a**2*b+a*b**2+b**3

#ここにf(a,b)を保存していく
X = []

for a in range(10**6):
    #二分探索の両端を定義
    ng = 0
    ok = 10**6
    while ok-ng>1:
        m = (ok+ng)//2
        if f(a,m)>=n:
            ok = m
        else:
            ng = m

    #ギリギリN以上になるf(a,b)をXに保存しておく
    X.append(f(a,ok))

print(min(X))

まとめ

最後まで見てくれてありがとう(´・ω・｀)
これからも自分の勉強がてらABCのC,D問題とか、過去問の解説上げてくかも。
来週も頑張ろうね(｀・ω・´)ｷﾘｯ