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

## A - Echo
問題はこちらです。

https://atcoder.jp/contests/abc306/tasks/abc306_a

回答は以下の通りです。

**Do文を使い、１文字ずつ２倍したものを順に格納していきます。**

値の格納には``配列の自動再割付機能``を使います。
追加する文字は一番後ろに追加されるので、Do文を回し終わった時点で完了です。

```Fortran
program ABC306a
    implicit none
    integer(8) i, N
    character(:), allocatable :: S
    character(1), allocatable ::S2(:)
    !入力
    READ (*, *) N
    allocate (character(N)::S)
    S2 = [character ::]
    READ (*, *) S

    !２倍して格納
    do i = 1, N
        S2 = [S2, S(i:i)]
        S2 = [S2, S(i:i)]
    end do

    !結果の出力
    write (*, *) S2
end
```

## B - Base 2
問題はこちらです。

https://atcoder.jp/contests/abc306/tasks/abc306_b

回答は以下の通りです。

**Do文を使い入力した文字を順に調べ、値が1であれば Ai\*\*2(i-1)を累加します。**

:::note warn
注意点
- 問題文のAiは0から始まっており、累乗もA**2(0)から始まります。
Fortranの配列は１からなので、計算する際には注意が必要です。

- integer(8)では値が収まりません。(1敗)
integer(16)での変数の宣言が必要です。
:::


```Fortran
program ABC306b
    implicit none
    integer(16) i, A(64), Ans
    !初期化
    A = 0; i = 0; Ans = 0

    !入力
    read (*, *) (A(i), i=1, 64)

    !計算部分
    do i = 1, 64
        if (A(i) == 1) Ans = Ans + A(i)*2**(i - 1)
    end do

    !結果の出力
    write (*, "(i0)") Ans
end
```


## C - Centers
問題はこちらです。

https://atcoder.jp/contests/abc306/tasks/abc306_c

回答は以下の通りです。

A(3＊N)の値を i=1,3*N のDo文を用いて順に調べ、 **1~N の出現回数をcnt(N)へ個別にカウントします。**
**カウント回数が ２(真ん中) となった時**、その位置i を A2(N) へ個別に記録します。

1~N の全ての数について、カウント回数が２となった時の位置が記録できたら、昇順に並べ替えて終了です。

並び替えについては、``クイックソート``を使用しました。
**ただし、並び替え対象は A2(N) ですが、答えに使うの出現位置に対応する数(1~N)です。**
従って、1~Nが昇順に格納された配列 Ans(N)を用意し、A2(N) の並び替えと並行して並び替えを行い、答えを求めました。

クイックソートのプログラムについては、t-nissieの日記 様のプログラムを一部改変して使用させていただきました。
この場を借りてお礼申し上げます。

https://srad.jp/~t-nissie/journal/450101/

```Fortran
program ABC306c
   program ABC306c
    integer(8) i, j, N
    integer(8), allocatable:: A(:), cnt(:), A2(:), Ans(:)
    !初期化
    i = 0; j = 0; N = 0

    !入力
    read (*, *) N
    allocate (A(3*N), cnt(N), A2(N), Ans(N))
    read (*, *) (A(i), i=1, 3*N)
    do i = 1, N
        Ans(i) = i
    end do

    !1~Nの出現回数のカウント
    do i = 1, 3*N
        j = A(i)
        cnt(j) = cnt(j) + 1
        if (cnt(j) == 2) then
            A2(A(i)) = i
        end if
    end do

    !登場順に並び替え
    call quicksort(A2, Ans, 1, N)

    !結果の出力
    write (*, *) Ans
end

!sub:クイックソート
recursive subroutine quicksort(a, b, first, last)
    implicit none
    integer*8 a(*)
    integer*8 b(*)
    integer*8 first, last
    integer(8) i, j
    real*8 x, t, t2
    x = a((first + last)/2)
    i = first
    j = last
    do
        do while (a(i) < x)
            i = i + 1
        end do
        do while (x < a(j))
            j = j - 1
        end do
        if (i >= j) exit
        t = a(i); a(i) = a(j); a(j) = t
        t2 = b(i); b(i) = b(j); b(j) = t2
        i = i + 1
        j = j - 1
    end do
    if (first < i - 1) call quicksort(a, b, first, i - 1)
    if (j + 1 < last) call quicksort(a, b, j + 1, last)
end subroutine quicksort

```

