【ABC331】FortranでA,B,C問題

## 目次
  - [A - Tomorrow](#a---tomorrow)
  - [B - Buy One Carton of Milk](#b----buy-one-carton-of-milk)
  - [C - Sum of Numbers Greater Than Me](#c---sum-of-numbers-greater-than-me)

## A - Tomorrow
### 問題
AtCoder 国では1年の暦が1 月から M 月までの M ヶ月間あり、１ヶ月は 1 日から D 日までの D 日間あります。
y 年 m 月 d 日の翌日は何年何月何日であるか求めてください。

>**制約**
>1. $1000≤y≤9000$ 
>2. $1≤m≤M≤99$ 
>3. $1≤d≤D≤99$
>4. 入力は全て整数である

詳細はこちらです。

https://atcoder.jp/contests/abc331/tasks/abc331_a

### 解説
現在の年月日が月末、年末であるかを順に調べ、該当する場合は年月日の繰り上げ処理を行います。


### プログラム例
```Fortran
program abc331a
    !MM   ：1年間の月数
    !DD   ：1ヶ月の日数
    !y,m,d： y 年 m 月 d 日
    !cnt  ：桁上がりの判定
    
    implicit none
    integer(16) MM, DD, y, m, d, cnt

    !入力
    read (*, *) MM, DD
    read (*, *) y, m, d

    !出力
    cnt = 0
    if (d >= DD) then
        d = 1
        m = m + 1
        cnt = 1
    end if
    if (m >= MM) then
        m = 1
        y = y + 1
        cnt = 1
    end if
    if (cnt == 0) then
        write (*, '(i0,1x,i0,1x,i0)') y, m, d + 1
    else
        write (*, '(i0,1x,i0,1x,i0)') y, m, d
    end if
end program abc331a

```



## B - Buy One Carton of Milk
### 問題
卵 6 個入りのパックが S 円、卵 8 個入りのパックが M 円、卵 12 個入りのパックが L 円で売られています。
どのパックも何パックでも購入できるとき、N 個以上の卵を買うために必要な最小の金額を求めてください。


>**条件**
>1. $1≤N≤100$
>2. L 以上、R以下であるどの整数Yでも$|X_i - A_i| ≤ |Y_i - A_i| $を満たす。
>3. A_1 ,A_2 ,…,A_N がすべて等しいということはない

>**制約**
>1. $1≤N≤100$
>2. $1≤S,M,L≤10^4$
>3. 入力は全て整数である

詳細はこちらです。

https://atcoder.jp/contests/abc331/tasks/abc331_b

### 解説
考えられる組み合わせを全て試し、最小の個数を求めます。
`do文`の３重ループを使い解きますか、N は最大でも１００と小さいためTLEにはなりません。


### プログラム例
```Fortran
program abc331b
    !S,M,L   ：各パックの値段
    !sn,mn,ln：各パックの購入個数
    !N       ：卵の必要個数
    !nn      ：購入した卵の個数
    !p       ：卵をnn個購入した際の金額
    !minp    ：条件を満たす最小の購入金額
    implicit none
    integer(16) N, S, M, L
    integer(16) sn, mn, ln, minp, p, i, j, k, nn

    read (*, *) N, S, M, L

    minp = 1000000000
    i = 0
    do
        ln = i
        nn = ln*12
        if (nn >= N) then
            p = ln*L
            minp = min(minp, p)
            exit
        end if
        j = 0
        do
            mn = j
            nn = ln*12 + mn*8
            if (nn >= N) then
                p = ln*L + mn*M
                minp = min(minp, p)
                exit
            end if
            k = 0
            do
                sn = k
                nn = ln*12 + mn*8 + sn*6
                if (nn >= N) then
                    p = ln*L + mn*M + sn*S
                    minp = min(minp, p)
                    exit
                end if
                k = k + 1
            end do
            j = j + 1
        end do
        i = i + 1
    end do
    write (*, *) minp
end program abc331b
```



## C - Sum of Numbers Greater Than Me
### 問題
長さ N の数列 $A=(A_1,…,A_N)$ が与えられます。
$i=1,…,N$のそれぞれについて、$A$ の全要素の中で $A_i$ より大きな要素全ての和を求めよ。

>1. $1≤N≤2×10^5$
>2. $1≤A_i≤10^6$
>3. 入力は全て整数である


詳細はこちらです。

https://atcoder.jp/contests/abc331/tasks/abc331_c


### 解説
$1≤N≤2×10^5$であるため、各$i$　ごとに$A_i$より大きな要素を　1〜N　まで調べていると計算量が多くなりTLEとなります。
対策としてあらかじめ A を昇順に並べておき、尺取り法を使って和を求めることで、計算量を減らす工夫を行います。


### プログラム例
```Fortran
program abc331c
    !A(N) ：長さNの配列
    !A2(N)：ソート後の配列A(N)
    implicit none
    integer(16) N, i, j, cnt
    integer(16), allocatable::A(:), An(:), A2(:)

    read (*, *) N
    allocate (A(N), An(N), A2(N))
    read (*, *) A(:)
    do i = 1, N
        An(i) = i
    end do
    call margesort(A, An, N)

    cnt = sum(A)
    do i = 1, N
        if (i /= 1 .and. A(i) == A(i - 1)) then
            A2(i) = cnt
            cycle
        else
            cnt = cnt - A(i)
        end if

        do j = i + 1, N
            if (A(i) < A(j)) exit
            cnt = cnt - A(j)
        end do
        A2(i) = cnt
    end do

    call margesort(An, A2, N)
    do i = 1, N
        write (*, '(i0,1x)', advance='no') A2(i)
    end do

contains
    subroutine margesort(x, y, n)
        integer(16) N
        integer(16) x(N), tmp(N)
        integer(16) y(N), tmp2(N)
        integer(16) start, end
        start = 1; end = N
        call loop_margesort(x, y, tmp, tmp2, N, start, end)
    end subroutine
    recursive subroutine loop_margesort(x, y, tmp, tmp2, N, left, right)
        integer(16) left, right, mid
        integer(16) N
        integer(16) x(N), tmp(N)
        integer(16) y(N), tmp2(N)
        integer(16) i, j, k

        !これ以上2分かつできないならretrun
        if (left >= right) return

        !分割できるだけ分割する
        mid = (left + right)/2
        call loop_margesort(x, y, tmp, tmp2, N, left, mid)
        call loop_margesort(x, y, tmp, tmp2, N, mid + 1, right)

        !並び替えの下準備としてtmpに配列をコピー
        j = 0
        tmp(left:mid) = x(left:mid)
        tmp2(left:mid) = y(left:mid)
        do i = mid + 1, right
            tmp(i) = x(right - j)
            tmp2(i) = y(right - j)
            j = j + 1
        end do

        !大小比較して小さい順に入れていく
        i = left
        j = right
        !write (*, '(3x,*(f13.101x),a)', advance='no') x(left:right)
        !write (*, '(a)', advance='no') '>>'
        do k = left, right
            if (tmp(i) < tmp(j)) then
                x(k) = tmp(i)
                y(k) = tmp2(i)
                i = i + 1
            else if (tmp(i) == tmp(j) .and. tmp2(i) < tmp2(j)) then
                x(k) = tmp(i)
                y(k) = tmp2(i)
                i = i + 1
            else
                x(k) = tmp(j)
                y(k) = tmp2(j)
                j = j - 1
            end if
        end do
        !write (*, '(3x,*(f13.10,1x))') x(left:right)
    end subroutine loop_margesort
end program abc331c
```