【Fortran】Fortran による Atcoder 競プロ典型 90 問 (★2) の回答集

# 概要
AtCoder において問題を解くために必要な実力を付ける問題集として、[競プロ典型 90 問](https://atcoder.jp/contests/typical90) があります。

本記事では、ABC の標準的な C 問題に相当する難易度である **★2**の問題を回答しています。

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

https://github.com/onodera-g/Fortran_Atcoder_90-Selection?tab=readme-ov-file

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

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

# 目次
  - [004-Cross_Sum](#004-cross_sum)
  - [010-Score_Sum_Queries](#010-score_sum_queries)
  - [022-Cubic_Cake](#022-cubic_cake)
  - [024-Select_+/-_One](#024-Select_+/-_One)
  - [027-Sign_Up_Requests](#027-sign_up_requests)
  - [033-Not_Too_Bright](#033-not_too_bright)
  - [055-Select_5](#055-select_5)
  - [061-Deck](#061-deck)
  - [067-Base_8_to_9](#067-base_8_to_9)
  - [078-Easy_Graph_Problem](#078-easy_graph_problem)

# 回答
## 004-Cross_Sum
各行と各列ごとに合計した結果をあらかじめ計算しておき、回答となる値を求めます。

ただし、マス (i,j) の結果は行と列の合計結果のどちらにも含まれるため、重複している部分は取り除く必要があります。


```Fortran
program Cross_Sum
    !A    ：整数
    !H,W  ：行と列の数
    !Hn,Wn：各行と各列の合計
    implicit none
    integer i, j
    integer H, W
    integer, allocatable::A(:, :), Hn(:), Wn(:)

    !入力
    read (*, *) H, W
    allocate (A(H, W), Hn(H), Wn(W))
    do i = 1, H
        read (*, *) (A(i, j), j=1, W)
    end do

    !各行列の合計
    do i = 1, H
        Hn(i) = sum(A(i, :)) !各行の合計
    end do
    do j = 1, W
        Wn(j) = sum(A(:, j)) !各列の合計
    end do

    !結果の出力
    do i = 1, H
        do j = 1, W
            if (j /= W) then
                write (*, '(i0,1x)', advance='no') Hn(i) + Wn(j) - A(i, j)
            else
                write (*, '(i0)') Hn(i) + Wn(j) - A(i, j)
            end if
        end do
    end do
end program Cross_Sum
```

## 010-Score_Sum_Queries
学籍番号が 1 ~ i までの結果をあらかじめ計算します。
回答時には、 1 ~ L の合計と、1 ~ R の合計の差を取り L ~ R  の合計を求めます。

```Fortran
program Score_Sum_Queries
    !N    ：生徒の人数
    !P    ：生徒の得点
    !C    ：生徒の得点
    !Q    ：クエリの総数
    !L,R  ：クエリにより合計したい範囲
    !subAB：生徒の得点の合計の累積
    implicit none
    integer i
    integer N, Q
    integer, allocatable::C(:), P(:), L(:), R(:), sumAB(:, :)

    !入力
    read (*, *) N
    allocate (C(N), P(N), sumAB(2, 0:N))
    do i = 1, N
        read (*, *) C(i), P(i)
    end do
    read (*, *) Q
    allocate (L(Q), R(Q))
    do i = 1, Q
        read (*, *) L(i), R(i)
    end do

    !合計の計算
    sumAB = 0
    do i = 1, N
        sumAB(C(i), i) = sumAB(C(i), i - 1) + p(i)
        sumAB(3 - C(i), i) = sumAB(3 - C(i), i - 1)
    end do

    !結果の出力
    do i = 1, Q
        write (*, '(i0,1x)', advance='no') sumAB(1, R(i)) - sumAB(1, L(i) - 1)
        write (*, '(i0)') sumAB(2, R(i)) - sumAB(2, L(i) - 1)
    end do
end program Score_Sum_Queries
```


## 022-Cubic_Cake
A , B , C の最大公約数を求めることにより、操作回数を求めます。
最大公約数はユークリッドの互除法により求めます。

```Fortran
program Cubic_Cake
    ! ABC(1): 幅A, ABC(2): 奥行きB, ABC(3): 高さCを格納する配列
    ! gcd_result: 直方体の幅A、奥行きB、高さCの最大公約数を格納する変数
    ! operations: 各方向で必要な切断回数の合計を格納する変数
    implicit none
    integer(16) :: ABC(3)
    integer(16) :: gcd_result
    integer(16) :: operations

    ! 入力
    read (*, *) ABC(1), ABC(2), ABC(3)

    ! 最大公約数の計算
    call cal_gcd(ABC, gcd_result)

    ! 各方向で必要な切断回数の計算
    operations = (ABC(1)/gcd_result - 1) + (ABC(2)/gcd_result - 1) + (ABC(3)/gcd_result - 1)

    ! 結果を出力
    write (*, *) operations
contains
    subroutine cal_gcd(nums, result)
        ! subroutine cal_gcd: 幅A、奥行きB、高さCの最大公約数を計算するサブルーチン
        ! nums: 幅A、奥行きB、高さCを格納した配列
        ! result: 計算された最大公約数を格納する変数
        implicit none
        integer(16), dimension(3), intent(in) :: nums
        integer(16), intent(out) :: result
        integer(16) :: i !

        ! 初期値として最初の要素のGCDを設定
        result = nums(1)

        ! 全ての数のGCDを計算
        do i = 2, size(nums)
            result = gcd(result, nums(i))
        end do
    end subroutine cal_gcd

    integer(16) function gcd(a, b)
        ! function gcd: 2つの整数のGCDを計算する関数
        ! a, b: GCDを計算する2つの整数
        ! r: 剰余を格納する変数
        ! x, y: a, bの絶対値をコピーし、GCD計算に使用する一時変数
        implicit none
        integer(16) :: a, b, r
        integer(16) :: x, y

        ! x, y に a, b をコピー
        x = abs(a)
        y = abs(b)

        ! ユークリッドの互除法を使用してGCDを計算
        do while (y /= 0)
            r = mod(x, y)
            x = y
            y = r
        end do
        gcd = x
    end function gcd
end program Cubic_Cake
```

## 024-Select_+/-_One
目的の配列の完成後に操作回数が余る場合には、　-1 と　+1 を繰り返して操作回数を調節します。
-1 と　+1 は 2 つで 1 セットなので、余剰分の操作回数は２で割り切れる必要があります。

```Fortran
program Select_One
    ! N   : 配列の長さ, K: 許される操作回数
    ! diff: 配列Aと配列Bの差の合計
    ! A   : 変換前の配列, B: 変換後の目標配列
    implicit none
    integer :: i
    integer :: N, K
    integer :: diff
    integer, allocatable :: A(:), B(:)

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

    !操作回数の計上
    diff = 0
    do i = 1, N
        diff = diff + abs(A(i) - B(i))
    end do

    !結果の出力
    if (diff <= K .and. mod(K - diff, 2) == 0) then
        print *, 'Yes'
    else
        print *, 'No'
    end if
end program Select_One
```

## 027-Sign_Up_Requests
登録済ユーザーのリストを配列で作成しておき、全探索により申請のあったユーザー名を受理するか判定します。
全探索時の計算量削減のため、登録済ユーザーの管理は １ 文字目のアルファベットごとに配列を作成して管理します。

```Fortran
program Sign_Up_Requests
    ! N              : 登録申請の数
    ! initial_chr    : ユーザ名の最初の文字のASCIIコード
    ! num_registered : 各初期文字ごとの登録されたユーザ名の数を追跡する配列
    ! registered     : それぞれの初期文字に基づいて登録されたユーザ名を保存する2次元配列
    ! name           : ユーザ名を格納する文字列
    implicit none
    integer :: N, i, j, initial_chr
    integer :: num_registered(48:122)
    character(len=15) :: registered(10**5, 48:122), name

    !入力
    read (*, *) N
    num_registered = 0

    ! 各日のユーザ申請を処理
    do i = 1, N
        ! ユーザ名の入力
        read (*, '(A)') name

        ! ユーザ名の1文字のASCIIコードを取得
        initial_chr = iachar(name(1:1))

        ! 登録済みユーザ名のチェック
        do j = 1, num_registered(initial_chr)
            if (name == registered(j, initial_chr)) exit ! 登録済みの場合は処理終了
        end do

        ! 新しいユーザ名なら登録
        if (j > num_registered(initial_chr)) then
            num_registered(initial_chr) = num_registered(initial_chr) + 1
            registered(num_registered(initial_chr), initial_chr) = name
            print *, i ! 登録された日の番号を出力
        end if
    end do
end program Sign_Up_Requests
```

## 033-Not_Too_Bright
列と行がどちらも偶数の場合には、 $(h * w ) / 2$ でLEDの個数が求められれます。
列と行がどちらも奇数の場合には、$(h + 1)/2)*((w + 1)/2)$ でLEDの個数が求められれます。

```Fortran
program Not_Too_Bright
    ! h : グリッドの縦の長さ
    ! w : グリッドの横の長さ
    use, intrinsic :: iso_fortran_env
    implicit none
    integer :: h, w ! グリッドの縦と横の長さを格納する変数

    ! 入力を受け取る
    read (input_unit, *) h, w

    ! 1行または1列の場合、全てのLEDを点灯可能
    if (h == 1 .or. w == 1) then
        print'(i0)', h*w
    else
        ! それ以外の場合は、縦横それぞれの半分(奇数なら+1)のLEDを点灯できる
        print'(i0)', ((h + 1)/2)*((w + 1)/2)
    end if
end program Not_Too_Bright
```

## 055-Select_5
全探索により回答を求めます。
ただし、$0≤A_i≤10^9$ であり、5 個の整数の積が integer(16) の範囲内に収まりきらない可能性があります。
この問題を回避するために、モジュロ演算（剰余演算）の性質を利用して、`mod(A(i)*A(j)*A(k)*A(l)*A(m),P)`　を　`mod(mod(mod(mod(A(i)*A(j), P)*A(k), P)*A(l), P)*A(m), P)`　に変換しています。


```Fortran
program Select_5
    ! N   : 整数の数
    ! P   : 割る数
    ! Q   : 余り
    ! cnt : 条件を満たす組み合わせの数
    ! A   : 整数の配列
    implicit none
    integer(16) :: i, j, k, l, m
    integer(16) :: N, P, Q
    integer(16) :: cnt
    integer(16), allocatable :: A(:)

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

    ! 5つの要素の積を P で割った余りが Q と等しいかを確認
    cnt = 0
    do i = 1, N - 4
        do j = i + 1, N - 3
            do k = j + 1, N - 2
                do l = k + 1, N - 1
                    do m = l + 1, N
                        if (mod(mod(mod(mod(A(i)*A(j), P)*A(k), P)*A(l), P)*A(m), P) == Q) cnt = cnt + 1
                    end do
                end do
            end do
        end do
    end do

    ! 結果の出力
    print *, cnt
end program Select_5
```

## 061-Deck
問題文通りにカードを山札を管理します。


```Fortran
program Deck
    ! Q      : 操作の数（クエリの数）
    ! top    : 山札の上にカードを追加する位置
    ! under  : 山札の下にカードを追加する位置
    ! t      : 操作の種類を格納する配列
    ! x      : 各操作で使う整数を格納する配列
    ! arr    : 山札の上と下にカードを格納する2次元配列
    implicit none
    integer :: i
    integer :: Q
    integer :: top, under
    integer :: tmp
    integer, allocatable :: t(:), x(:), arr(:, :)

    ! 入力
    read (*, *) Q
    allocate (t(Q), x(Q), arr(2, Q))
    do i = 1, Q
        read (*, *) t(i), x(i)
    end do

    ! カードを整理
    top = 1; under = 1; arr = 0
    do i = 1, Q
        select case (t(i))
        case (1) ! 山札の上にカードを追加
            arr(1, top) = x(i)
            top = top + 1
        case (2) ! 山札の下にカードを追加
            arr(2, under) = x(i)
            under = under + 1
        case (3) ! 山札の上から x(i) 番目のカードを出力
            if (x(i) < top) then
                tmp = top - x(i)
                write (*, *) arr(1, tmp)
            else
                tmp = x(i) - top + 1
                write (*, *) arr(2, tmp)
            end if
        end select
    end do
end program Deck
```

## 067-Base_8_to_9
８進数から9進数の変換は、「８進数 → 10進数 → 9進数」のように10進数を経由して行います。

```Fortran
program Base_8_to_9
    implicit none
    character(len=50) :: N ! x進数で表される数値 (文字列)
    integer :: x, y ! x: 元の進数, y: 変換後の進数
    character(len=50) :: result ! y進数に変換した結果
    integer :: status

    ! 入力 (元の数値N、x進数、y進数)
    print *, 'Enter the number (as string), base x, and base y:'
    read (*, *) N, x, y

    ! x進数からy進数への変換
    call convert_base(N, x, y, result, status)

    ! 結果の出力
    if (status == 0) then
        print *, 'The number in base ', y, ' is: ', result
    else
        print *, 'Error in conversion!'
    end if

contains
    ! x進数からy進数へ変換するサブルーチン
    subroutine convert_base(num_str, from_base, to_base, result, status)
        character(len=*), intent(in) :: num_str
        integer, intent(in) :: from_base, to_base
        character(len=*), intent(out) :: result
        integer, intent(out) :: status

        integer :: num_10, i, digit, len_str
        character(len=50) :: tmp_result
        character(len=1) :: ch

        result = ''
        status = 0
        num_10 = 0
        len_str = len_trim(num_str)

        ! (1) x進数から10進数へ変換
        do i = 1, len_str
            ch = num_str(i:i)
            select case (ch)
            case ('0':'9')
                digit = ichar(ch) - ichar('0')
            case ('A':'Z')
                digit = ichar(ch) - ichar('A') + 10
            case default
                status = 1 ! 不正な文字が含まれている場合
                return
            end select
            if (digit >= from_base) then
                status = 1 ! 不正な桁
                return
            end if
            num_10 = num_10*from_base + digit
        end do

        ! (2) 10進数からy進数へ変換
        tmp_result = ''
        if (num_10 == 0) then
            result = '0'
            return
        end if

        do while (num_10 > 0)
            digit = mod(num_10, to_base)
            if (digit < 10) then
                tmp_result = char(digit + ichar('0'))//tmp_result
            else
                tmp_result = char(digit - 10 + ichar('A'))//tmp_result
            end if
            num_10 = num_10/to_base
        end do

        result = adjustl(tmp_result)
    end subroutine convert_base
end program Base_8_to_9
```

## 078-Easy_Graph_Problem
各頂点における自分より小さい隣接頂点の数をカウントしておき、回答を求めます。

```Fortran
program Easy_Graph_Problem
    implicit none
    ! N  : 頂点数
    ! M  : 辺の数
    ! a, b : 各辺の頂点番号を格納する変数
    ! cnt: 条件を満たす頂点数をカウントする変数
    ! num_lower : 各頂点における自分より小さい隣接頂点の数を格納する配列
    integer(16) :: N, M, a, b, i, cnt
    integer(16), allocatable :: num_lower(:)

    ! 入力
    read (*, *) N, M
    allocate (num_lower(N))
    do i = 1, M
        read (*, *) a, b
        if (a < b) then
            num_lower(b) = num_lower(b) + 1
        else
            num_lower(a) = num_lower(a) + 1
        end if
    end do

    ! 条件を満たす頂点のカウント
    cnt = 0
    do i = 2, N
        if (num_lower(i) == 1) then
            cnt = cnt + 1
        end if
    end do

    ! 結果を出力
    print '(i0)', cnt
end program Easy_Graph_Problem
```