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


## A - Weekly Records

### 問題
1から9 までの数字が書かれた 3×3の盤面の中に、A,Bを配置します。
配置したA,Bについて、隣り合う位置にあるかを調べ、"Yes"or"No"を出力します。

>**制約**
>1. $1≤A<B≤9$
>2. A,B は整数である。
>3. 隣り合う位置は**A,Bが"左右"に並んでいる場合のみ**を指します。



詳細はこちらです。

https://atcoder.jp/contests/abc309/tasks/abc309_a

### 解説
**【フローチャート】**
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/c3b6cc7d-dbc0-bc23-ab68-4b064bf017d7.png" width=60%>



**【補足】**
※1
3*3の盤面であるため、**3,4と6,7は隣り合う形になりません。**
従って、Aが３、６の時にはどうやっても隣り合うことはないため、Noとなります。





### プログラム例
```Fortran
program ABC309a
    implicit none
    integer(8) A, B
    !初期化
    A = 0; B = 0

    !入力
    read (*, *) A, B

    !処理
    if (A /= 3 .and. A /= 6) then !3と6の時は盤面の隅なので対象外
        if (A + 1 == B) then
            write (*, "(a)") 'Yes'
            stop
        end if
    end if

    !結果の出力
    write (*, "(a)") 'No'
end

```

## B - Default Price

### 問題
N 行 N 列の盤面のうち、**外周のみを時計回り**に動かした盤面を出力します。
>**制約**
>1. $2≤N≤100$
>2. $0≤A_{i,j}≤1(1≤i,j≤N)$
>3. 入力は全て1か0の整数

詳細はこちらです。

https://atcoder.jp/contests/abc309/tasks/abc309_b

### 解説
**【フローチャート】**
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/8ba0eaee-ad93-2823-ef52-18298899c914.png" width=45%>


**【補足】**
※1
Aは区切りのない数字で用意されています。
何もせずにread文を使い数字として読み込むと、区切りがないため、以下の様に読み込んでしまいます。

>A(1)=101
>A(2)=1101
>A(3)=1111
>A(4)=0000

今回は１文字ずつ区切って盤面を配列に構成したいため、 ``read (*, '(*(i1))')``により書式を指定して読み込みました。


※2
時計回りで回転させた盤面をBに作ります。
外周以外はそのままで良いので、``B=A``を行い一括して配列の中身をコピーします。
外周もそのままコピーされしまいますが、後の処理で値は上書きするので問題ありません。


※3
２重のdoループを用いて、回転させた後の盤面Bを１マスずつ作成します。

※4
対象のマスを**横方向**に１つ移動させます。
対象となるマスは、**1行目かN行目のマス**です。
ただし、$B(1,1)$と $B(N,N)$は**縦方向**にマスを移動させる必要があるため、``if文``を用いて判定から除外する必要があります。

※5
対象のマスを**縦方向**に１つ移動させます。
対象となるマスは、**1列目かN列目のマス**です。
ただし、$B(1,N)$と $B(N,1)$は**横方向**にマスを移動させる必要があるため、``if文``を用いて判定から除外する必要があります。



### プログラム例
```Fortran
program ABC309b
    implicit none
    integer i, j
    integer N
    integer, allocatable :: A(:, :), B(:, :)
    !初期化
    i = 0; j = 0; N = 0

    !入力
    read (*, *) N
    allocate (A(N, N), B(N, N))
    do i = 1, N
        read (*, '(*(i1))') (A(i, j), j=1, N) !1文字区切りで入力
    end do

    !時計回りに回転
    B = A
    do i = 1, N
        do j = 1, N
            !横の移動
            if (i == 1 .and. j /= 1) then
                B(1, j) = A(1, j - 1)
            else if (i == N .and. j /= N) then
                B(N, j) = A(N, j + 1)
            end if
            !縦の移動
            if (j == 1 .and. i /= N) then
                B(i, 1) = A(i + 1, 1)
            elseif (j == N .and. i /= 1) then
                B(i, N) = A(i - 1, N)
            end if
        end do
    end do

    !結果の出力
    do i = 1, N
        write (*, '(*(i1))') (B(i, j), j=1, N)
    end do
end


```

