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


## A - Attack
問題は[こちら](https://atcoder.jp/contests/abc302/tasks/abc302_a)です。
回答は以下の通りです。

:::note alert
注意：以下の解法で求めるよりも、体力Aを１回の攻撃ダメージ数Bで割ることで、
　　　最小の攻撃回数は簡単に求められます。

:::

`１回攻撃のダメージ数Bを累乗し`、体力Aが0未満となる攻撃回数を探します。
そこから体力Aが０にできる範囲を`半分ずづ絞っていき`、最小で０以下にできる攻撃回数を探しています。


```fortran
program ABC302a
    implicit none
    integer(16) i, A, B, j, cnt_mae, cnt_usiro, Ans, hantei, sa
    !入力
    READ (*, *) A, B

    !確認
    i = 0
    Ans = 0
    do
        i = i + 1
        Ans = A - B**i
        if (Ans <= 0) then
            cnt_mae = (B**(i - 1))
            cnt_usiro = (B**i)
            do
                hantei = cnt_mae + cnt_usiro
                !write (*, *) (cnt_mae + cnt_usiro)/2
                hantei = hantei/2
                if (A >= hantei) then
                    cnt_mae = hantei
                else
                    cnt_usiro = hantei
                end if
                !write (*, *) cnt_mae, '<', A, '<', cnt_usiro
                sa = cnt_usiro - cnt_mae
                if (sa <= B) then
                    if (cnt_mae == A) then
                        write (*, *) cnt_mae/B
                    else
                        write (*, *) cnt_mae/B + 1
                    end if
                    stop
                end if
            end do
        end if
    end do
end program
```

## B - Find snuke
問題は[こちら](https://atcoder.jp/contests/abc302/tasks/abc302_b)です。
回答は以下の通りです。

初めに`全てのマス`を調べ,`１文字目：s`を探します。

`１文字目：s`が見つかった場合には、`周囲の８マス`を調べ、`２文字目：n`を探します。

ここまで調べると、`縦・横・ななめ`のどの方向にsnukeの文字が続いているか分かります。
従って、３文字目以降(u~e)は`２文字目の方向に沿って探索を続け`、snukeが存在するかを調べます。

プログラムでは、do文を使って、１文字目→２文字→３文字目以降と範囲を絞って検索しています。

２文字目では、周囲８マスではなく中心も含めた９マス調べていますが、中心の文字はsであり、nになることは絶対にないので問題ありません。

補足：処理的には無駄に１マス調べているため、遅くなると思います。
　　　ですが9マス調べる方針にするとdo文で書けて分かりやすいので今回はこの方法をとっています。

```fortran
program ABC302b
    implicit none
    integer i, j, H, W, k, l, m, n
    integer Ans(5, 2)
    character(:), allocatable :: S(:) !配列数がn、n文字入る
    character(5) ::snuke = "snuke"

    Ans = 0
    !入力
    READ (*, *) H, W
    allocate (character(W) :: S(H))
    READ (*, *) S

    !SNUKE検索
    do i = 1, H
        do j = 1, W
            !sがあるか
            if (S(i) (j:j) == snuke(1:1)) then
                Ans(1, 1) = i
                Ans(1, 2) = j
                !sの周囲８マスにnがあるか
                do k = -1, 1
                    do l = -1, 1
                        if (S(i + k) (j + l:j + l) == snuke(2:2)) then
                            if (i + 4*k > H .or. j + 4*l > W &
                                .or. i + 4*k < 1 .or. j + 4*l < 1) cycle
                            Ans(2, 1) = i + k
                            Ans(2, 2) = j + l
                            do m = 2, 4
                                if (S(i + m*k) (j + m*l:j + m*l) == snuke(m + 1:m + 1)) then
                                    Ans(1 + m, 1) = i + m*k
                                    Ans(1 + m, 2) = j + m*l
                                else
                                    exit
                                end if
                            end do
                            if (Ans(5, 2) /= 0) then
                                do n = 1, 5
                                    write (*, '(i0, 1x, i0)') ans(n, 1), ans(n, 2)
                                end do
                                stop
                            end if
                        end if
                    end do
                end do
            end if
        end do
    end do
end

```
## C - Almost Equal
問題は[こちら](https://atcoder.jp/contests/abc302/tasks/abc302_c)です。
回答は以下の通りです。

入力した文字列に１から番号を振って数列を作り、その数列の全ての順列を試して、条件が成立しているか調べます。
例えば、「bbed、abcd、abed、fbed」なら、
　1：bbed
　2：abcd
　3：abed
　4：fbed
と番号をふって、数列1234の順列を
　1234
　1243
　1432
　4231 ...
と順番に変えていき、条件が成立しているかを毎回調べていきます。

文字列に振る番号は、配列に格納した順番としました。
順列の順番(文字列の呼び出し順)については、別で配列を用意し、そこで管理しました。

問題はここからで、条件の成立をくまなく調べるために、`全ての順列を用意する必要があります。`

C++やPythonでは`next_permutation`や`itertools.permutations`で全ての順列を取り出すことができますが、Fortranにはその様な機能はありません。

そこで今回はnext_permutationを参考に、[自分で順列を吐き出すサブルーチンを作りました。](https://qiita.com/onodera/items/6d72c40cf2a1777256e4)

順列が無事に取り出せれば、中身をdo文で全て調べれば完了です。

```fortran
program ABC302c
    implicit none
    logical check
    integer N, M, i, j, diff, k
    character(:), allocatable :: S(:)
    integer, allocatable :: S_order(:)
    !入力
    READ (*, *) N, M
    allocate (character(M) :: S(N))
    allocate (S_order(N), source=[(i, i=1, n)])

    READ (*, *) S
    do k = 1, gamma(dble(N + 1))
        diff = 0
        check = .true.
        do i = 1, N - 1
            do j = 1, M
                if (S(S_order(i)) (j:j) /= S(S_order(i + 1)) (j:j)) diff = diff + 1
            end do
            if (diff > 1) then
                check = .false.
                exit
            else
                !write (*, *) 'S_order = (', S_order, ' )', S(S_order(i)), ' > ', S(S_order(i + 1)), i + 1
            end if
            diff = 0
        end do
        if (check .eqv. .true.) then
            write (*, '(a)') "Yes"
            stop
        end if
        call next_permutation(S_order, N)
    end do
    write (*, '(a)') "No"

end program

subroutine next_permutation(arr, n)

    integer i, n, k, l, kari, arr(n), tmp(n)

    do k = n - 1, 1, -1
        if (arr(k) < arr(k + 1)) exit
        if (k == 1) then
            !stop
        end if
    end do

    !STEP 2
    do l = n, k + 1, -1
        if (arr(k) < arr(l)) exit
    end do

    !STEP 3
    kari = arr(k)
    arr(k) = arr(l)
    arr(l) = kari

    !STEP 4
    if (k + 1 /= n) then
        do i = 1, k
            tmp(i) = arr(i)
        end do
        do i = 0, n - (k + 1)
            tmp(n - i) = arr(k + 1 + i)
        end do
        arr = tmp
    end if
end subroutine

```


## 余談
- C問題について、ついにFortranで解くには不利な問題に当たりました。next_permutationは自前で用意したので、次回からは大丈夫です。(えらい)
- 今回はA問題について、素直に割り算する方法がなぜか思い付かず、時間をギリギリでACして終了になりました。自身の発想力が、不安になるコンテストでしたが、危うくA問題すら解けなさそうな所、諦めずにAC出来た経験が得られたので満足です。