## 余談
### C問題の公式解答について

公式の解答では、A(３＊N)を順番に調べて 1~N の出現回数をカウントしていき、２になった時点で答えの配列の末尾に追加する解法が解説されています。

この方法なら、A(３＊N)を調べた終わった時点で昇順にならんでいるため、ソートを行う必要がありません。

当初はこの方法でACを目指していたのですが、TLEになってしまいました。
(計算量が増えない様に工夫をしましたが、それでもACになるほど速度が改善しませんでした。)

~~前述のACになった解答と比べても``自動再割付け機能``くらいしか違いがありません。
自動再割付け機能って処理として結構重たいのでしょうか....?~~

<font color="Navy">自動割り付け機能そのものが重たい訳ではない様です</font>
<font color="Navy">原因として、配列要素数の拡張``Ans = [Ans, j]``の計算量が多く、TLEとなっています。</font>

<font color="Navy">``Ans = [Ans, j]``で配列を追加する場合には、</font>
　<font color="Navy">$0$から$1$へ拡張する場合は$O(1)$</font>
　<font color="Navy">$1$から$2$へ拡張する場合は$O(2)$</font>
　<font color="Navy">$2$から$3$へ拡張する場合は$O(3)$</font>
<font color="Navy">...</font>
<font color="Navy">　$n-1$から$n$へ拡張する場合は$O(n)$</font>

<font color="Navy">といった様に、$n$が大きくなるほどに計算量が増えていきます。</font>
<font color="Navy">今回はDoループの中に``Ans = [Ans, j]``を組み込んでいる上、N=$10^5$であるため、TLEとなってしまったという事です。</font>



<font color="Navy">当該部分をあらかじめ用意した配列に格納する形としたところ、ACとなりました。</font>
<font color="Navy">（@osada-yum 様にご指摘いただきました。ありがとうございます。)</font>

<font color="red">修正後</font>
```Fortran
program ABC306c
    integer i, j, k, N
    integer, allocatable:: A(:), cnt(:), Ans(:)
    !初期化
    i = 0
    j = 0
    k = 0

    !入力
    read (*, *) N
    allocate (A(3*N), cnt(N), Ans(N))
    read (*, *) (A(i), i=1, 3*N)

    !1~nの出現地位の検出
    do i = 1, 3*N
        j = A(i)
        cnt(j) = cnt(j) + 1
        !カウント２ならAnsに追加
        if (cnt(j) == 2) then
            k = k + 1
            ans(k) = j
        end if
    end do
    !結果の出力
    write (*, *) Ans
end
```

<font color="red">修正前</font>
```Fortran
program ABC306c2
    integer i, N, j
    integer, allocatable:: A(:), cnt(:), Ans(:)
    !初期化
    i = 0
    Ans = [integer ::]

    !入力
    read (*, *) N
    allocate (A(3*N), cnt(N))
    read (*, *) (A(i), i=1, 3*N)

    !1~nの出現地位の検出
    do i = 1, 3*N
        j = A(i)
        cnt(j) = cnt(j) + 1
        !カウント２ならAnsに追加
        if (cnt(j) == 2) then
            Ans = [Ans, j]
        end if
        ![TLE回避策①]最後１つだけ見つかってないのなら、最後尾確定なのでAnsに追加
        if (cnt(j) == 1 .and. size(Ans) == N - 1) Ans = [Ans, j]
        ![TLE回避策②]Ansの要素数がNなら、全部見つかっているので終了
        if (size(Ans) == N) exit
    end do
    !結果の出力
    write (*, *) Ans
end

```


<details><summary> 感想</summary><div>

- 今回はB問題まで解けました。 C問題はTLEを回避する方法が思いつきませんでした。
- 変数は4倍精度、変数の初期化は問題に関わらず必ず行うべきな気がしてきました。
(問題の条件やコンパイラの挙動の違いを考えている暇はあんまりなさそうなので....)
</div></details>