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

## 目次
  - [A - Same](#a---same)
  - [B - 3-smooth Numbers](#b---3-smooth-numbers)
  - [C - Error Correction](#c---error-correction)


## A - Same
### 問題
N 個の整数 $A_1,A_2,…,A_N$ が与えられます。
これらの値がすべて等しいならば `Yes` 、そうでなければ `No` と出力してください。

>**制約**
>1. $2≤N≤100$
>2. $1≤A_i≤100 (1≤i≤N)$
>3. 入力はすべて整数

詳細はこちらです。

https://atcoder.jp/contests/abc324/tasks/abc324_a


### 解説
**【フローチャート】**
1 文字目から順番に一致するか調べます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/296120c4-125c-8885-cff5-956abea221c1.png" width=60%>

**【補足】**
※1
A(i)とA(i+1)が一致するかを調べます。


### プログラム例
```Fortran
program abc324a
    ! A(N)：整数A1,A2,...AN
    ! N   ：整数の個数
    implicit none
    integer N, i
    integer, allocatable::A(:)

    !入力
    read (*, *) N
    allocate (A(N))
    read (*, *) A
    
    !判定
    do i = 1, N - 1
        if (A(i) == A(i + 1)) then
            cycle
        else
            write (*, '(a)') 'No'
            stop
        end if
    end do
    write (*, '(a)') 'Yes'
end program abc324a
```



## B - 3-smooth Numbers
:::note warn
警告
ACとなっている回答ですが、解法として非効率な部分があります。
:::
### 問題
正の整数 N が与えられます。 
$N=2^x3^y$ を満たす整数 x,y が存在するなら `Yes` 、そうでなければ `No` と出力してください。

>**制約**
>1. $1≤N≤10^{18}$
>2. N は整数

詳細はこちらです。

https://atcoder.jp/contests/abc324/tasks/abc324_b


### 解説
**【フローチャート】**
$2^x3^y = N$ となるまで、x と y 総当たりで変化させて調べます。 

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/5167e44d-1b90-5520-ab87-499d2652e25f.png" width= 60%>

**【補足】**
※1
**x の値を固定し、yの値を変化させ $2^x3^y = N$ が成立するかを調べます。**
例えば、 x = 1 で固定をし、 y=1,2,3,4,... と変化させます。
x,y は $2^x3^y > N$ となるまで調べます。

※2
x,y は値を増やす形で $2^x3^y = N$ が成立するかを調べています。
x= i , y = 0 の時点で $2^x3^y$ が N を超える場合、これ以上値を増やしても $2^x3^y$ が N を下回ることはありません。
これ以上は $2^x3^y = N$ の成立を調べる必要はないので、ループを終了します。

※3
x,y は値を増やす形で $2^x3^y = N$ が成立するかを調べています。
$2^x3^y$ が N 以上となる場合、これ以上値を増やしても $2^x3^y$ が N を下回ることはありません。
これ以上は $2^x3^y = N$ の成立を調べる必要はないので、ループを終了します。

※4
※3の分岐では $2^x3^y = N$ と $2^x3^y > N$ のどちらかの可能性があります。
$2^x3^y = N$となっている場合、ループを終了します。

※5
$2^x3^y = N$となっている場合、結果を出力します。

※6
**y の値を固定し、yの値を変化させ $2^x3^y = N$ が成立するかを調べます。**
例えば、 y = 1 で固定をし、 x=1,2,3,4,... と変化させます。
x,y は $2^x3^y > N$ となるまで調べます。

### プログラム例

```Fortran
program abc324b
    !N    ：作りたい目的の整数
    !xa,ya：2**x,3**y
    !ans  ：xa+ya
    implicit none
    integer(8) N
    integer(8) x, y, ans, xa, ya

    !入力
    read (*, *) N
    x = 0; y = 0
    if (N == 1) then
        write (*, '(a)') 'Yes'
        stop
    end if

    !x基準
    xloop: do
        !初期値
        x = x + 1; y = 1
        !xの値更新
        xa = 2**x
        ans = xa
        if (xa >= N) exit xloop
        !yの値更新
        yloop: do
            ans = xa*(3**y)
            if (ans >= N) exit yloop
            y = y + 1
        end do yloop
        if (ans == N) exit
    end do xloop

    !結果の出力
    if (ans == N) then
        write (*, '(a)') 'Yes'
        stop
    end if

    !y基準
    x = 0; y = 0
    y2loop: do
        !初期値
        y = y + 1; x = 1
        !yの値更新
        ya = 3**y
        ans = ya
        if (ya >= N) exit y2loop
        !xの値更新
        x2loop: do
            ans = ya*(2**x)
            if (ans >= N) exit x2loop
            x = x + 1
        end do x2loop
        if (ans == N) exit
    end do y2loop

    !結果の出力
    if (ans == N) then
        write (*, '(a)') 'Yes'
    else
        write (*, '(a)') 'No'
    end if
end program abc324b
```



## C - Error Correction
### 問題
送信した文字列 Tと受信した文字列 S があります。
文字列 S は文字列 T から変化している部分があります。

変更されている箇所は下記の４つの条件のどれかに当てはまる場合、T = S(i) とすることができます。
受信した文字列のうち、どれが T と一致している可能性があるかを調べます。　

>**条件**
>1. T は、S(i) と完全に等しい。
>2. T は、S(i) のいずれか 1 つの位置に英小文字を 1 つ挿入して得られる文字列である。
>3. T は、S(i） からある 1 文字を削除して得られる文字列である
>4. T  は、S(i) のある 1 文字を別の英小文字に変更して得られる文字列である。

>**制約**
>1. N は整数
>2. $1≤N≤5×10^5$
>3. $S_i$ と $T′$ は英小文字からなる長さ 1 以上 $5×10^5$ 以下の文字列
>4. $S_1,S_2,…,S_N$ の長さの総和は $5×10^5$ 以下

詳細はこちらです。

https://atcoder.jp/contests/abc324/tasks/abc324_c


### 解説
**【フローチャート】**
**許容できる文字列の長さの差は、最大で１文字です。**
N と T の文字列の長さの差が 1 を超えない場合のみ、文字列の一致について検証します。

N と T の文字列の一致を調べる場合は、**文字列の長さの差に応じて、調べる条件を変化させます。**

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/392f4403-2d9d-5d65-3278-4a8e5fe6a58b.png" width= 80%>


**【補足】**
※1
$N=5×10^5、Sの長さ=5×10^5$の場合、1つの配列で　S　を定義すると、`character(500000) S(500000)`となり、
配列サイズが大きくメモリが確保できずエラーとなります。
対策として、入力を1文字づつ変数cに読み込み、`S(i:i)`に代入していきます。

※2
T と　S の文字列の長さを左を調べ、左に応じて調べる条件を変化させます。
文字列の差が 1 を超える場合には、どの条件にも合致しませんので、次のループに進みます。

※3
※2で調べた結果に応じて、T と S(j) が一致するかを判定します。
判定用の`変数tf` が**1 なら一致、0　なら不一致**と判定します。

※4
　T と S(j) が一致する場合、その位置と累計回数を記録します。


### プログラム例
```Fortran
module global_abc324c
    !cnt   ：SとTが一致している数
    !tf    ：SとTが一致するかの判定用(1なら一致,0なら不一致)
    !ans(N)：SとTが一致するかを記録(1なら一致,0なら不一致)
    implicit none
    integer(8) cnt, tf
    integer(8), allocatable ::ans(:)
end module
program abc324c
    !T    ：送信した文字列
    !N    ：受信した文字列の数
    !S(N) ：受信した文字列
    !c    ：入力用文字列(1文字分)
    !tl,sl：TとSの文字の長さ
    use global_abc324c
    implicit none
    character(500000) T, S
    character(1) c
    integer(16) N
    integer(16) i, j, tl, sl

    read (*, *) N, T
    allocate (ans(N))
    cnt = 0; ans = 0; i = 1
    tl = len_trim(T)
    do j = 1, N
        !入力
        S(1:i) = ' '
        i = 1
        do
            read (*, '(a1)', advance="no") c
            if (c == " ") exit
            S(i:i) = c
            i = i + 1
        end do

        !T = T'一致判定
        sl = i - 1
        if (abs(sl - tl) > 1) cycle
        select case (sl - tl)
        case (1)
            call check2(S(1:sl), T(1:tl), sl, tl)
        case (-1)
            call check3(S(1:sl), T(1:tl), sl, tl)
        case (0)
            call check4(S(1:sl), T(1:tl), sl, tl)
        end select
        if (tf == 1) then
            cnt = cnt + 1
            ans(j) = 1
        end if
    end do

    !結果の出力
    write (*, '(i0)') cnt
    do i = 1, N
        if (ans(i) == 1) write (*, '(i0,1x)', advance='no') i
    end do
contains
    !条件2：Sに１文字挿入されている
    subroutine check2(S, T, sl, tl)
        !T    ：送信した文字列
        !S    ：受信した文字列
        !miss：文字が不一致の回数
        !tl,sl：TとSの文字の長さ
        integer(16) sl, tl, i, j, miss
        character(sl + 1) S
        character(tl + 1) T
        i = 1; j = 1; tf = 0; miss = 0
        do
            if (T(i:i) == S(j:j)) then
                i = i + 1
                j = j + 1
            else
                j = j + 1
                miss = miss + 1
                if (miss > 1) return
            end if
            if (i == tl + 1 .or. j == sl + 1) exit
        end do
        tf = 1
    end subroutine check2

    !条件3：Sが１文字削除されている
    subroutine check3(S, T, sl, tl)
        !T    ：送信した文字列
        !S    ：受信した文字列
        !miss：文字が不一致の回数
        !tl,sl：TとSの文字の長さ
        integer(16) sl, tl, i, j, miss
        character(sl + 1) S
        character(tl + 1) T
        i = 1; j = 1; tf = 0; miss = 0
        do
            if (T(i:i) == S(j:j)) then
                i = i + 1
                j = j + 1
            else
                i = i + 1
                miss = miss + 1
                if (miss > 1) return
            end if
            if (i == tl + 1 .or. j == sl + 1) exit
        end do
        tf = 1
    end subroutine check3

    !条件4：SとTが完全一致
    subroutine check4(S, T, sl, tl)
        !T    ：送信した文字列
        !S    ：受信した文字列
        !miss：文字が不一致の回数
        !tl,sl：TとSの文字の長さ
        integer(16) sl, tl, i, j, miss
        character(sl + 1) S
        character(tl + 1) T
        i = 1; j = 1; tf = 0; miss = 0
        do i = 1, tl
            if (T(i:i) /= S(i:i)) then
                miss = miss + 1
                if (miss > 1) return
            else
            end if
        end do
        tf = 1
    end subroutine check4
end
```


## 感想
- C問題について、コンテスト終了後に @ osada-yum(yum osada) 様に多くのアドバイスをいただきました。
アドバイスがなければACにはなっていなかったと思います。この場を借りてお礼申し上げます。