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

## A - Chord 
### 問題
英大文字からなる長さ3の文字列 S が与えられます。
Sが`ACE、BDF、CEG、DFA、EGB、FAC、GBD` のいずれかと等しいとき `Yes` を、そうでないとき `No` を出力します。


>**制約**
>1. $S$は英大文字からなる長さ 3 の文字列

詳細はこちらです。

https://atcoder.jp/contests/abc312/tasks/abc312_a


### 解説
**【フローチャート】**
入力した``S``に対して、順番に`ACE、BDF、CEG、DFA、EGB、FAC、GBD `のいずれかに当てはまるかを調べます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/b4dc9729-1062-8cb3-f5d7-4082096cca57.png" width=60%>

**【補足】**
※1
``S``に対して、順番に`ACE、BDF、CEG、DFA、EGB、FAC、GBD `のいずれかに当てはまるかを判定します。
当てはまる文字列が見つかった時点で`Yes`を出力し、プログラムを終了します。


### プログラム例
```Fortran
program ABC312a
    implicit none
    character(3) :: S

    !入力
    read (*, *) S

    !判定
    if (S == 'ACE') then
        write (*, *) 'Yes'
        stop
    end if
    if (S == 'BDF') then
        write (*, *) 'Yes'
        stop
    end if
    if (S == 'CEG') then
        write (*, *) 'Yes'
        stop
    end if
    if (S == 'DFA') then
        write (*, *) 'Yes'
        stop
    end if
    if (S == 'EGB') then
        write (*, *) 'Yes'
        stop
    end if
    if (S == 'FAC') then
        write (*, *) 'Yes'
        stop
    end if
    if (S == 'GBD') then
        write (*, *) 'Yes'
        stop
    end if
    write (*, *) 'No'
end program abc312a
```



## B - TaK Code
### 問題
縦 N マス、横 M マスのグリッドが、以下の条件に当てはまる場合は `Yes`,そうでない場合は `No` を出力します。

>**条件(TaK Code)**
>1. 縦 9 マス 横 9 マスの領域である
>2. 左上及び右下の縦 3 マス、横 3 マスの領域に含まれる計 18 マスは全て黒である
>3. 左上及び右下の縦 3 マス、横 3 マスの領域に八方位で隣接する計 14 マスは全て白である

>**制約**
>1. $9≤N,M≤100$
>2. N,M は整数である
>3. $S_i$は `.` および `#` のみからなる長さ M の文字列である

詳細はこちらです。

https://atcoder.jp/contests/abc312/tasks/abc312_b


### 解説
**【フローチャート】**
１マスずつ起点とする位置をずらしながら、 TaK Code　が成立するエリアがあるかを調べます。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/22e7778d-598c-0016-3a5d-a7e84ed870cd.png" width=35%>



**【補足】**
※1
**TaK Codeの条件2**を満たしているかの判定を行います。
判定は`any関数`を使用します。
`any関数`は複数の変数を一括して判定にかけることができ、1つでも当てはまらない変数がある場合には`No`となります。
`No`となった場合にはTaK Codeの**不成立が確定**するので、`cycle文`で次のループへ進みます。


※2
TaK Codeの条件3を満たしているかの判定を行います。
判定は`any関数`を使用します。
`No`となった場合にはTaK Codeの**不成立が確定**するので、`cycle文`で次のループへ進みます。

※3
ここまでの判定で条件1~3を満たしているため、TaK Codeが成立しており、成立ケース`(i,j)`の出力を行います。
`(i,j)` の組は**辞書順の昇順**に出力する必要がありますが、本フローチャートでは(1,1)から随時成立ケースを検証、出力することになるため、並び替えは不要となります。


