【Fortran】Fortran による AtCoder Beginners Selection の回答集

# 概要
AtCoder における初心者向けの問題集として、[Atcoder Beginners Selection](https://atcoder.jp/contests/abs) があります。

同様の内容は github にも投稿しています。ライセンスは GPL-3.0 license です。

https://github.com/onodera-g/Fortran_Atcoder_Beginners-Selection

# 検証環境
回答では以下の環境で作成しています。
AtCoder での Fortran のバージョンは **gfortran 12.2** です。

|PC|OS|CPU|
|--|--|---|
|MacBook Air 2020|macOS Sonoma 14.5|M1|

# 目次
  - [PracticeA - Welcome to AtCoder](#practicea---welcome-to-atCoder)
  - [ABC086A - Product](#abc086a---product)
  - [ABC081A - Placing Marbles](#abc081a---placing-marbles)
  - [ABC081B - Shift only](#abc081b---shift-only)
  - [ABC087B - Coins](#abc087b---coins)
  - [ABC083B - Some Sums](#abc083b---some-sums)
  - [ABC088B - Card Game for Two](#abc088b---card-game-for-two)
  - [ABC085B - Kagami Mochi](#abc085b---kagami-mochi)
  - [ABC085C - Otoshidama](#abc085c---otoshidama)
  - [ABC049C - 白昼夢](#abc049c---白昼夢)
  - [ABC086C - Traveling](#abc086c---traveling)

# 回答
## PracticeA - Welcome to AtCoder
Sは1~100文字で長さが指定されません。
character(100)で変数Sを用意して、100文字分格納できる変数を用意しましょう。

```Fortran
program PracticeA
    !a,b,c：整数a,b,c
    !S    ：文字列S
    implicit none
    integer a, b, c
    character(100) S

    !入力
    read (*, *) a
    read (*, *) b, c
    read (*, *) S

    !結果の出力
    write (*, '(i0,1x,a)') a + b + c, S
end program PracticeA
```

## ABC086A - Product
aとbの積を2で割ったあまりが0か1かによって、偶数か奇数を判定します。
あまりの計算はmod関数で行います。

```Fortran
program ABC086A
    !a,b：正整数a,b
    implicit none
    integer a, b

    !入力
    read (*, *) a, b

    !偶数と奇数の判定
    if (mod(a*b, 2) == 0) then
        write (*, '(a)') 'Even'
    else
        write (*, '(a)') 'Odd'
    end if
end program ABC086A
```


## ABC081A - Placing Marbles
s1,s2,s3の入力がスペースで区切られていないため、そのまま読み込むと３桁の数として認識されてしまいます。
read文に書式を記載し、１文字区切りで値をs1,s2,s3へ読み込みます。

```Fortran
program ABC081A
    !s1,s2,s3：マス目s1~s3
    !cnt     ：ビー玉のあるマスの数
    implicit none
    integer s1, s2, s3
    integer cnt

    !入力
    read (*, '(*(i1))') s1, s2, s3

    !ビー玉のあるマスのカウント
    cnt = 0
    if (s1 == 1) cnt = cnt + 1
    if (s2 == 1) cnt = cnt + 1
    if (s3 == 1) cnt = cnt + 1

    !結果の出力
    write (*, '(i0)') cnt
end program ABC081A
```

## ABC081B - Shift only
正の整数Aの要素数は入力Nによって決まるため、Aは動的割り付け可能な配列として宣言します。
Aの全ての要素に対して２で割ることができるか確かめる必要がありますが、all関数を用いてまとめて判定を行うことができます。
また、Aを２で割る際にも、A=A/2とすることで全ての要素に対してまとめて処理を行うことができます。

```Fortran
program ABC081B
    !N ：正の整数Aの個数
    !A ：正の整数A
    !cnt：操作回数
    implicit none
    integer N, cnt
    integer, allocatable::A(:)

    !入力
    read (*, *) N
    allocate (A(N))
    read (*, *) A

    !Aを２で割って置き換える操作
    cnt = 0
    do
        if (all(mod(A, 2) == 0)) then
            A = A/2
            cnt = cnt + 1

        else
            exit
        end if
    end do

    !結果の出力
    write (*, *) cnt
end program ABC081B
```

## ABC087B - Coins
A,B,Cを0枚から全部使う組み合わせを全て試して、X円になる組み合わせを数えます。
3重のdo loopになりますが、A,B,Cは最大で50と少ないため、実行時間超過は発生しません。

```Fortran
program ABC087B
    !A  ：500円玉の個数
    !B  ：100円玉の個数
    !C  ：50円玉の個数
    !X  ：合計金額
    !cnt：合計金額をX円にできる組み合わせの個数
    implicit none
    integer i, j, k
    integer A, B, C, X, cnt

    !入力
    read (*, *) A
    read (*, *) B
    read (*, *) C
    read (*, *) X

    !効果の組み合わせの検証
    cnt = 0
    do i = 0, A
        do j = 0, B
            do k = 0, C
                if (500*i + 100*j + 50*k == X) cnt = cnt + 1
            end do
        end do
    end do

    !結果の出力
    write (*, *) cnt
end program ABC087B
```

## ABC083B - Some Sums
整数i を 各桁に分割する部分をsubroutineで実装しています。

```Fortran
program ABC083B
    !N：総和したい整数の上限
    !A,B：総和する条件(A 以上 B 以下)
    !cnt：A 以上 B 以下であるものの総和
    !digit_arr：1 ~ N を10 進法での各桁で分割した結果
    implicit none
    integer i
    integer N, A, B
    integer cnt
    integer, dimension(:), allocatable :: digit_arr
    !入力
    read (*, *) N, A, B

    !各桁の和が A 以上 B 以下であるものの総和
    do i = 1, N
        call get_digits(i, digit_arr)
        if (sum(digit_arr) >= A .and. sum(digit_arr) <= B) cnt = cnt + i
    end do

    !結果の出力
    write (*, *) cnt

contains
    ! 各桁を取り出すサブルーチン
    subroutine get_digits(N, digit_array)
        integer, intent(in) :: N ! 入力された整数
        integer, dimension(:), allocatable, intent(out) :: digit_array ! 各桁を格納する配列
        character(len=20) :: num_str ! 整数を文字列に変換するための変数
        integer :: i

        ! 整数を文字列に変換
        write (num_str, '(I0)') N

        ! 文字列の長さに基づいて配列を確保
        allocate (digit_array(len_trim(num_str)))

        ! 各桁を取り出して配列に格納
        do i = 1, len_trim(num_str)
            digit_array(i) = ichar(num_str(i:i)) - ichar('0')
        end do
    end subroutine get_digits
end program ABC083B
```

## ABC088B - Card Game for Two
Aを昇順にソートし、Alice→Bob→Alice...の順でカードを割り当てます。
ゲームの参加者は２名で交互にカードを取得するため、Aliceは奇数の時にカードを取得し、Bobは偶数の時にカードを取得します。

```Fortran
program ABC088
    !N：カードの枚数
    !A：各カードの数字
    !Alice：アリスの合計得点
    !Bob：ボブの合計得点
    implicit none
    integer i
    integer N, Alice, Bob
    integer, allocatable::A(:)

    !入力
    read (*, *) N
    allocate (A(N))
    read (*, *) A

    !並び替え
    call margesort(A, N)

    !得点差の計算
    Alice = 0; Bob = 0
    do i = 1, N
        if (mod(i, 2) == 1) then
            Alice = Alice + A(i)
        else
            Bob = Bob + A(i)
        end if
    end do

    !結果の出力
    write (*, *) abs(Alice - Bob)

contains
    subroutine margesort(x, n)
        integer N
        integer x(N), tmp(N)
        integer 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 left, right, mid
        integer N
        integer x(N), tmp(N)
        integer 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 ABC088
```

## ABC085B - Kagami Mochi
dを昇順にソートして、順番に鏡餅として積み重ねを行います。
ただし積み重ねる餅は真下の餅より小さい必要があるため、最上段の餅のサイズを保持しておき、サイズを比較しながら積み上げするか判定します。

```Fortran
program ABC085B
    !N：餅の数
    !d：餅のサイズ
    !Mochi：最上段の餅のサイズ
    !cnt：餅の段数
    implicit none
    integer N, Mochi, i, cnt
    integer, allocatable ::d(:)

    !入力
    read (*, *) N
    allocate (d(N))
    read (*, *) d

    !ソート
    call margesort(d, N)

    !鏡餅の積み重ね
    Mochi = d(1); cnt = 1
    do i = 2, N
        if (Mochi /= d(i)) then
            cnt = cnt + 1
            Mochi = d(i)
        end if
    end do

    !結果の出力
    write (*, *) cnt
contains
    subroutine margesort(x, n)
        integer N
        integer x(N), tmp(N)
        integer 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 left, right, mid
        integer N
        integer x(N), tmp(N)
        integer 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 ABC085B
```

## ABC085C - Otoshidama
10000円札、5000円札の組み合わせを総当たりで調べます。
なお、1000円札の枚数は、総当たりで調べる必要はありません。
10000円札、5000円札の枚数が定まる時、合計枚数Nから引くことで1000円札は求められます。

```Fortran
program ABC085C
    !N：お札の枚数
    !Y：合計金額
    !xx：10000円札の枚数
    !yy：5000円札の枚数
    !zz：1000円札の枚数
    implicit none
    integer :: N
    integer(16) Y, xx, yy, zz

    ! 入力
    read (*, *) N, Y

    !お札の枚数の検証
    do xx = 0, N
        do yy = 0, N
            zz = N - (xx + yy)
            if (zz >= 0) then
                if (10000_8*xx + 5000_8*yy + 1000_8*zz == Y) then
                    write (*, *) xx, yy, zz
                    stop
                end if
            end if
        end do
    end do
    write (*, *) - 1, -1, -1
end program ABC085C
```

## ABC049C - 白昼夢
dream dreamer erase eraser は内容が部分的に一致しているため、先頭から文字列の判定を行う場合は、文字列の区切る位置の見極めがつきません。
この問題を回避するために、文字列の末尾から順に単語として区切っていきます。

```Fortran
program ABC049C
    !S   ：文字列S
    !lenS：文字列Sの長さ
    !flag：結果の分岐判定(trueならYes)
    implicit none
    integer i, lenS
    character(len=100000) S
    logical flag

    ! 入力
    read (*, *) S
    lenS = len_trim(s)

    ! 文字列の再現判定(末尾から判定)
    i = lenS
    flag = .true.
    !文字列の再現判定
    do while (i > 0 .and. flag)
        if (i >= 7 .and. s(i - 6:i) == 'dreamer') then
            i = i - 7
        elseif (i >= 6 .and. s(i - 5:i) == 'eraser') then
            i = i - 6
        elseif (i >= 5 .and. s(i - 4:i) == 'dream') then
            i = i - 5
        elseif (i >= 5 .and. s(i - 4:i) == 'erase') then
            i = i - 5
        else
            flag = .false.
        end if
    end do

    ! 結果の出力
    if (flag .eqv. .true.) then
        print *, 'YES'
    else
        print *, 'NO'
    end if
end program ABC049C
```

## ABC086C - Traveling
1単位時間に移動できる移動量は、x,y のいずれかに１マスです。
現在地点から目的地までの移動距離が移動時間を越える場合は、移動距離が足りなくなるため旅行プランは実行不可能です。
移動距離と移動時間の偶奇が一致する場合に、旅行プランは実行可能となります。

```Fortran
program ABC086C
    !N        ：目的地の数
    !dt       ：目的地間での経過時間
    !t_prev   ：現在時刻
    !x_prev   ：現在のx座標
    !y_prev   ：現在のy座標
    !t_curr   ：目的地のx座標
    !x_curr   ：目的地の到着時刻
    !y_curr   ：目的地のy座標
    !dt       ：現在時刻と到着時刻の差
    !dist     ：現在位置から目的地までの道のり
    !flag_move：目的地までの移動可否
    implicit none
    integer i, N
    integer t_prev, x_prev, y_prev, t_curr, x_curr, y_curr, dt, dist
    logical flag_move

    ! N 入力
    read (*, *) N
    t_prev = 0; x_prev = 0; y_prev = 0
    flag_move = .true.
    do i = 1, n
        !t,x,y 入力
        read (*, *) t_curr, x_curr, y_curr
        dt = t_curr - t_prev
        dist = abs(x_curr - x_prev) + abs(y_curr - y_prev)
        !移動判定
        if (dist > dt .or. mod(dist, 2) /= mod(dt, 2)) then
            flag_move = .false.
            exit
        end if
        !座標と時刻の更新
        t_prev = t_curr; x_prev = x_curr; y_prev = y_curr
    end do

    !結果の出力
    if (flag_move) then
        print *, 'Yes'
    else
        print *, 'No'
    end if
end program ABC086C
```