Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@onodera

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

Last updated at Posted at 2024-09-20

概要

AtCoder において問題を解くために必要な実力を付ける問題集として、競プロ典型 90 問 があります。

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

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

検証環境

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

PC OS CPU
MacBook Air 2020 macOS Sonoma 14.5 M1

目次

回答

004-Cross_Sum

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

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

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 の合計を求めます。

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 の最大公約数を求めることにより、操作回数を求めます。
最大公約数はユークリッドの互除法により求めます。

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 セットなので、余剰分の操作回数は２で割り切れる必要があります。

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

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

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の個数が求められれます。

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)　に変換しています。

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

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

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進数を経由して行います。

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

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

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
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?