### プログラム例
```Fortran
program ABC312b
    implicit none
    integer i, j
    integer N, M
    character(1), allocatable::  S(:, :)

    !初期化
    i = 0; j = 0
    N = 0; M = 0
    !入力
    read (*, *) N, M
    allocate (S(N, M))
    do i = 1, N
        read (*, '(*(a1))') (S(i, j), j=1, M)
    end do

    !判定
    do i = 1, N
        do j = 1, M
            !黒マス判定
            if (any(S(i:i + 2, j:j + 2) /= '#')) cycle
            if (any(S(i + 6:i + 8, j + 6:j + 8) /= '#')) cycle
            !シロマス判定
            !縦
            if (any(S(i:i + 2, j + 3) /= '.')) cycle
            if (any(S(i + 6:i + 8, j + 5) /= '.')) cycle
            !横
            if (any(S(i + 3, j:j + 3) /= '.')) cycle
            if (any(S(i + 5, j + 5:j + 8) /= '.')) cycle
            !結果の出力(随時)
            write (*, '(i0,1x,i0)') i, j
        end do
    end do
end program abc312b
```


## C - Invisible Hand
### 問題
りんご市場に N 人の売り手と M 人の買い手がいます。
りんごを X 円で売ってもよいと考える売り手の人数が、りんごを X 円で買ってもよいと考える買い手の人数以上である最小の金額を調べます。

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

詳細はこちらです。

https://atcoder.jp/contests/abc312/tasks/abc312_c


### 解説
**【注意点】**
- $1≤A_i,B_i≤10^9$であるため、1円ずつ条件の成立を調べていくと`TLE`となってしまいます。

**【フローチャート】**
条件の成立、不成立の変化は$A_i$と$B_i+1$円で発生するため、調べる範囲を絞ってプログラムを回します。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/053d0e4c-538b-cfac-a5e8-c04930dd73e2.png" width=80%>

**【補足】**
※1
条件の成立、不成立の変化は$A_i$と$B_i+1$円で発生するため、入力した`A,B`から売買の成立判定に使う読み出し順`events`を作成します。


※2
売買の成立する最小金額を知りたいので、読み出し順`events`をソートします。
ソートには`クイックソート`を使用します。

※3
`events`を順番に読み込み、売り買いの人数を増減させます。

※4
売買の成立判定を行います。
**売り手の人数 >= 買い手の人数**　であれば売買の成立となります。
売買が成立している場合には、結果`events(i)`を出力し、プログラムを終了します。



### プログラム例
```Fortran
program ABC312c
    implicit none
    integer(8) i, j, cnt_A, cnt_B, start
    integer(8) N, M
    integer(8), allocatable::  A(:), B(:), events(:)
    character(1), allocatable::events_AB(:)

    !初期化
    i = 0; j = 0

    !入力
    read (*, *) N, M
    allocate (A(N), B(M))
    allocate (events_AB(N + M), events(N + M))
    read (*, *) A(:)
    read (*, *) B(:)

    !読み出し順の作成
    B = B + 1
    events(1:N) = A; events(N + 1:M) = B
    events_AB = 'B'; events_AB(1:N) = 'A'
    start = 1
    call quicksort(events, events_AB, start, N + M)

    !判定
    cnt_A = 0; cnt_B = M
    do i = 1, N + M
        if (events_AB(i) == 'A') then
            cnt_A = cnt_A + 1
        else
            cnt_B = cnt_B - 1
        end if
        if (cnt_A >= cnt_B) then
            write (*, '(i0)') events(i)
            stop
        end if
    end do

contains
!sub:クイックソート
    recursive subroutine quicksort(a, b, first, last)
        implicit none
        integer(8) a(:), i, j, t
        character(1) b(:), t2
        integer(8) first, last, center

        i = first
        j = last

        center = a(int((first + last)/2))
        do
            do while (a(i) < center)
                i = i + 1
            end do

            do while (center < a(j))
                j = j - 1
            end do

            if (i > j) then
                exit
            else if (i == j) then
                exit
            end if

            t = a(i); a(i) = a(j); a(j) = t
            t2 = b(i); b(i) = b(j); b(j) = t2
            i = i + 1
            j = j - 1
        end do
        if (first < i - 1) call quicksort(a, b, first, i - 1)
        if (j + 1 < last) call quicksort(a, b, j + 1, last)
    end subroutine quicksort
end program abc312c
```


## 感想

- A,B問題WAなしで回答できました。良い。 
- 残りの時間でC問題を解いていたら終わりました。
- (時間が確保できず、記事更新が大幅に遅れてしまいました....。みなさんはどうやって時間を確保しているのでしょうか。)