コドフォEducational 90 A~D解説[python]

結果：A~Dの4完遅解きでぎり青パフォくらい

A - Donut Shops

算数、パズル

概要

２つの店A,Bがある。
Aではドーナツを１つa ドルでうり、Bではb 個単位でc ドルでうる。

考察

式に落とすとb*k < c*ceil(k/b) だが、この中で、１つでも条件を満たすものを考えれば良い(コドフォでよくある）
この中で、１つでも条件を満たすものを考えれば良い(コドフォでよくある）は、閾値を考える
B が安くなるのは、ちょうど単位セットで変えた時で最小はb の時
Aが安くなるのはB が最も余分が多い時で1こしか買わないとき

実装

import sys
import math

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
t = int(input())
for case in range(t):
    a, b, c = map(int, input().split())
    if a >= c:
        print(-1, end=" ")
    else:
        print(1, end=" ")
    if a * b <= c:
        print(-1)
    else:
        print(b)

全体で10min
if a*b <= c : else の箇所で出力を1 にしてて1WA出した。（ちゃんと解けたと思っても確認しようね）

B - 01 Game

ゲーム

考察：

　動けなくなる時とは？：隣接した文字が全て同じ文字なら（１種類の文字だけになれば動けない）
　必ず1回の操作で0,1が１つずつ減る
　場所や順番は関係ないので　1,0の少ない方の個数が奇数なら先行が勝つ
文字列で/b を除きたい時ってどうやるんだっけ？

実装

import sys
import math

read = sys.stdin.buffer.read
# input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
t = int(input())
for case in range(t):
    s = input()
    zero_num = s.count("0")
    # 小さい方が奇数なら勝ち ただし0の場合は数えない
    if min(len(s) - zero_num, zero_num) == 0:
        print("NET")
    elif min(len(s) - zero_num, zero_num) % 2:
        print("DA")
    else:
        print("NET")

C - Pluses and Minuses

コードの理解、累積和（事前計算）、定式化
二重ループ

考察

　内側をみるとbreakされないならlen(s) -1 になる
　先頭から見てcur　より- の数が+より大きくなったら終了
　外側はok だったらberakする
　最後まで行ってもcur がずっと0以上なら続ける
定式化すると、累積わ*-1を持っておいて、1,2,3...と回してそこまでの分を足せば良い
O(N)

実装

import sys
import math

read = sys.stdin.buffer.read
# input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
t = int(input())
for case in range(t):
    s = input()
    n = len(s)
    ans = 0
    cnt = [0] * (1 + n)
    cum = 0
    for i in range(n):
        if s[i] == "-":
            cum += 1
        else:
            cum -= 1
        if cum > 0 and cnt[cum] == 0:
            ans += i + 1
            cnt[cum] = i + 1
    # 最後まで行ったケースを考える。
    ans += i + 1
    print(ans)

D - Maximum Sum on Even Positions

数列の操作、反転、累積和、実装ゲー

考察

偶数番目にくる数がどのように変わるだけを見れば良い。
l,r の偶奇で場合わけする
even,even => 変わらない
even , odd => 範囲内の選択が逆転
odd, even => 同様
odd,odd => 変わらない
任意の地点に対して、そこまでの偶数、奇数それぞれの累積和を持って差分の差分を計算してmax を取れば良さそう
　どうやってmaxを計算するか？
　まとめたい。偶数の時は+ 奇数は- の累積和をとる

　累積わの区間の最大はどうやって求める？
　現在のmax, minを持ってそれぞれ更新する感じ

実装

step1 : 現在の偶数番目の和を計算
step2: 累積和を計算する
step3: 偶数番目、奇数番目それぞれ累積和の列に対して、現在の最大、最小をそれぞれ更新して差分のmaxを計算

import sys
import math

read = sys.stdin.buffer.read
# input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
t = int(input())
for case in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    """step1 : 現在の偶数番目の和を計算
step2: 累積和を計算する
step3: 偶数番目、奇数番目それぞれ累積和の列に対して、現在の最大、最小をそれぞれ更新して差分のmaxを計算
"""
    origin = sum([a[i] for i in range(n) if i % 2 == 0])
    acc = [0] * (1 + n)
    for i in range(n):
        if i % 2:
            acc[i + 1] = acc[i] + a[i]
        else:
            acc[i + 1] = acc[i] - a[i]
    # 偶数に対して現在のmax,minを更新=> min のみの管理
    ans_dif = 0
    # print(origin, acc)
    even_min = acc[0]
    for i in range(n // 2 + 1):
        even_min = min(even_min, acc[i * 2])
        ans_dif = max(ans_dif, acc[i * 2] - even_min)

    odd_min = acc[1]
    for i in range((1 + n) // 2):
        odd_min = min(odd_min, acc[i * 2 + 1])
        ans_dif = max(ans_dif, acc[i * 2 + 1] - odd_min)
    print(ans_dif + origin)

こういう問題は遷移を頭の中でイメージできなくて難しい。典型的な問題みたいなので慣れかな。