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

## A - 3.14
### 問題
1 以上 100 以下の整数 N が与えられます。
円周率を小数第 N 位まで出力してください。

>**制約**
>1. $1≤N≤100$
>2. N は整数

詳細はこちらです。

https://atcoder.jp/contests/abc314/tasks/abc314_a


### 解説
**【フローチャート】**
入力した``N``に従って、円周率を出力します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/19023196-6e0a-f616-1284-9278dcc61525.png" width=35%>

**【補足】**
※1
円周率を100桁分を`変数pi`に用意します。
100桁をreal型で管理すると桁落ちが心配です。
加えて実数で管理すると、出力時の桁数を可変にするのが大変そうなので、文字型で管理します。

※2
`N`の数に関わらず、`3.`までは確実に出力するため、予め`3.`までを出力しておきます。

※3
円周率の**少数点よりも後ろの数字**を入力した`N`に合わせて出力します。
文字型で定義しているので、出力する範囲を`pi(1:N)`とすれば、出力時の桁数を可変にできます。


### プログラム例
```Fortran
program ABC314a
    implicit none
    character(100) pi
    integer N

    !初期化
    pi = '1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679'

    !入力
    read (*, *) N

    !出力
    write (*, '(a2)', ADVANCE='NO') '3.'
    write (*, '(a)') pi(1:N)

end program abc314a
```



## B - Roulette
### 問題
N 人の人がルーレットの賭けに参加しました。
ルーレットの出目は、0 から 36 までの整数です。
N 人はそれぞれ$C_i$個の目、 $A_{i,1},A_{i1},A_{i,1},…,A_{i,C_i}$ に賭けています。

ルーレットが回され、出目が X の時、 X に賭けた人たちのうち、**賭けた目の個数が最も少ない人**たちの番号を**昇順**にすべて出力してください。

>**制約**
>1. $1≤N≤100$
>2. $1≤C_i≤37$
>3. $0≤A_{i,j}≤36$
>4. 任意の i=1,2,…,N について、$A_{i,1},A_{i,2},…,A_{i,C_i}$はすべて異なる。
>5. $0≤X≤36$
>6. 入力はすべて整数

詳細はこちらです。

https://atcoder.jp/contests/abc314/tasks/abc314_b


### 解説
**【フローチャート】**
$N,C_i$ が十分に小さいので、N 人の結果を全て確認し、X に賭けた人で賭けた目の個数が最も少ない人を探します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/8a72f9f2-618c-1af7-8b93-793351bcc94d.png" width=50%>


**【補足】**
※1
`any関数`を使い、$A_{i,1},A_{i1},A_{i,1},…,A_{i,C_i}$ の中にXが含まれているかを調べます。

※2
`min関数`を用いて、Xが含まれている最小の$C_i$を探します。

※3
結果の出力を行います。
$C_1 ~C_N$までを全て調べ、Xが含まれている最小の$C_i$を順次出力します。


### プログラム例
```Fortran
program ABC314b
    implicit none
    integer i, j
    integer N, X, min_C, cnt
    integer, allocatable :: A(:, :), check_hit(:), C(:)

    !初期化
    cnt = 0
    check_hit = 0
    min_C = 99

    !入力1
    read (*, *) N
    allocate (A(N, 99), check_hit(N), c(N))
    A = 99
    do i = 1, N
        read (*, *) C(i)
        read (*, *) (A(i, j), j=1, C(i))
    end do
    read (*, *) X

    !Xを含む最小のCを調べる
    do i = 1, N
        if (any(A(i, :) == X)) then
            check_hit(i) = 1
            min_C = min(min_C, C(i))
        end if
    end do

    !結果の出力
    if (min_C == 99) then
        write (*, '(i0)') 0
    else
        do i = 1, N
            if (C(i) == min_C .and. check_hit(i) == 1) cnt = cnt + 1
        end do
        write (*, '(i0)') cnt
        do i = 1, N
            if (C(i) == min_C .and. check_hit(i) == 1) write (*, '(i0,1x)', ADVANCE='NO') i
        end do
    end if
end program abc314b
```


## C - Rotate Colored Subsequence
:::note warn
~~【未ACです】~~
~~プログラム例には注意が必要です。~~
~~`allocate (a(M, N))`が入るタイミングでRE(実行時エラー)となるケースがあり、ACされていません。~~
ACになりました。修正した回答は最後に掲載しています。
:::

### 問題
長さ N の文字列 S が与えられます。
S の各文字は、色 1から色 M のいずれかの色で塗られています。
文字列 S について、同じ色で塗られた文字同士で**右に 1 つ巡回シフト*を行い、最終的な文字列 S を作成します。

>**制約**
>1. $1≤M≤N≤2×10_5$
>2. $21≤C_i≤M$
>3. $N,M,C_i$はすべて整数
>4. S は英小文字からなる長さ N の文字列
>5. 任意の整数 $1≤i≤M$ に対して、ある整数 $1≤j≤N$ が存在して $C_j=i$ が成り立つ

詳細はこちらです。

https://atcoder.jp/contests/abc314/tasks/abc314_c


### 解説
**【注意点】**
- $1≤M≤N≤2×10_5$であるため、総当たりで巡回シフトを実装すると、`TLE`となってしまいます。

**【フローチャート】**
同じ色ごとに文字列の配列を作成し、個別に巡回シフトを行い、最後に文字列を結合して配列を作成します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/4104a576-2dd0-46cf-d2f1-1e78ac16a4b4.png" width=50%>

**【補足】**
※1
各文字を１文字ずつ調べ、色 1から色 M までの出現回数を算出します。

