A - Full Moon

問題

今日を 1 日目とすると、今日以降で満月を見られる最初の日は M 日目です。以後は P 日ごとに満月が見れます。
1 日目から N 日目までの中で満月を見られる日の数を求めてください。

制約

$1≤N≤2×10^5$

$1≤M≤P≤2×10^5$

入力される数値は全て整数

詳細はこちらです。

解説

【フローチャート】
１回以上満月が見れるかの判定をした後、全体で何回満月が見れるか計算します。

【補足】
※1
制約1,2より$N<M$となるケースが考えられるため、1日も満月が見れない場合もあります。
if文で$N<M$の判定を行います。

※２
$N<M$の場合、1日も満月を見ることができません。
結果として0を出力します。

※3
$M≤N$の場合は満月を１回以上見ることができます。
以下の計算を行い、全体で何回満月を見れるか計算します。

$Ans=(N-M)/P +1$

プログラム例

program abc318a
    implicit none
    integer N, M, P
    integer ans

    !読み込み
    read (*, *) N, M, P

    !満月の日数計算
    if (N - M < 0) then
        write (*, '(i0)') 0
        stop
    end if
    ans = (N - M)/P + 1

    !結果の出力
    write (*, '(i0)') ans
end program abc318a

B - Overlapping sheets

問題

座標平面上に N 枚の長方形のシートが張られています。
1 枚以上のシートによって覆われている領域の面積 Sを求めてください。

制約

$2≤N≤100$

$0≤A_i<B_i≤100$

$0≤C_i<D_i≤100$

入力はすべて整数

詳細はこちらです。

解説

【フローチャート】
１枚ずつ全てのシートの範囲を調べ、シートが１枚でも張られている範囲を記録し面積を求めます。

【補足】
※1
シート i が張られている範囲を計算します。
シートは１マス単位、長方形で張られているので、シートの有無の記録は論理型の２次元配列で管理します。
シートが張られているマス(配列)はtrueにします。

※2
シートが張られている範囲を集計します。
集計には、count関数を使用します。
count関数は対象とする変数に対して、.ture.となっている個数を戻り値として返します。

プログラム例

program abc318b
    implicit none
    integer i, j, N, cnt
    logical sheet(101, 101)
    integer, allocatable :: A(:), B(:), C(:), D(:)

    !読み込み
    read (*, *) N
    allocate (A(N), B(N), C(N), D(N))
    do i = 1, N
        read (*, *) A(i), B(i), C(i), D(i)
    end do

    !シートの作成
    A = A + 1; C = C + 1
    cnt = 0; sheet = .false.
    do i = 1, N
        do j = C(i), D(i)
            sheet(j, A(i):B(i)) = .true.
        end do
    end do

    !結果の出力
    cnt = count(sheet)
    write (*, '(i0)') cnt
end program abc318b

C - Blue Spring

問題

N 日間の旅行を計画しています。
それぞれの日について、運賃の通常料金を払うか、1 日周遊パスを 1 枚使用するか選ぶことができます。
1 日周遊パスはD 枚セットで P 円で売られており、何枚でも買うことができます。

旅行にかかる最小の総額を求めてください。

制約

$1≤N≤2×10^5$

$1≤D≤2×10^5$

$1≤P≤10^9$

$1≤F_i≤10^9$

入力はすべて整数

詳細はこちらです。

解説

【注意点】
$1≤N≤2×10^5$であるため、1 日周遊パスを i 枚使う際の総額を毎回計算すると、TLEとなってしまします。

【フローチャート】
あらかじめ1 日周遊パスを使わない場合の総額を計算し、1 日周遊パスを使う枚数に応じて総額を増減させ最小金額を求めます。

【補足】
※1
1日周遊券は1日の運賃が高い順に使用すると、総額を効率的に抑えられます。
旅行期間の各日の運賃は降順ではないのでマージソートにより降順に並び替え、1日周遊券を使う順番を求めます。

※2
以降の処理で1日周遊パスを i 枚使う場合の総額を計算するため、あらかじめ1日周遊パスを１枚も使わない場合の総額を計算します。
計算にはSUM関数を使用します。

※3
1日周遊パスを i 枚使う場合の総額を計算します。
計算は1日周遊パスを使用した増分だけ、金額を増減させ計算します。
1日周遊パスを適用する順番は1日の運賃が高い順とします。

プログラム例

program abc318c
    implicit none
    integer(16) N, D, P
    integer(16) i, ticket, start, total, ans, diff
    integer(16), allocatable::F(:), tmp(:)

    !入力
    read (*, *) N, D, P
    allocate (F(N), tmp(N))
    read (*, *) F(:)

    !最小金額の計算
    ticket = 0; start = 1
    call margesort(F, tmp, N, start, N)
    total = sum(F)
    ans = total
    do i = 1, N, D
        diff = D - 1 + i
        if (diff > N) diff = N
        total = total - sum(F(i:diff)) + P
        ans = min(ans, total)
        !write (*, '(i0)') total
    end do

    write (*, '(i0)') ans

contains
    recursive subroutine margesort(x, tmp, N, left, right)
        integer(16) left, right, mid
        integer(16) N
        integer(16) x(N), tmp(N)
        integer(16) i, j, k

        if (left >= right) return

        mid = (left + right)/2
        call margesort(x, tmp, N, left, mid)
        call margesort(x, tmp, N, mid + 1, right)

        j = 0
        tmp(left:mid) = x(left:mid)
        do i = mid + 1, right
            tmp(i) = x(right - j)
            j = j + 1
        end do

        i = left
        j = right

        do k = left, right
            if (tmp(i) > tmp(j)) then
                x(k) = tmp(i)
                i = i + 1
            else if (tmp(i) == tmp(j)) then
                x(k) = tmp(i)
                i = i + 1
            else
                x(k) = tmp(j)
                j = j - 1
            end if
        end do
    end subroutine margesort
end program abc318c

感想

C問題はABCXXXcの類題でした。解法を覚えていたのでアルゴリズムに悩まずに解けました。