LoginSignup
1
1
@onodera

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

Last updated at Posted at 2023-10-10

目次

A - Weak Beats

問題

0 と 1 からなる長さ 16 の文字列 S が与えられます。
2 以上 16 以下のすべての偶数 i 文字目が 0 ならば Yes を、 そうでないならば No を出力してください。

ABC が見つかる場合、A の出現位置を出力してください。
ただし、ABC が複数見つかる場合には、最も初めに見つかった ABC が対象になります。
S の中に ABC が見つからない場合、-1 を出力します。

制約

  1. S は 0 と 1 からなる長さ 16 の文字列

詳細はこちらです。

解説

【フローチャート】
1 文字目から順番に 0 か 1 かを判定します。
i 文字目が奇数の時には何もしません。

【補足】
※1
0 か 1 かの判定は偶数文字のみで行います。
奇数文字の場合は何も行わないので、次のループに進みます。

※2
i 文字目(偶数文字)が 0 か判定します。
1 文字でも 1 となる場合には結果は No になるので、結果を出力してプログラムを終了します。

プログラム例

program abc323a
    ! S(16)：文字列S
    implicit none
    character(16) s
    integer i

    read (*, *) S

    do i = 1, len(S)
        if (mod(i, 2) /= 0) cycle
        if (S(i:i) == '1') then
            write (*, '(a)') 'No'
            stop
        end if
    end do
    write (*, '(a)') 'Yes'
end program abc323a

B - Round-Robin Tournament

問題

N 人のプレイヤーで総当たり戦をしました。
各プレイヤーの勝敗の結果は文字列 S で与えられます。
N人を勝利数の多い順に求めてください。

なお、勝利数が同じ場合には、プレイヤー番号が若い人が上位の順位となります。

制約

  1. $2≤N≤100$
  2. N は整数
  3. $S_i$ は o, x, - からなる長さ N の文字列
  4. $S_1,…,S_N$ は問題文中の形式を満たす

詳細はこちらです。

解説

【フローチャート】
各人のプレイヤーの処理数を集計し、マージソートにより並び替えます。

【補足】
※1
i 番目のプレイヤーの勝利数を算定します。
勝利数の算定はif文を用いSを１文字ずつ順番に調べ、o か それ以外を判定し勝利数のカウントを増加させます。

※2
各プレイヤーの勝利数を降順に並び替えます。
勝利数が同数の場合はプレイヤーの番号が小さい方が順位が上になります。
同数の場合の並びを順番の入れ替えたくないので、安定性が保証されているソートを用い勝利数の並び替えを行います。
今回はマージソートを使用します。

プログラム例

module global_abc323b
    ! N：プレイヤー数
    ! S：各プレイヤーの対戦結果
    implicit none
    character(:), allocatable :: S(:)
    integer N
end module
program abc323b
    ! cnt：各プレイヤーの並び順と勝利数
    ! tmp：マージソート用の仮変数
    use global_abc323b
    implicit none
    integer, allocatable:: cnt(:, :), tmp(:), tmp2(:)
    integer i

    read (*, *) N

    allocate (character(N)::S(N))
    allocate (cnt(N, 2), tmp(N), tmp2(N))
    do i = 1, N
        cnt(i, 2) = i
    end do

    read (*, *) S

    do i = 1, N
        call cnt_win(i, cnt)
    end do

    call margesort(cnt(:, 1), cnt(:, 2), tmp, tmp2, N, 1, N)

    write (*, '(*(1x,i0))') cnt(:, 2)

contains
    subroutine cnt_win(i, cnt)
        integer i, cnt(N, 2)
        integer j

        do j = 1, N
            if (S(i) (j:j) == 'o') cnt(i, 1) = cnt(i, 1) + 1
        end do
    end subroutine cnt_win

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

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

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

        !並び替えの下準備としてtmpに配列をコピー
        j = 0
        tmp(left:mid) = x(left:mid)
        tmp2(left:mid) = y(left:mid)
        do i = mid + 1, right
            tmp(i) = x(right - j)
            tmp2(i) = y(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)
                y(k) = tmp2(i)
                i = i + 1
            else if (tmp(i) == tmp(j) .and. tmp2(i) < tmp2(j)) then
                x(k) = tmp(i)
                y(k) = tmp2(i)
                i = i + 1
            else
                x(k) = tmp(j)
                y(k) = tmp2(j)
                j = j - 1
            end if
        end do
        !write (*, '(3x,*(f13.10,1x))') x(left:right)
    end subroutine margesort
end program abc323b

C - World Tour Finals

問題

N 人が M 問題を解き総合得点を競います。
問題 i の点数は $A_i$ 点です。

N人の回答状況が $S_1,S_2,...S_N$ で与えられます。
プレイヤー i がまだ解いていない問題を少なくとも何問解くことで、総合得点が1位になるかを求めます。
ただしプレイヤー i は i 点を始めから所持しています。

制約

  1. $2≤N≤100$
  2. $1≤M≤100$
  3. $500≤A_i≤2500$
  4. $A_i$ は 100 の倍数
  5. $S_i$ は o, x からなる長さ M の文字列
  6. $S_i$ には x が一個以上含まれる
  7. 入力される数値は全て整数

