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


## A - First Player
問題は[こちら](https://atcoder.jp/contests/abc304/tasks/abc304_a)です。
回答は以下の通りです。

出力の開始点(最年少の位置)が1人目になるとは限らないため、最年少からN番目まで単純に出力しても、全員が列挙できない可能性があります。
例えば、全体が10人で、最年少が3人目の場合、 3 ~ N まで出力すると1，2人目が出力されません。

そこで、以下の通り出力範囲を２つに分けて行いました。
    ①　最年少からN番目まで 
    ②　1番目から最年少の手前まで

```Fortran
program ABC304a
    implicit none
    integer(8) i
    integer(8) N, min_num, min_i
    character(10), allocatable :: Name(:)
    integer, allocatable:: num(:)
    !入力
    READ (*, *) N
    allocate (Name(N), num(N))

    !最年少の検索
    min_num = 1*10**9
    do i = 1, N
        read (*, *) Name(i), num(i)
        if (num(i) < min_num) then
            min_num = num(i)
            min_i = i
        end if
    end do

    !結果の表示
    do i = min_i, N
        write (*, "(a)") Name(i)
    end do
    do i = 1, min_i - 1
        write (*, "(a)") Name(i)
    end do
end
```

## B - Subscribers
問題は[こちら](https://atcoder.jp/contests/abc304/tasks/abc304_b)です。
回答は以下の通りです。

Nを10^n で割って少数点以下を切り捨てます。
その後、10^n をかければ近似値を求める事が出来ます。

また、`Nをinteger型で定義すれば、小数点以下は切り捨て`になります。
従って、割った際の四捨五入等は不要です。

```Fortran
program ABC304b
    implicit none
    integer(8) N

    !入力
    READ (*, *) N

    !Nの近似値判定
    if (N <= 10**3 - 1) then !N が 10^3 −1 以下
        write (*, "(i0)") N
        stop
    end if
    if (N >= 10**3 .and. N <= 10**4 - 1) then !N が 10^3 以上、10^4 −1 以下
        N = N/(10**1)
        N = N*(10**1)
        write (*, "(i0)") N
        stop
    end if
    if (N >= 10**4 .and. N <= 10**5 - 1) then !N が 10^4 以上、10^5 −1 以下
        N = N/(10**2)
        N = N*(10**2)
        write (*, "(i0)") N
        stop
    end if
    if (N >= 10**5 .and. N <= 10**6 - 1) then !N が 10^5 以上、10^6 −1 以下
        N = N*(10**3)
        write (*, "(i0)") N
        stop
    end if
    if (N >= 10**6 .and. N <= 10**7 - 1) then !N が 10^6 以上、10^7 −1 以下
        N = N/(10**4)
        N = N*(10**4)
        write (*, "(i0)") N
        stop
    end if
    if (N >= 10**7 .and. N <= 10**8 - 1) then !N が 10^7 以上、10^8 −1 以下
        N = N/(10**5)
        N = N*(10**5)
        write (*, "(i0)") N
        stop
    end if
    if (N >= 10**8 .and. N <= 10**9 - 1) then !N が 10^8 以上、10^9 −1 以下
        N = N/(10**6)
        N = N*(10**6)
        write (*, "(i0)") N
        stop
    end if
end
```

## C - Virus

問題は[こちら](https://atcoder.jp/contests/abc304/tasks/abc304_c)です。
回答は以下の通りです。

**連鎖する可能性のある全てのパターンを試した場合、計算量が多くTLEとなります。**
従って今回は、**DFS(深さ優先探索**)を用いて感染する範囲を調べます。

DFSは`再帰処理`で実装します。
実装例はこちらです。

https://qiita.com/onodera/items/715b516e3dbc6a467b18

ここで、各点がつながっているかどうかは、**ユークリッド距離**で調べます。
探索済み(感染済み)であれば z(i)=1 とします。


```Fortran
module mod_global
    implicit none
    ! グローバル変数
    real, save, allocatable:: x(:), y(:), z(:)
    integer N

end module mod_global

program ABC304a
    use mod_global
    implicit none
    integer i, D

    !入力
    READ (*, *) N, D
    allocate (y(N), x(N), z(N))
    do i = 1, N
        read (*, *) x(i), y(i)
    end do
    z = 0

    !感染判定
    z(1) = 1
    do i = 2, N
        call DFS(1, i)
    end do

    !結果の出力
    do i = 1, N
        if (z(i) == 1) then
            write (*, "(a)") 'Yes'
        else
            write (*, "(a)") 'No'
        end if
    end do
contains
    !深さ優先探索
    recursive subroutine DFS(i, j)
        integer i, j, k
        real kyori
        kyori = sqrt((x(i) - x(j))**2 + (y(i) - y(j))**2)
        if (kyori <= D) then
            z(j) = 1
            do k = 2, N
                if (z(k) == 0) call DFS(j, k)
            end do
        end if
    end subroutine
end

```

## 余談
- Fortranで再帰処理を書く場合には、頭にrecursiveを付ける必要がある
    - 例1 ）recursive subroutine
    - 例2 ）recursive function
<details><summary> 感想</summary><div>

- 今回はついにB問題まで解く事が出来た。(問題が優しすぎた気がする)
- C問題は解き方は分かったが、実装する時間が足りなくて終了。
</div></details>