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

## 目次
  - [A - Weak Beats](#a---weak-beats)
  - [B - Round-Robin Tournament](#b---round-robin-tournament)
  - [C - World Tour Finals](#c---world-tour-finals)


## 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 の文字列

詳細はこちらです。

https://atcoder.jp/contests/abc323/tasks/abc323_a


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

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/06739707-7ab4-6dff-ea0c-76aa47fd13c3.png" width=70%>

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

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


### プログラム例
```Fortran
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$ は問題文中の形式を満たす

詳細はこちらです。

https://atcoder.jp/contests/abc323/tasks/abc323_b


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

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/e0addd46-99eb-1964-a137-2f1d1e687b2b.png" width= 45%>

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

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

### プログラム例
```Fortran
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. 入力される数値は全て整数

詳細はこちらです。

https://atcoder.jp/contests/abc323/tasks/abc323_c


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

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/95d930ab-f236-e3a1-bf7f-7e5773836757.png" width= 80%>

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

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

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

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

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

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


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