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

A - 321-like Checker

問題

以下の条件を満たす正整数 x を 321-like Number と呼びます。
入力した N が 321-like Number なら Yes 、そうでないなら No と出力してください。

321-like Number

1. x の各桁を上から見ると狭義単調減少になっている。
2. x が d 桁の整数だとすると、 $1≤i<d$ を満たす全ての整数 i について次の条件を満たす。
   ( x の上から i 桁目 ) > ( x の上から i+1 桁目 )

制約

1. 入力は全て整数
2. $1≤N≤99999$

詳細はこちらです。

解説

【フローチャート】
先に各桁の数字を求めておき、その後に321-like Numberに該当するか調べます。

【補足】
※1
先に各桁の数字を求めておきます。

※2
do文を用いて５桁目から降順に１桁ずつ比較し、321-like Numberに該当するか調べます。

プログラム例

program abc321a
    implicit none
    integer N, x(6), i

    !読み込み
    read (*, *) N

    !各桁の計算
    x(6) = 0
    x(5) = N/10000
    x(4) = N/1000 - x(5)*10
    x(3) = N/100 - x(5)*100 - x(4)*10
    x(2) = N/10 - x(5)*1000 - x(4)*100 - x(3)*10
    x(1) = N/1 - x(5)*10000 - x(4)*1000 - x(3)*100 - x(2)*10

    !321-like Numberの判定
    do i = 5, 2, -1
        if (x(i) == 0 .and. x(i + 1) == 0) cycle
        if (x(i) <= x(i - 1)) then
            write (*, '(a)') 'No'
            stop
        end if
    end do
    write (*, '(a)') 'Yes'
end program abc321a

B - Cutoff

問題

１ 〜 N ラウンド目まである試験を受けます。
各試験は 0 〜 100 点でスコアが与えられます。
最終的結果は 1 〜 N ラウンドの最小スコアと最高スコアを除いたスコアの平均になります。

現在、試験のうち N−1 ラウンドが終了し、 i ラウンド目のスコアは $A_i$ でした。
最終結果を X 以上とするために N ラウンド目に取るべきスコアの最小値を出力してください。
N ラウンド目にどの様な点をとっても最終結果が X 以上にならない場合は -1 と出力してください。

制約

1. 入力は全て整数
2. $3≤N≤100$
3. $0≤X≤100×(N−2)$
4. $0≤A_i≤100$

詳細はこちらです。

解説

【フローチャート】
スコアは整数かつ 0 〜 100 と非常に小さいので、総当たりで最終結果が X 以上となるスコアを探します。

【補足】
※1
Nラウンドの目の試験の結果として i 点を追加します。

※2
最終的な結果の計算は最小スコアと最高スコアを除いた平均になります。
最小スコアと最高スコアを把握するために、マージソートを用いてNラウンドまでの結果をソートします。

プログラム例

program abc321b
    implicit none
    integer N, X, total, i
    integer, allocatable::A(:), tmp(:), arr(:)

    !読み込み
    read (*, *) N, X
    allocate (A(N), tmp(N), arr(N))
    read (*, *) A(1:N - 1)

    !Nラウンド目の数値検索
    do i = 0, 100
        arr = A; arr(N) = i
        call margesort(arr, tmp, N, 1, N)
        !write (*, *) arr
        total = SUM(arr(2:N - 1))
        if (total >= X) then
            write (*, '(i0)') i
            stop
        end if
    end do
    write (*, '(i0)') - 1

contains
    recursive subroutine margesort(x, tmp, N, left, right)
        integer left, right, mid
        integer N
        integer x(N), tmp(N)
        integer i, j, k

        !これ以上2分かつできないならretrun
        if (left >= right) return

        !分割できるだけ分割する
        mid = (left + right)/2
        call margesort(x, tmp, N, left, mid)
        call margesort(x, tmp, N, mid + 1, right)

        !並び替えの下準備としてtmpに配列をコピー
        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
        !write (*, '(3x,*(f13.101x),a)', advance='no') x(left:right)
        !write (*, '(a)', advance='no') '>>'
        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
        !write (*, '(3x,*(f13.10,1x))') x(left:right)
    end subroutine margesort
end program abc321b

C - 321-like Searcher

問題

A問題の続きです。
K 番目に小さい 321-like Number を求めてください。

制約

1. 入力は全て整数
   2.$1≤K$
2. 321-like Number は K 個以上存在する

詳細はこちらです。

解説

【フローチャート】
0 ~ 9 の 10 種類の数字は使う、使わないの２通りしか選択肢がないので、考えうる組み合わせは $2^{10}$ 通りしか組み合わせがありません。

321-like Number の組み合わせを計算し、K 番目に小さい 321-like Number を求めます。
組み合わせの列挙にはbit全探索を使用します。

【補足】
※1
「0 〜 9 を全て使用しないケース」、「0のみ使用するケース」では321-like Numberを作れないので、
321-like Numberは 2 〜 1023　の1022通りになります。

※2
321-like Number を計算します。
i をビット表記にし、j 番目のビットが 1 の場合は 321-like Number の計算処理を行います。

※3
計算した321-like Numberを解答用の配列の最後尾に追加します。

※4
解答用の配列には順次 321-like Number を格納したため、昇順に整理されていません。
マジーソートを用いて昇順に整理しなおします。

プログラム例

program abc321c
    implicit none
    integer(8) K
    integer(8) i, j, n, x, s
    integer(8), allocatable::ans(:), tmp(:)
    ans = [integer ::]; tmp = [integer ::]

    !読み込み
    read (*, *) K

    !321-like Numberの計算
    s = 1
    do i = 2, 1023
        x = 0
        do j = 9, 0, -1
            if (btest(i, j) .eqv. .true.) x = x*10 + j
        end do
        if (x == 0) cycle
        ans = [ans, x]
    end do
    n = size(ans)

    !結果の出力
    call margesort(ans, tmp, n, s, n)
    write (*, '(i0)') ans(K)

contains
    recursive subroutine margesort(x, tmp, N, left, right)
        integer(8) left, right, mid
        integer(8) N
        integer(8) x(N), tmp(N)
        integer(8) i, j, k

        if (left >= right) return

        mid = (left + right)/2
        call margesort(x, tmp, N, left, mid)
        call 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 margesort
end program abc321c

感想

• A問題がうまく解けず焦りましたが、気持ちを切り替えてA,B問題を解くところまで持ち直せました。