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

## A - First ABC 
### 問題
A,B,Cからなる文字列Sがあります。
Sを左１文字目から順に見て、A,B,Cの全てか１回以上出現したタイミングを出力します。

>**制約**
>1. $3≤N≤100$
>2. S は A , B , C からなる長さN の文字列
>3. S は A, B, C を全て含む



詳細はこちらです。

https://atcoder.jp/contests/abc311/tasks/abc311_a

### 解説
**【フローチャート】**
入力した``S``に対して、順番にに``A,B,C``のいずれかに当てはまるかを調べます。
**全てが１回ずつ出現**している時点、結果を出力します。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/8f37c71c-3d9f-b3bc-76e4-415a7b618a70.png" width=60%>



**【補足】**
※1
``S(i:i)``に対して、順番に``A,B,C``のいずれかに当てはまるかを判定します。
当てはまる場合には、出現回数を1にします。

※2
``A,B,C``が**全て１回出現しているか**を判定します。
``Yes``の場合には、結果を出力し、プログラムを終了します。





### プログラム例
```Fortran
program ABC311a
    implicit none
    integer i
    integer N, a, b, c
    character(:), allocatable :: S

    !初期化
    a = 0; b = 0; c = 0
    N = 0; i = 0

    !入力
    read (*, *) N
    allocate (character(N)::S)
    read (*, *) S

    !A,B,Cのカウント
    do i = 1, N
        if (S(i:i) == 'A') a = 1
        if (S(i:i) == 'B') b = 1
        if (S(i:i) == 'C') c = 1
        if (a == 1 .and. b == 1 .and. c == 1) then
            write (*, *) i
            stop
        end if
    end do
end program abc311a
```


## B - Vacation Together
### 問題
1 から N までの番号がついた N 人の人がいます。
N 人の今後 D 日の予定("o" or "x")が与えられるので、最大で何日連続で予定が合うかを調べます。
>**制約**
>1. $1≤N≤100$
>2. $1≤D≤100$
>3. $S_i$ は o と x からなる長さ D の文字列

詳細はこちらです。

https://atcoder.jp/contests/abc311/tasks/abc311_b

### 解説
**【注意点】**
- 全期間で全員の予定が**1日も合わない**場合もあります。


**【フローチャート】**
１日ずつ全員の予定を調べていき、連続して空いている日数を調べます。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/9f9a6625-7c58-5a03-234b-5693cf13f6aa.png" width=75%>



**【補足】**
※1
**予定が空いている場合**(="o")に、``cnt_free``を１増やします。

※2
予定が空いている場合**(="o")にカウントを増やしているので、
``cnt_free=N``の場合は、**全員の予定が空いている**ことを意味します。

※3
**全員の予定が空いている**ため、予定が合う日数``cnt_day``を累加します。
(併せて、**予定が合う連続日数と比較**し、更新可否を判断します。)

※4
一人でも予定が空いていなければ、**予定が合うとは言えません。**
前日からの予定が合う連続日数``cnt_day``をリセットします。



### プログラム例
```Fortran
program ABC311b
    implicit none
    integer i, j, k
    integer N, D, cnt_day, cnt_free, ans
    character(1), allocatable :: S(:, :)
    !初期化
    i = 0; j = 0; k = 0; 
    N = 0; D = 0; ans = 0
    cnt_day = 0; cnt_free = 0

    !入力
    read (*, *) N, D
    allocate (S(N, D))
    do i = 1, N
        read (*, '(*(a1))') S(i, :)
    end do

    !スケジュールの確認
    do i = 1, D
        do j = 1, N
            if (S(j, i) == 'o') cnt_free = cnt_free + 1
        end do
        if (cnt_free == N) then
            cnt_day = cnt_day + 1
            if (ans < cnt_day) ans = cnt_day
        else
            cnt_day = 0
        end if
        cnt_free = 0
    end do

    !結果の出力
    write (*, *) ans
end program abc311b
```

## C - Find it!
### 問題
N 頂点 N 辺の有向グラフがあります。
i 番目の辺は頂点 i から 頂点 $A_i$ に伸びます。
同一頂点を複数回含まない有向閉路をひとつ求めます。

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


詳細はこちらです。

https://atcoder.jp/contests/abc311/tasks/abc311_c



### 解説
**【注意点】**
- 答えの組み合わせは複数あります。どの答えを選んでもACになります。
- ループの始点と終点に指定はありません。
    - 例）7 5 3 2 でも 2 7 5 3 でも良い


**【フローチャート】**
``再帰関数``を用いて、``A``がループしているかを調べます。
**メインルーチン**
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/8a7abc98-4f16-4037-7319-8ab629038d1d.png" width=40%>
**サブルーチン**
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/ab9c4ffc-4d55-a706-21db-1e1d10657c53.png" width=80%>


**【補足】**
※1
``A``のループ判定に``サブルーチン``を使用します。

※2
``A(i)``が既に2回以上出てきている(今回で３回目)かを判定します。
``A(i)``の出現が今回で３回目なら、ループを一通り記録し終え、**再度ループが繰り返され始めている**ことを意味しています。
従って、``A(i)``が**2回以上出てきている範囲をループと判定**します。

※3
**2回以上なら、ループしていると判定**するので、その時点での結果``Ans``を出力します。

※4
``A(i)``が既に1回出てきているかを判定します。
既に１回出てきている場合、今回で2回目の出現になるので、**ループの内部にいる**ことを意味します。
``A(i)``を``Ans``に代入して記録します。

※5
``A(i)``の出現回数を``check(1,i)``で管理します。

※6
``A(i)``を変え、再帰関数によって再度ループチェックを行います。






### プログラム例
```Fortran
module ABC311c_global
    implicit none
    ! グローバル変数
    integer, allocatable:: ans(:)
end module

program ABC311c
    use ABC311c_global
    implicit none
    integer(4) i, j
    integer(4) N
    integer(4), allocatable::A(:), check(:, :)

    !初期化
    i = 0; j = 0; check = 0

    !入力
    read (*, *) N
    allocate (A(N), check(2, N), ans(N))
    read (*, *) A(:)

    !ループの調査
    do i = 1, N
        call LOOP_CHECK(A, check, i, j, N)
    end do

contains
!SUB:ループしてるかチェック
    recursive subroutine LOOP_CHECK(A, check, i, j, N)
        integer(4) i, j, k, N
        integer(4) A(:), check(:, :)
        if (check(1, i) == 2) then
            write (*, '(i0)') j
            do k = 1, j
                write (*, '(1x,i0)', advance='no') A(Ans(k)) ! 改行しない
            end do
            stop
            check = 0
            return
        else
            if (check(1, i) == 1) then
                j = j + 1
                Ans(j) = i
                check(2, i) = j
            end if
            check(1, i) = check(1, i) + 1
            ! write (*, *) A(i), check(1, i), j
            i = A(i)
            call LOOP_CHECK(A, check, i, j, N)
        end if
    end subroutine
end
```


## 感想
- AtCoder全体として、ここ２回のレーティングが過剰に上振れしている気がします。A,B問題の回答だけで茶に近いパフォーマスが出ています。
- 過剰に実力が評価されることは本望ではないので、早く適正な評価に戻ってほしいです。
- A,B問題WAなしで回答できました。落ち着いて解けている....
- C問題をパッと見て解けそうになかったので、D問題に取り組みました。
    - C問題：グラフの問題は苦手なので避けましたが、後で解いてみたらすんなり解けました。
    - D問題：DFSで解けそうなのでやったみましたが、デバック中に終了。