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

## 目次
  - [A - ab](#a---ab)
  - [B - A^A](#b---aa)
  - [C - Number Place](#c---number-place)


## A - ab
### 問題
英小文字からなる長さ N の文字列 S が与えられます。
S の中で `a` と `b` が隣接する箇所があれば `Yes` を、なければ `No` を出力します。

>**制約**
>1.$2≤N≤100$
>2. S は英小文字からなる長さ N の文字列

詳細はこちらです。

https://atcoder.jp/contests/abc327/tasks/abc327_a


### 解説
**【フローチャート】**
文字列 S　を2文字ずつ**総当たり**で調べ、abの隣接を調べます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/dfb19969-1b4c-fdd0-cd7c-24be1e838a2d.png" width= 70%>

**【補足】**
※1
S を i に応じて２文字ずつ取り出し、a と b の隣接判定を行います。
a と b が隣接するパターンは、**ab** と **ba** が考えられます。
判定には`if文`を用い、`S(i:i+1)== 'ab'`もしくは  `S(i:i+1)== 'ba'`が成立するかを判定します。

### プログラム例
```Fortran
program abc327a
    !N：文字列の長さ
    !S：文字列
    implicit none
    integer(16) N, i
    character(:), allocatable :: S

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

    !隣接判定
    do i = 1, N - 1
        if (S(i:i + 1) == 'ab' .or. S(i:i + 1) == 'ba') then
            write (*, '(a)') 'Yes'
            stop
        end if
    end do

    !結果の出力
    write (*, '(a)') 'No'
end program abc327a
```



## B - A^A
### 問題
整数 B が与えられます。
$A^A=B$ が成立する正の整数が存在する場合はその値を、存在しない場合は `-1` を出力します。


>**制約**
>1. $1≤B≤10^18$
>2. B は整数

詳細はこちらです。

https://atcoder.jp/contests/abc327/tasks/abc327_b


### 解説
**【フローチャート】**
$A^A=B$ が成立する正の整数を総当たりで調べます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/75934fd0-98b6-1c94-7b63-95c87d1d87e0.png" width=65%>

**【補足】**
※1
$A^A > B$となった場合、以降は A どれだけを増加させても　$A^A > B$から変化することはありません。
$A^A=B$となることはないため、ループを終了させます。


### プログラム例
```Fortran
program abc327b
    !B：整数
    !ans：a**a
    implicit none
    integer(16) B, ans, a

    !入力
    read (*, *) B

    !判定
    do a = 1, B
        ans = a**a
        if (ans == B) then
            write (*, '(i0)') a
            stop
        elseif (ans > B) then
            exit
        end if

    end do
    write (*, '(i0)') - 1
end program abc327b
```



## C - Number Place
### 問題
9×9 のマス目 A があります。
各マスには 1 以上 9 以下の整数が書き込まれています。

A が以下の3つの条件を全て満たす場合は `Yes` を、そうでないならば `No` を出力します。

>**条件**
>1. A の各行の９マスに 1 〜 9 の整数が 1 回ずつ書き込まれている。
>2. A の各列の９マスに 1 〜 9 の整数が 1 回ずつ書き込まれている。
>3. Aを上から３行、左から３列にずつ分け、3×3 のマス目に作った際、各マスに 1 〜 9 の整数が 1 回ずつ書き込まれている。

>**制約**
>1. $1≤A_{i,j} ≤9$
>2. 入力はすべて整数

詳細はこちらです。

https://atcoder.jp/contests/abc327/tasks/abc327_c


### 解説
**【フローチャート】**
Aの各行、各列で １~9 が1回ずつ使用されている場合は、ソートした結果が 1 から順番に 1 ずつ増減しているはずです。
あらかじめ `1,2,3,4,5,6,7,8,9`の配列を別で用意しておき、Aをソートした結果と比較して条件の成立を確認します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/ef7c8a71-6ead-41e9-8810-2299d8135a73.png" width= 80%>


**【補足】**
※1
9×9 のマスから各条件に沿って数字を取り出します。
取り出した結果を昇順に並び替えます。

※2
※1で昇順に並び替えた結果が条件1,2,3を満たすかを判定します。
条件1,2,3を満たしていれば、ソートした結果が 1 から順番に 1 ずつ増減しています。



### プログラム例
```Fortran
program abc327c
    !A        ：9x9のマス目
    !A_yoko   ：Aのi行目(長さ9)
    !A_tate   ：Aのi列目(長さ9)
    !A_box    ：Aから3x3を抽出し、一列に並べた形
    !check_arr：条件1~3の判定用(1~9が連番で格納されてる)
    integer(16) A(9, 9)
    integer(16) A_yoko(9, 9), A_tate(9, 9), A_box(9), check_arr(9)
    integer(16) i, n

    !入力
    do i = 1, 9
        read (*, *) A(i, :)
    end do
    read (*, *) A(i, :)
    n = 9
    data check_arr/1, 2, 3, 4, 5, 6, 7, 8, 9/

    !条件1
    A_yoko = A
    do i = 1, 9
        call margesort(A_yoko(i, :), n)
        if (any(check_arr /= A_yoko(i, 1:9))) then
            write (*, '(a)') 'No'
            stop
        end if
    end do

    !条件2
    A_tate = A
    do i = 1, 9
        call margesort(A_tate(:, i), n)
        if (any(check_arr /= A_tate(1:9, i))) then
            write (*, '(a)') 'No'
            stop
        end if
    end do

    !条件3
    do j = 1, 9, 3
        do i = 1, 9, 3
            A_box(1:3) = A(j, i:i + 2)
            A_box(4:6) = A(j + 1, i:i + 2)
            A_box(7:9) = A(j + 2, i:i + 2)
            call margesort(A_box, n)
            if (any(check_arr /= A_box)) then
                write (*, '(a)') 'No'
                stop
            end if
        end do
    end do

    !結果の出力
    write (*, '(a)') 'Yes'
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 abc327c
```


## 感想
- A：5分、B：10分、C：46分でした。