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

目次

• A - 2UP3DOWN
• B - 326-like Numbers
• C - Peak

A - 2UP3DOWN

問題

ビルの X 階から Y 階へ移動したいです。

2 階分までの上りと 3 階分までの下りであれば移動には階段を使います。
それ以外の場合はエレベーターを使います。

ビルの X 階から Y 階へ移動するとき、移動に使うのは階段とエレベーターのどちらかを求めます。

制約

1. $1≤X,Y≤100$
2. $X \neq Y$
3. 入力は全ては整数である

詳細はこちらです。

解説

【フローチャート】
入力 X,Y の数に応して条件を分岐させ、結果を出力します、

プログラム例

program abc326a
    ! X：現在階
    ! Y：目的階
    implicit none
    integer x, y

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

    !出力
    if (Y > X) then
        if (X + 2 >= Y) then
            write (*, '(a)') 'Yes'
        else
            write (*, '(a)') 'No'
        end if
    else
        if (X - 3 <= Y) then
            write (*, '(a)') 'Yes'
        else
            write (*, '(a)') 'No'
        end if
    end if
end program abc326a

B - 326-like Numbers

問題

3 桁の正整数 N　 が与えられます。
3 桁の正整数で「百の位の数と十の位の数の積」が「一の位の数と等しい」、N以上の最小の数を探します。

制約

1. $100≤N≤919$
2. N は整数である

詳細はこちらです。

解説

【フローチャート】
総当たりで「百の位の数と十の位の数の積が一の位の数と等しい数」を探します。

【補足】
※1
３桁の数　i を百の位、十の位、一の位に分ける計算を行います。
計算は以下の式を使用します。xは整数型で宣言しているため、小数点以下は切り捨てられます。

x(3) = i/100
x(2) = i/10 - x(3)*10
x(1) = i - x(3)*100 - x(2)*10

プログラム例

program abc326b
    !N    ：入力した整数
    !x    ：Nを桁ごとに分割した数
    !check：百の位の数と十の位の数の積
    implicit none
    integer N, i
    integer x(3), check

    !入力
    read (*, *) N

    !判定
    do i = N, 919
        x(3) = i/100
        x(2) = i/10 - x(3)*10
        x(1) = i - x(3)*100 - x(2)*10
        check = x(3)*x(2)
        !write (*, *) i, x(3), x(2), x(1)
        if (check == x(1)) then
            write (*, '(i0)') i
            stop
        end if
    end do
end program abc326b

C - Peak

問題

N 個のプレゼントが直線上の座標 $A_i$ に配置されています。

直線上の長さ M の半開区間 [x,x+M) を選び、そこに含まれるプレゼントを全て獲得します。
最大でいくつのプレゼントを獲得することができるかを求めます。

制約

1. 入力は全て整数
2. $1≤N≤3×10^5$
3. $1≤M≤10^9$
4. $1≤A_i≤10^9$

詳細はこちらです。

解説

【フローチャート】
$1≤N≤3×10^5$ であるため、総当たりでプレゼントの入手可否を調べるとTLEとなります。
尺取り法を用いて増分のみプレゼントの取得可否を調べます。

【補足】
※1
半開区間を調べる際、前回調べた範囲から増分のみを調べたいです。
Aが無作為に並んでいる場合は毎回、A(1)〜A(N)まで調べる必要が出てきてしまいます。
これを回避するために、A をソートします。

プログラム例

program abc326c
    ! N         ：直線上に置かれたプレゼントの総数
    ! M         ：半開区間
    ! A         ：直線上に置かれたプレゼントの座標
    !cnt_current：現在の区間で獲得できるプレゼントの数
    !cnt_max    ：獲得できるプレゼントの最大数
    implicit none
    integer(16) N, M
    integer(16), allocatable::A(:)
    integer(16) i, j, cnt_current, cnt_max

    !入力
    read (*, *) N, M
    allocate (A(N))
    read (*, *) A(:)
    call margesort(A, N)

    !最大値の検索
    cnt_max = 0
    j = 2
    cnt_current = 1
    do i = 1, N
        do
            if (M + A(i) > A(j) .and. j <= N) then
                cnt_current = cnt_current + 1
                j = j + 1
            else
                exit
            end if
        end do
        cnt_max = max(cnt_current, cnt_max)
        cnt_current = cnt_current - 1
    end do

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

感想

• A：3分、B：28分でした。
• C問題は前の結果から増分だけ調べる方法で実装を試みましたが、間に合いませんでした....