【ABC304】FortranでA,B,C問題 #AtCoder

A - First Player

問題はこちらです。
回答は以下の通りです。

出力の開始点(最年少の位置)が1人目になるとは限らないため、最年少からN番目まで単純に出力しても、全員が列挙できない可能性があります。
例えば、全体が10人で、最年少が3人目の場合、 3 ~ N まで出力すると1，2人目が出力されません。

そこで、以下の通り出力範囲を２つに分けて行いました。
①　最年少からN番目まで
②　1番目から最年少の手前まで

program ABC304a
    implicit none
    integer(8) i
    integer(8) N, min_num, min_i
    character(10), allocatable :: Name(:)
    integer, allocatable:: num(:)
    !入力
    READ (*, *) N
    allocate (Name(N), num(N))

    !最年少の検索
    min_num = 1*10**9
    do i = 1, N
        read (*, *) Name(i), num(i)
        if (num(i) < min_num) then
            min_num = num(i)
            min_i = i
        end if
    end do

    !結果の表示
    do i = min_i, N
        write (*, "(a)") Name(i)
    end do
    do i = 1, min_i - 1
        write (*, "(a)") Name(i)
    end do
end

B - Subscribers

問題はこちらです。
回答は以下の通りです。

Nを10^n で割って少数点以下を切り捨てます。
その後、10^n をかければ近似値を求める事が出来ます。

また、Nをinteger型で定義すれば、小数点以下は切り捨てになります。
従って、割った際の四捨五入等は不要です。

program ABC304b
    implicit none
    integer(8) N

    !入力
    READ (*, *) N

    !Nの近似値判定
    if (N <= 10**3 - 1) then !N が 10^3 −1 以下
        write (*, "(i0)") N
        stop
    end if
    if (N >= 10**3 .and. N <= 10**4 - 1) then !N が 10^3 以上、10^4 −1 以下
        N = N/(10**1)
        N = N*(10**1)
        write (*, "(i0)") N
        stop
    end if
    if (N >= 10**4 .and. N <= 10**5 - 1) then !N が 10^4 以上、10^5 −1 以下
        N = N/(10**2)
        N = N*(10**2)
        write (*, "(i0)") N
        stop
    end if
    if (N >= 10**5 .and. N <= 10**6 - 1) then !N が 10^5 以上、10^6 −1 以下
        N = N*(10**3)
        write (*, "(i0)") N
        stop
    end if
    if (N >= 10**6 .and. N <= 10**7 - 1) then !N が 10^6 以上、10^7 −1 以下
        N = N/(10**4)
        N = N*(10**4)
        write (*, "(i0)") N
        stop
    end if
    if (N >= 10**7 .and. N <= 10**8 - 1) then !N が 10^7 以上、10^8 −1 以下
        N = N/(10**5)
        N = N*(10**5)
        write (*, "(i0)") N
        stop
    end if
    if (N >= 10**8 .and. N <= 10**9 - 1) then !N が 10^8 以上、10^9 −1 以下
        N = N/(10**6)
        N = N*(10**6)
        write (*, "(i0)") N
        stop
    end if
end

C - Virus

問題はこちらです。
回答は以下の通りです。

連鎖する可能性のある全てのパターンを試した場合、計算量が多くTLEとなります。
従って今回は、DFS(深さ優先探索)を用いて感染する範囲を調べます。

DFSは再帰処理で実装します。
実装例はこちらです。

ここで、各点がつながっているかどうかは、ユークリッド距離で調べます。
探索済み(感染済み)であれば z(i)=1 とします。

module mod_global
    implicit none
    ! グローバル変数
    real, save, allocatable:: x(:), y(:), z(:)
    integer N

end module mod_global

program ABC304a
    use mod_global
    implicit none
    integer i, D

    !入力
    READ (*, *) N, D
    allocate (y(N), x(N), z(N))
    do i = 1, N
        read (*, *) x(i), y(i)
    end do
    z = 0

    !感染判定
    z(1) = 1
    do i = 2, N
        call DFS(1, i)
    end do

    !結果の出力
    do i = 1, N
        if (z(i) == 1) then
            write (*, "(a)") 'Yes'
        else
            write (*, "(a)") 'No'
        end if
    end do
contains
    !深さ優先探索
    recursive subroutine DFS(i, j)
        integer i, j, k
        real kyori
        kyori = sqrt((x(i) - x(j))**2 + (y(i) - y(j))**2)
        if (kyori <= D) then
            z(j) = 1
            do k = 2, N
                if (z(k) == 0) call DFS(j, k)
            end do
        end if
    end subroutine
end

余談

Fortranで再帰処理を書く場合には、頭にrecursiveを付ける必要がある
- 例1 ）recursive subroutine
- 例2 ）recursive function

感想

今回はついにB問題まで解く事が出来た。(問題が優しすぎた気がする)
C問題は解き方は分かったが、実装する時間が足りなくて終了。