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

## 目次
  - [A - 2UP3DOWN](#a---2up3down)
  - [B - 326-like Numbers](#b---326-like-numbers)
  - [C - Peak](#c---peak)


## A - 2UP3DOWN
### 問題
ビルの X 階から Y 階へ移動したいです。
 
2 階分までの上りと 3 階分までの下りであれば移動には階段を使います。
それ以外の場合はエレベーターを使います。

ビルの X 階から Y 階へ移動するとき、移動に使うのは階段とエレベーターのどちらかを求めます。

>**制約**
>1. $1≤X,Y≤100$
>2. $X \neq Y$
>3. 入力は全ては整数である

詳細はこちらです。

https://atcoder.jp/contests/abc326/tasks/abc326_a


### 解説
**【フローチャート】**
入力 X,Y の数に応して条件を分岐させ、結果を出力します、

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/37167a6d-8e9c-a145-e6f8-631d747cdc52.png" width= %>

### プログラム例
```Fortran
program abc326a
    ! X：現在階
    ! Y：目的階
    implicit none
    integer x, y

    !入力
    read (*, *) X, Y

    !出力
    if (Y > X) then
        if (X + 2 >= Y) then
            write (*, '(a)') 'Yes'
        else
            write (*, '(a)') 'No'
        end if
    else
        if (X - 3 <= Y) then
            write (*, '(a)') 'Yes'
        else
            write (*, '(a)') 'No'
        end if
    end if
end program abc326a
```



## B - 326-like Numbers
### 問題
3 桁の正整数 N　 が与えられます。
3 桁の正整数で「百の位の数と十の位の数の積」が「一の位の数と等しい」、**N以上の最小の数**を探します。

>**制約**
>1. $100≤N≤919$
>2. N は整数である

詳細はこちらです。

https://atcoder.jp/contests/abc326/tasks/abc326_b


### 解説
**【フローチャート】**
**総当たり**で「百の位の数と十の位の数の積が一の位の数と等しい数」を探します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/c71ad74f-ad37-a1c4-1173-15c63a38d500.png" width=65%>

**【補足】**
※1
３桁の数　i を**百の位、十の位、一の位**に分ける計算を行います。
計算は以下の式を使用します。xは整数型で宣言しているため、小数点以下は切り捨てられます。
```
x(3) = i/100
x(2) = i/10 - x(3)*10
x(1) = i - x(3)*100 - x(2)*10
```


### プログラム例
```Fortran
program abc326b
    !N    ：入力した整数
    !x    ：Nを桁ごとに分割した数
    !check：百の位の数と十の位の数の積
    implicit none
    integer N, i
    integer x(3), check

    !入力
    read (*, *) N

    !判定
    do i = N, 919
        x(3) = i/100
        x(2) = i/10 - x(3)*10
        x(1) = i - x(3)*100 - x(2)*10
        check = x(3)*x(2)
        !write (*, *) i, x(3), x(2), x(1)
        if (check == x(1)) then
            write (*, '(i0)') i
            stop
        end if
    end do
end program abc326b
```



## C - Peak
### 問題
N 個のプレゼントが直線上の座標 $A_i$ に配置されています。

直線上の長さ M の半開区間 **[x,x+M)** を選び、そこに含まれるプレゼントを全て獲得します。
最大でいくつのプレゼントを獲得することができるかを求めます。

>**制約**
>1. 入力は全て整数
>2. $1≤N≤3×10^5$
>3. $1≤M≤10^9$
>4. $1≤A_i≤10^9$

詳細はこちらです。

https://atcoder.jp/contests/abc326/tasks/abc326_c


### 解説
**【フローチャート】**
$1≤N≤3×10^5$ であるため、総当たりでプレゼントの入手可否を調べると`TLE`となります。
尺取り法を用いて増分のみプレゼントの取得可否を調べます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/4cf85535-2f37-de08-7eec-fac652b1e279.png" width= 45%>

**【補足】**
※1
半開区間を調べる際、前回調べた範囲から増分のみを調べたいです。
`A`が無作為に並んでいる場合は毎回、A(1)〜A(N)まで調べる必要が出てきてしまいます。
これを回避するために、A を`ソート`します。


### プログラム例
```Fortran
program abc326c
    ! N         ：直線上に置かれたプレゼントの総数
    ! M         ：半開区間
    ! A         ：直線上に置かれたプレゼントの座標
    !cnt_current：現在の区間で獲得できるプレゼントの数
    !cnt_max    ：獲得できるプレゼントの最大数
    implicit none
    integer(16) N, M
    integer(16), allocatable::A(:)
    integer(16) i, j, cnt_current, cnt_max

    !入力
    read (*, *) N, M
    allocate (A(N))
    read (*, *) A(:)
    call margesort(A, N)

    !最大値の検索
    cnt_max = 0
    j = 2
    cnt_current = 1
    do i = 1, N
        do
            if (M + A(i) > A(j) .and. j <= N) then
                cnt_current = cnt_current + 1
                j = j + 1
            else
                exit
            end if
        end do
        cnt_max = max(cnt_current, cnt_max)
        cnt_current = cnt_current - 1
    end do

    !結果の出力
    write (*, *) cnt_max
contains
    subroutine margesort(x, n)
        integer(16) N
        integer(16) x(N), tmp(N)
        integer(16) start, end
        start = 1; end = N
        call loop_margesort(x, tmp, N, start, end)
    end subroutine
    recursive subroutine loop_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 loop_margesort(x, tmp, N, left, mid)
        call loop_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 loop_margesort
end program abc326c
```


## 感想
- A：3分、B：28分でした。
- C問題は前の結果から増分だけ調べる方法で実装を試みましたが、間に合いませんでした....