※2
各文字を１文字ずつ調べ、その文字が何色で何文字目かを記録します。
※1で算出した出現回数を参照して、昇順に配列に格納します。

※3
各色ごとに記録した配列において、右に1つ巡回シフトした配列番号を計算します。
基本的に右に1つずらすだけなので+1すれば良いのですが、末尾は先頭にシフトすることに注意が必要です。
今回は、各色の出現回数の総数で割ったあまりを使うことで、1つの計算式で巡回シフト先の配列番号を計算しています。
>例
>色Aの出現回数の総数が4の場合
>元の配列 (i=1,4) は[1],[2],[3],[4]は巡回シフト後、[4],[1],[2],[3]となります。
> $巡回シフト先 =mod(i,4)+1$とすれば、1,2,3の時はあまり+1になり、4の時は0+1で先頭にシフトするとができます。


※4
計算した巡回シフト先の番号を元に、各色ごとの配列に格納された出現順の記録を右に1つ巡回シフトします。


※5
文字列 S の色を順番に見ていき、色に応じた文字を１文字づつ出力します。
出力は各色ごとの出現順を記録した配列を参照し、昇順に出力していきます。
１文字づつ順次出力するので、`write構文`に `advance='no'`を追加し、改行されない様にします。


### プログラム例
<details><summary>なぜ以前の回答はREだったのか？</summary><div>

以前の回答では、各色の出現位置と回数を管理する配列を考えうる最大サイズ`(M,N)`で確保していたことにより、**必要なメモリが大きくなりすぎた結果**、`RE`となっていました。

解決策として、`type`を用いて**配列の中にallocatable な配列を持たせ**配列のサイズを最小限にし、メモリ不足を解消、ACとなりました。

</div></details>


<details><summary>古い回答</summary><div>

```Fortran
program ABC314c_RE
    !implicit none
    integer(16) N, M, i, tmp
    integer(16), allocatable::  C(:), cnt(:), cnt_max(:)
    character(:), allocatable :: S, list(:, :), ans(:, :)

    read (*, *) N, M
    allocate (character(N) :: S)
    allocate (cnt_max(M), cnt(M)); cnt_max = 0; cnt = 0
    allocate (character(1) :: list(M, N), ans(M, N))
    read (*, *) S
    allocate (C(N))
    read (*, *) C(:)

    !出現位置の振り分け
    do i = 1, N
        cnt(C(i)) = cnt(C(i)) + 1
        list(C(i), cnt(C(i))) = S(i:i)
    end do

    !巡回シフト
    cnt_max = cnt
    cnt = 0
    do i = 1, N
        cnt(C(i)) = cnt(C(i)) + 1
        tmp = mod(cnt(C(i)), cnt_max(C(i))) + 1
        ans(C(i), tmp) = list(C(i), cnt(C(i)))
    end do

    !結果の出力
    cnt = 0
    do i = 1, N
        cnt(C(i)) = cnt(C(i)) + 1
        write (*, '(a)', advance='no') ans(C(i), cnt(C(i)))
    end do
end
```
</div></details>

```Fortran
program ABC314c_AC
    !implicit none
    integer(16) N, M, i, tmp
    integer(16), allocatable::  C(:), cnt(:), cnt_max(:)
    character(:), allocatable :: S
    type :: array
        character(1), allocatable :: arr(:)
        character(1), allocatable :: arr2(:)
    end type
    type(array), allocatable :: arr_of_arr(:), arr2_of_arr(:)
    !１次元の配列(arr_of_arr)の中に1次元の配列(arr)が入っています。
    !arr_of_arr(:)で縦の長さを可変長、arr(:)で横の長さを可変長にしています。

    read (*, *) N, M
    allocate (character(N) :: S)
    allocate (cnt_max(M), cnt(M)); cnt_max(M) = 0; cnt(M) = 0
    allocate (arr_of_arr(M), arr2_of_arr(M))

    read (*, *) S
    allocate (C(N))
    read (*, *) C(:)

    !各色の出現回数の取得
    do i = 1, N
        cnt(C(i)) = cnt(C(i)) + 1
    end do
    do i = 1, M
        allocate (arr_of_arr(i)%arr(cnt(i)))
        allocate (arr2_of_arr(i)%arr2(cnt(i)))
    end do
    cnt = 0
    do i = 1, N
        cnt(C(i)) = cnt(C(i)) + 1
        arr_of_arr(C(i))%arr(cnt(C(i))) = S(i:i)
    end do

    !巡回シフト
    cnt_max = cnt
    cnt = 0
    do i = 1, N
        cnt(C(i)) = cnt(C(i)) + 1
        tmp = mod(cnt(C(i)), cnt_max(C(i))) + 1
        arr2_of_arr(C(i))%arr2(tmp) = arr_of_arr(C(i))%arr(cnt(C(i)))
    end do

    !結果の出力
    cnt = 0
    do i = 1, N
        cnt(C(i)) = cnt(C(i)) + 1
        write (*, '(a)', advance='no') arr2_of_arr(C(i))%arr2(cnt(C(i)))
    end do
end
```


## 感想

- C問題について、allocate (a(M, N))が入るタイミングでRE(実行時エラー)となるケースがあり、ACがどうしてもACできませんでした。(下記URL)
    - [該当部分のみ]https://atcoder.jp/contests/abc314/submissions/45003764
    - [回答全体]https://atcoder.jp/contests/abc314/submissions/45002589
    -  $1≤M≤N≤2×10^5$に対して`allocate(a(M,N))`をしているので、配列が大きすぎるとallocateの機能が使えないのかなと、今のところ考えています。
    -  記事にするか悩みましたが、自身の勉強のために投稿していること、回答のアルゴリズム自体は間違っていないと考え投稿しています。