詳細はこちらです。

解説

【フローチャート】
$2≤N≤100$、$1≤M≤100$ なので総当たりで1位になる問題を探すとTLEになります。
ソートを行い得点の高い順に得点を追加して 1 位を目指します。

【補足】
※1
各プレイヤーが最小で何問解けば1位になるかを知りたいので、得点が高い問題から解いてもらえるよう、各問題を得点の昇順に並び替えます。

※2
対象のプレイヤー i の各問題の回答状況を調べます。
結果は配列submitに格納します。
回答済の場合は 1 を格納します。
未回答の場合は、回答した際に得られる得点を格納します。

※3
※2で集計した配列submitをソートすることで、未回答の問題を降順に並び替えます。
回答済みの問題は 1 が格納されているので、末尾に移動します。

※4
現時点での各プレイヤーの総得点を降順に並び替えます。
並び替えによって、現状の最高得点を知ることができます。

※5
※3で並び替えた配列submitの中身を手前(得点が高い順)から順番に総得点に累加していきます。
累加した回数に合わせて、追加で解く必要のある問題数のカウントをcntに記録します。

※6
※5でカウントしたcntは現状の総得点の降順に並んでいます。
出力時はプレイヤー順で出力することが求められます。
プレイヤー番号とcntを紐づけて、プレイヤー順を参照しソートします。

プログラム例

module global_abc323c
    ! M　　　：問題数
    ! N　　　：プレイヤー人数
    ! A(2,M)：各問題の並び順と得点
    ! S(N)  ：各プレイヤーの回答状況(回答済o,未回答x)
    implicit none
    character(:), allocatable :: S(:)
    integer, allocatable::A(:, :)
    integer N, M
end module
program abc323c
    ! submit(N,M)：各プレイヤーの回答状況(回答済1,未回答は得点)
    ! score(2,N) ：各プレイヤーの並び順と総得点
    ! cnt(N)　　　：1位になるために必要な回答数
    ! score_max  ：現時点の最高総得点
    ! tmp        ：マージソート用の仮変数
    use global_abc323c
    implicit none
    integer, allocatable:: submit(:, :), score(:, :), tmp(:), tmp2(:), tmp3(:), tmp4(:), cnt(:)
    integer i, score_max, j

    !入力
    read (*, *) N, M
    allocate (A(2, M), submit(N, M), score(2, N), tmp(N), tmp2(N), tmp3(M), tmp4(M), cnt(N))
    allocate (character(M)::S(N))
    read (*, *) A(2, :)
    read (*, *) S
    do i = 1, M
        A(1, i) = i
    end do
    do i = 1, N
        score(:, i) = i
    end do

    !得点並び替え
    call sort_margesort(A(2, :), A(1, :), tmp3, tmp4, M, 1, M)

    !現状の集計
    submit = 1
    do i = 1, N
        do j = 1, M
            if (S(i) (A(1, j):A(1, j)) == 'o') then
                score(2, i) = score(2, i) + A(2, j)
            else
                submit(i, j) = A(2, j)
            end if
        end do
        call sort_margesort(submit(i, :), cnt, tmp3, tmp4, M, 1, M)
    end do
    call sort_margesort(score(2, :), score(1, :), tmp, tmp2, N, 1, N)
    score_max = score(2, 1)

    !1位になるための問題数の算定
    cnt = 0
    do i = 2, N
        do j = 1, M
            score(2, i) = score(2, i) + submit(score(1, i), j)
            cnt(i) = cnt(i) + 1
            if (score(2, i) > score_max) exit
        end do
    end do
    call sort_margesort(score(1, :), cnt, tmp, tmp2, N, 1, N)

    !結果出力
    do i = N, 1, -1
        write (*, '(i0)') cnt(i)
    end do

contains
    !マージソート
    recursive subroutine sort_margesort(x, y, tmp, tmp2, N, left, right)
        integer(4) left, right, mid
        integer(4) N
        integer(4) x(N), tmp(N)
        integer(4) y(N), tmp2(N)
        integer(4) i, j, k

        if (left >= right) return

        mid = (left + right)/2
        call sort_margesort(x, y, tmp, tmp2, N, left, mid)
        call sort_margesort(x, y, tmp, tmp2, N, mid + 1, right)

        j = 0
        tmp(left:mid) = x(left:mid)
        tmp2(left:mid) = y(left:mid)
        do i = mid + 1, right
            tmp(i) = x(right - j)
            tmp2(i) = y(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)
                y(k) = tmp2(i)
                i = i + 1
            else if (tmp(i) == tmp(j) .and. tmp2(i) < tmp2(j)) then
                x(k) = tmp(i)
                y(k) = tmp2(i)
                i = i + 1
            else
                x(k) = tmp(j)
                y(k) = tmp2(j)
                j = j - 1
            end if
        end do
    end subroutine sort_margesort
end program abc323c

感想

  • C問題のデバッグをしている最中に終了しました。
  • 10/11に直近３回のレートのロールバック、再計算を行うようです。(大規模な不正が行われていたみたいです)
  • プログラム例の可読性向上のため、今回から各変数の説明を入れています。
  • スマホで記事を見た時の可読性向上のため、目次を入れていました。
1
1
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
1