## C - Medicine
### 問題
N種類の薬を処方されました。
それぞれの薬は、**1日に飲む錠数 $b_i$錠** と **飲み続ける日数 $a_i$日が**異なります。
**1日に飲む錠数の総数**がK個以下となるには何日必要かを求めます。

>**制約**
>1. $1≤N≤3×10^5$
>2. $0≤K≤10^9$
>3. $1≤a_i,b_i≤10^9$


詳細はこちらです。

https://atcoder.jp/contests/abc309/tasks/abc309_c



### 解説
**【注意点】**
- この問題は、$1≤a_i,b_i≤10^9$です。
そのため、Do文を使って1日ずつ薬の飲む数を調べるとTLEになります。
また、日毎にDo文を使って飲む数を毎回調べるとTLEになります。

- $0≤K≤10^9$であるため、a,bの数に関わらず、1日目からK以下となる場合があります。

**【フローチャート】**
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/94caadf0-1509-68ac-157a-dd3c5aa9501d.png" width=70%>






※1
$1≤a_i,b_i≤10^9$であるため、その日飲む薬の総数についてaを全て調べ求めると**TLE**になってしまいます。
そこで、予め1日で飲む薬の最大数を調べておき、そこからA(i)日経過した時にb(i)錠だけ薬の数を減らすアプローチを取ります。
この方法は、その日に飲み切る薬のみを減らすだけで、その日飲む薬の総数を求める事ができます。
この処理を実装するために、**a,bの入力時に1日で飲む薬の最大数を調べておきます。**

※2
※1で示した内容を実践するためには、aは昇順に並んでいる必要があります。
今回はクイックソートを使用して並び替えを行いました。
なお、クイックソートは安定ソートではないため、同日内で薬の切れる順が前後する可能性があります。
ですが今回の場合は、薬の切れる順番は見ていないため問題ありません。


※3
1日目からK以下となっている場合を考慮し、先に判定を行います。

※4
その日飲む薬の総数は、$a(i)+1$日目から$a(i+1)+1$日目までは変化しません。
なぜなら、飲む薬の種類が変化しないからです。
従って、経過日数はa(i)ごとに見ていきます。




### プログラム例
```Fortran

program ABC309c
    implicit none
    integer(8) i
    integer(8) N, K, tmp
    integer(8), allocatable ::a(:), b(:)

    !初期化
    i = 0; tmp = 0

    !入力
    read (*, *) N, K
    allocate (a(N), b(N))
    do i = 1, N
        read (*, *) a(i), b(i)
        tmp = tmp + b(i)
    end do

    !昇順にソート
    call quicksort(a, b, 1, N, N)

    ! 1 日目：飲む薬がK以下かどうか
    if (tmp <= K) then
        write (*, '(i0)') 1
        stop
    end if

    ! i 日目：飲む薬がK以下かどうか
    do i = 1, N
        tmp = tmp - b(i)
        if (tmp <= K) then
            write (*, '(i0)') a(i) + 1
            stop
        end if
    end do
end program

!sub:クイックソート
recursive subroutine quicksort(a, b, first, last, N)
    implicit none
    integer(8) N
    integer(8) a(N), b(N), i, j, tmp1, tmp2
    integer(8) first, last, center
    i = first
    j = last
    center = a(int((first + last)/2))
    do
        do while (a(i) < center)
            i = i + 1
        end do
        do while (center < a(j))
            j = j - 1
        end do
        if (i > j) then
            exit
        else if (i == j) then
            exit
        end if
        tmp1 = a(i); a(i) = a(j); a(j) = tmp1
        tmp2 = b(i); b(i) = b(j); b(j) = tmp2
        i = i + 1
        j = j - 1
    end do
    if (first < i - 1) call quicksort(a, b, first, i - 1, N)
    if (j + 1 < last) call quicksort(a, b, j + 1, last, N)
end subroutine quicksort
```


## 感想
- A問題、**隣り合う縦の数**も調べていました。２次元の盤面だったので、勝手に縦も調べないといけないと錯覚していました。
- A問題に手間取ったので、B問題をギリギリ解いて終了でした。時間的にギリギリな中、落ち着いて問題を解けたのはよかったです。