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

## A - Potions
### 問題
**体力 H** のモンスターに対して**傷薬 P** を与え、**体力を X 以上にしたいです。**
傷薬は N 種類あり、効き目の弱い順に 1 から N までの番号がついています。

モンスターの体力が X 以上になる、**最小の傷薬**を探します。

>**制約**
>1. $2≤N≤100$
>2. $1≤H<X≤999$
>3. $1≤P_1<P_2<⋯<P_N=999$
>4. 入力される値はすべて整数

詳細はこちらです。

https://atcoder.jp/contests/abc317/tasks/abc317_a


### 解説
**【フローチャート】**
薬を**1から昇順**に使い、モンスターの体力が X 以上になる最小の種類を探します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/c2cab89f-8e64-b7af-47c3-2ed1a57d4606.png" width=70%>

**【補足】**
※1
薬を与えた後のモンスターの体力``Ans``が ``X``以上であるかを調べます。
 ``X``以上の場合、薬の種類``i``を出力します。


### プログラム例
```Fortran
program ABC317a
    implicit none
    integer i, Ans, N, H, X
    integer, allocatable :: P(:)

    !入力
    read (*, *) N, H, X
    allocate (P(N))
    read (*, *) P(:)

    !判定
    do i = 1, N
        Ans = H + P(i)
        if (Ans >= X) then
            write (*, '(i0)') i
            stop
        end if
    end do
end program abc317a
```



## B - MissingNo.
### 問題
N+1 個の連続する整数 $A_1,A_2,...A_N$ を 1 個ずつ持っていましたが、そのうち 1 個をなくしてしまいました。なくした整数を求めてください。

>**制約**
>1. $2≤N≤100$
>2. $1≤A_i≤1000$
>3. 入力は全て整数である
>4. なくした整数は一意に定まる

詳細はこちらです。

https://atcoder.jp/contests/abc317/tasks/abc317_b


### 解説
**【フローチャート】**
**$A_1,A_2,...A_N$** をソートし、順番に$A_1$から順に連続して並んでいるかを調べます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/de05b8ae-5b5f-e6dd-5fd5-1da1dd2e4fa0.png" width=75%>

**【補足】**
※1
入力した**$A_1,A_2,...A_N$**を降順に並び替えます。
並び替えには``マージソート``を使用します。

※2
隣り合う数$A_iとA_{i+1}$が連続しているかについて、$A_i-A_{i+1}$で差を求めることで確かめます。
連続する整数であれば、**差が1**になり、連続する整数でなければ、**差が1以上**になっています。


### プログラム例
```Fortran
program ABC317b
    implicit none
    integer N, i
    integer, allocatable ::  A(:), tmp(:)

    !入力
    read (*, *) N
    allocate (A(N), tmp(N))
    read (*, *) A(:)

    !Aを昇順にソート
    call margesort(A, tmp, N, 1, N)

    !不連続部分を調べる
    do i = 1, N
        if (A(i) - A(i + 1) > 1) then
            write (*, '(i0)') A(i) - 1
            stop
        end if
    end do
contains
    recursive subroutine margesort(x, tmp, N, left, right)
        integer left, right, mid
        integer N
        integer x(N), tmp(N)
        integer 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 abc317b
```



## C - Remembering the Days
### 問題
1 から N の番号がついた N 個の街と、1 から M の番号がついた M 本の道路があります。
i 番目の道路は街 $A_i$と街 $B_i$ を双方向に結び、長さは $C_i$ です。

好きな街からスタートして**同じ街を二度以上通らず**に別の街へ移動するときの、通る道路の長さの和としてありえる最大値を求めてください。

>**制約**
>1. $2≤N≤10$
>2. $1≤M≤N(N−1)/2$
>3. $1≤A_i<B_i≤N$
>4. (A_i,B_i) は相異なる
>5. $1≤C_i≤10^8$
>6. 入力は全て整数である

詳細はこちらです。

https://atcoder.jp/contests/abc317/tasks/abc317_c


### 解説
**【注意点】**
- $N=10$の時$M=45$であるため、繋がっていない道を含め総当たりでを調べると、**TLE**となってしまします。

**【フローチャート】**
DFSを使って**接続されている**道の組み合わせを全て試し、最大値を求めます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/cba24734-78bd-2113-232d-8e5700686938.png" width=50%>

**【補足】**
※1
``DFS``を用いて接続している道を探し、通る道路の長さの和を求めます。
併せて、通る道路の長さの最大値を随時更新していきます。

始めに通る道の進行方向はA(i)とB(i)の２通りあることに注意が必要です。
最大値の更新には``MAX関数``を使用します。

DFSの実装には再帰処理を用いた``subroutine``を使用します。
再帰処理は、``subroutine``の前に``recursive``を入れること実装できます。


### プログラム例
```Fortran
module ABC317c_mod
    implicit none
    ! グローバル変数
    integer(16), allocatable :: A(:), B(:), C(:)
    integer(16) distance_max, M, N
end module

program ABC317c
    use ABC317c_mod
    implicit none
    integer(16) i, distance
    integer(16), allocatable ::  visited(:)

    !入力
    read (*, *) N, M
    allocate (A(M), B(M), C(M), visited(N))
    do i = 1, M
        read (*, *) A(i), B(i), C(i)
    end do

    !DFS
    distance_max = 0
    do i = 1, M
        distance = 0; visited = 0; visited(A(i)) = 1
        call move(B(i), i, distance, visited)
        distance = 0; visited = 0; visited(B(i)) = 1
        call move(A(i), i, distance, visited)
    end do
    write (*, '(i0)') distance_max

contains

    !深さ優先探索
    recursive subroutine move(current, route, distance, visited)
        implicit none
        integer(16) current, route, distance, visited(N)
        integer(16) i, tmp(N), tmp2

        !移動先が訪問済かどうか
        visited(current) = 1
        distance = distance + C(route)
        distance_max = max(distance_max, distance)

        !次の訪問先を調べる
        do i = 1, M
            if (current == A(i) .and. visited(B(i)) == 0) then
                tmp = visited; tmp2 = distance
                call move(B(i), i, distance, visited)
                visited = tmp; distance = tmp2
            end if
            if (current == B(i) .and. visited(A(i)) == 0) then
                tmp = visited; tmp2 = distance
                call move(A(i), i, distance, visited)
                visited = tmp; distance = tmp2
            end if
        end do
    end subroutine
end program abc317c
```


## 感想
- C問題のDFSを書くのにかなり苦労しました。それぞれの問題の条件に落とし込んで実装するのがどうも上手くいきません...
- ABC316は公式でスキップされているのでありません。