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

## A - Similar String
問題は[こちら](https://atcoder.jp/contests/abc303/tasks/abc303_a)です。
回答は以下の通りです。

入力した文字列SとTを１文字ずつ比較し、異なる文字が何文字あるかを調べます。
`ただし、似ている文字(1とl、０とo)は同じ文字として判定します。`

最後に異なる文字の数０ならYes、１以上ならNoを出力します。

```Fortran
program ABC303a
    implicit none
    integer i, N, diff
    character(:), allocatable:: S, T

    !入力
    READ (*, *) N
    allocate (character(N) :: S)
    allocate (character(N) :: T)
    READ (*, *) S, T

    !似た文字列の判定する
    diff = 0
    do i = 1, N
        if (S(i:i) /= T(i:i)) then
            diff = diff + 1
            if (S(i:i) == '1' .and. T(i:i) == 'l') diff = diff - 1
            if (S(i:i) == 'l' .and. T(i:i) == '1') diff = diff - 1
            if (S(i:i) == '0' .and. T(i:i) == 'o') diff = diff - 1
            if (S(i:i) == 'o' .and. T(i:i) == '0') diff = diff - 1
        end if
    end do

    !結果の出力
    if (diff == 0) then
        write (*, "(a)") 'Yes'
    else
        write (*, "(a)") 'No'
    end if
end
```

## B - Discord
問題は[こちら](https://atcoder.jp/contests/abc303/tasks/abc303_b)です。
回答は以下の通りです。

初めに考えうる全てのペアについて、組み合わせを用意します。
ペアの管理方法については、`となり合う数字(生徒)を４文字分の文字型に変換して管理しました。`
例えば、
　　12,11 なら '1211' として記録します。
　　 9,18 なら ' 918' として記録します。
とします。
(生徒が数字で表現されているので、足し算や掛け算で管理しようとしましたが、数字が被ってしまいそうだったので文字の並びとしました。)

その後、用意した組み合わせのペアについて、順番に集合写真に存在するかを１つずつ調べていきます。
集合写真の中に目的のペアが発見できた場合には、調べるのをやめて次のペアを調べる作業に移ります。
最後まで目的のペアが発見できなかった場合には、不仲とみなし、カウントを１増やします。

全ての組み合わせのペアについて調べ終わった後、カウントの数を出力して終了です。

```Fortran
program ABC303b
    implicit none
    integer i, j, k
    integer N, M, cnt_bad, cnt_pair
    character(4) pair_current
    integer, allocatable:: a(:, :)

    character(:), allocatable ::pair_all(:, :)
    !入力
    READ (*, *) N, M
    allocate (a(N, M))
    READ (*, *) a

    !ペアの組み合わせの総数の計算
    cnt_pair = 0
    do i = N - 1, 1, -1
        cnt_pair = cnt_pair + i
    end do
    allocate (character(4) :: pair_all(cnt_pair, 2))

    !ペアの組み合わせの作成
    cnt_pair = 0
    do i = 1, N - 1
        do j = 1, N - i
            cnt_pair = cnt_pair + 1
            write (pair_all(cnt_pair, 1), '(2i2)') a(i, 1), a(i + j, 1)
            write (pair_all(cnt_pair, 2), '(2i2)') a(i + j, 1), a(i, 1)
        end do
    end do

    !不仲である可能性の判定
    cnt_bad = 0
    do i = 1, cnt_pair
        tate: do j = 1, M
            yoko: do k = 1, N - 1
                write (pair_current, '(2i2)') a(k, j), a(k + 1, j)
                if (pair_all(i, 1) == pair_current) exit tate
                if (pair_all(i, 2) == pair_current) exit tate

            end do yoko
            if (j == M) cnt_bad = cnt_bad + 1
        end do tate
    end do

    !結果の出力
    write (*, '(i0)') cnt_bad
end


```

## C - Dash
問題は[こちら](https://atcoder.jp/contests/abc303/tasks/abc303_c)です。
回答は以下の通りです。

高橋くんを入力した指示通り(R,L,U,D)に移動させ、１回移動するたびに、
　・ HPを１減らす
　・ HPの0判定
　・ 回復マスの判定
を行います。

移動の途中でHPが0未満になれば、Noを出力させ、処理を終了させます。
最後まで処理を通す事が出来た(指示通り移動を全て終えれた)場合には、Yesを出力します。

流れとしては簡単ですが、回復マスの判定を行う部分が肝になります。
なぜなら、`移動回数や回復マスの個数が最大で 2×10^5 個となるからです。`

回復マスが2×10^5 個になった場合には、線形探索(1つずつ順番に調べる)では回復マスの有無の判定に時間がかかり、`実行時間内に処理が間に合いません。`

そこで今回は `hash map` で回復マスを管理し,`hash探索`により回復マスの有無を調べました。
`hash探索を用いる事で、1回の計算で回復マスの有無を調べる事が出来ます。(すごい)`

なお、hash mapはFortranには標準で搭載されていません。

そこで今回は、@ue1221さんが作成した[Java7のhash_mapをFortranに移植したもの](https://qiita.com/ue1221/items/1f2c435a12d4d82cbbf8)を使用させて頂きます。
この場を借りてお礼申しあげます。ありがとうございます。
([詳細についてはこちらで取り上げさせていただいています](https://qiita.com/onodera/items/f24b76bf5542073f6538)




<details><summary>プログラム例</summary><div>

```Fortran
module mod_hash_map
    implicit none
    integer, parameter :: int_max_value = 2147483647 ! integer(4)の最大値
    integer, parameter :: default_initial_capacity = 16 ! デフォルトの初期容量
    integer, parameter :: maximum_capacity = lshift(1, 30) ! ハッシュセットに保持できる最大の要素数
    real, parameter :: default_load_factor = 0.75 ! デフォルトの負荷係数

    type t_entry ! キーと値のペアを保持するノード
        integer :: key ! キー
        integer :: val ! 値
        type(t_entry), pointer :: next => null() ! このノードに繋がっている次のノード
        integer :: hash ! ハッシュ値
    end type

    type t_entry_ptr ! ノードのポインタ
        type(t_entry), pointer :: ref => null()
    end type

    type t_hash_map ! ハッシュマップ
        ! tableはキーと値のペアのノードを管理する配列
        type(t_entry_ptr), private, allocatable :: table(:)
        integer :: size = 0
        ! thresholdはtableのサイズを大きくするかの基準
        integer, private :: threshold = int(default_initial_capacity*default_load_factor)
        ! load_factorはthresholdを決めるための負荷係数
        real, private :: load_factor = default_load_factor
    contains
        procedure :: is_empty => is_empty
        procedure :: is_not_empty => is_not_empty
        procedure :: put => put
        procedure :: get => get
        procedure :: get_or_default => get_or_default
        procedure :: remove => remove
        procedure :: clear => clear
        procedure :: contains_key => contains_key
        procedure :: contains_val => contains_val
    end type

    interface hash_map ! ハッシュマップのコンストラクタ
        module procedure :: newhm0, newhm1, newhm2
    end interface

contains

    ! ノードのコンストラクタ
    function new_entry(key, val, h) result(res)
        integer, intent(in) :: key
        integer, intent(in) :: val
        integer, intent(in) :: h
        type(t_entry), pointer :: res
        allocate (res)
        res%key = key
        res%val = val
        res%hash = h
    end

    ! integer(4)のハッシュ値を計算する関数
    ! integer(4)だとf(n) = nの形になっていて無駄に見えますが、
    ! integer(8)やreal・character等の場合は、
    ! それらの値に応じて固有のinteger(4)を計算するために必要です。
    ! 例えばinteger(8)の場合はres = xor(i, shr(i, 32))など。
    ! 注：shrは下で宣言されている関数です。
    integer function hash_code(i) result(res)
        integer, intent(in) :: i
        res = i
    end

    ! ハッシュマップのコンストラクタ
    type(t_hash_map) function newhm0() result(res)
        allocate (res%table(default_initial_capacity))
    end

    ! ハッシュマップのコンストラクタ
    type(t_hash_map) function newhm1(initial_capacity) result(res)
        integer, intent(in) :: initial_capacity
        res = newhm2(initial_capacity, default_load_factor)
    end

    ! ハッシュマップのコンストラクタ
    type(t_hash_map) function newhm2(initial_capacity, load_factor) result(res)
        integer, intent(in) :: initial_capacity
        real, intent(in) :: load_factor
        integer :: capacity
        if (initial_capacity < 0) then
            capacity = default_initial_capacity
        else
            capacity = 1
            do while (capacity < min(initial_capacity, maximum_capacity))
                capacity = lshift(capacity, 1)
            end do
        end if

        if (load_factor <= 0 .or. load_factor /= load_factor) then
            res%load_factor = default_load_factor
        else
            res%load_factor = load_factor
        end if

        res%threshold = int(capacity*res%load_factor)
        allocate (res%table(capacity))
    end

    ! ビットシフト関数(Javaの>>>に相当)
    integer function shr(i, n) result(res)
        integer, intent(in) :: i, n
        if (n == 0) then
            res = i
        else
            res = rshift(ibclr(rshift(i, 1), 31), n - 1)
        end if
    end

    ! tableのインデックスに用いるハッシュ値生成関数
    integer function hash(i) result(res)
        integer, intent(in) :: i
        integer :: h
        h = i
        h = xor(h, xor(shr(h, 20), shr(h, 12)))
        res = xor(h, xor(shr(h, 7), shr(h, 4)))
    end

    ! ハッシュ値を1~size(table)に圧縮する関数
    integer function index_for(h, length) result(res)
        integer, intent(in) :: h, length
        res = and(h, length - 1) + 1
    end

    ! ハッシュマップが空かどうか
    logical function is_empty(this) result(res)
        class(t_hash_map), intent(in) :: this
        res = this%size == 0
    end

    ! ハッシュマップに要素が1つ以上入っているかどうか
    logical function is_not_empty(this) result(res)
        class(t_hash_map), intent(in) :: this
        res = this%size /= 0
    end

    ! キーに対応する値を取り出す
    ! キーが存在しない場合は適当に0を返す
    integer function get(this, key) result(res)
        class(t_hash_map), intent(in) :: this
        integer, intent(in) :: key
        integer :: h
        type(t_entry), pointer :: e
        h = hash(hash_code(key))
        e => this%table(index_for(h, size(this%table)))%ref
        do while (associated(e))
            if (e%hash == h .and. e%key == key) then
                res = e%val
                return
            end if
            e => e%next
        end do
        res = 0
    end

    ! キーに対応する値を取り出す
    ! キーが存在しない場合はdefを返す
    integer function get_or_default(this, key, def) result(res)
        class(t_hash_map), intent(in) :: this
        integer, intent(in) :: key
        integer, intent(in) :: def
        integer :: h
        type(t_entry), pointer :: e
        h = hash(hash_code(key))
        e => this%table(index_for(h, size(this%table)))%ref
        do while (associated(e))
            if (e%hash == h .and. e%key == key) then
                res = e%val
                return
            end if
            e => e%next
        end do
        res = def
    end

    ! キーが存在するかどうか
    logical function contains_key(this, key) result(res)
        class(t_hash_map), intent(in) :: this
        integer, intent(in) :: key
        type(t_entry), pointer :: e
        e => get_entry(this, key)
        res = associated(e)
    end

    ! キーに対応するノードを取得する
    ! キーが存在しない場合はnullを返す
    function get_entry(this, key) result(res)
        class(t_hash_map), intent(in) :: this
        integer, intent(in) :: key
        integer :: h
        type(t_entry), pointer :: e
        type(t_entry), pointer :: res
        h = hash(hash_code(key))
        e => this%table(index_for(h, size(this%table)))%ref
        do while (associated(e))
            if (e%hash == h .and. e%key == key) then
                res => e
                return
            end if
            e => e%next
        end do
        res => null()
    end

    ! ハッシュマップにキーと値のペアを登録する
    ! すでにキーが存在する場合は値を新しい値に上書きする
    subroutine put(this, key, val)
        class(t_hash_map), intent(inout) :: this
        integer, intent(in) :: key
        integer, intent(in) :: val
        integer :: h, i
        type(t_entry), pointer :: e
        h = hash(hash_code(key))
        i = index_for(h, size(this%table))
        e => this%table(i)%ref
        do while (associated(e))
            if (e%hash == h .and. e%key == key) then ! すでにキーが存在する場合
                e%val = val
                return
            end if
            e => e%next
        end do
        call add_entry(this, key, val, h, i) ! ハッシュマップに新しいキーと値のペアを追加する
    end

    ! ハッシュマップに新しいキーと値のペアを追加する
    ! ハッシュが衝突した際の処理は連鎖法となっている。連鎖法については以下を参照。
    ! https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB#%E9%80%A3%E9%8E%96%E6%B3%95
    subroutine add_entry(this, key, val, h, idx)
        class(t_hash_map), intent(inout) :: this
        integer, intent(in) :: key
        integer, intent(in) :: val
        integer, intent(in) :: h, idx
        type(t_entry), pointer :: e
        e => this%table(idx)%ref
        this%table(idx)%ref => new_entry(key, val, h)
        this%table(idx)%ref%next => e
        this%size = this%size + 1
        if (this%size >= this%threshold) call resize(this, 2*size(this%table))
    end

    ! tableがthreshold以上の個数の要素を保持している場合にtableを拡張する
    subroutine resize(this, new_capacity)
        class(t_hash_map), intent(inout) :: this
        integer, intent(in) :: new_capacity
        integer :: capacity, i, j
        type(t_entry), pointer :: e, next
        type(t_entry_ptr) :: table(new_capacity)
        capacity = size(this%table)
        if (capacity == maximum_capacity) then
            this%threshold = int_max_value
            return
        end if

        do j = 1, capacity
            e => this%table(j)%ref
            if (associated(e)) then
                this%table(j)%ref => null()
                do
                    next => e%next
                    i = index_for(e%hash, new_capacity)
                    e%next => table(i)%ref
                    table(i)%ref => e
                    e => next
                    if (.not. associated(e)) exit
                end do
            end if
        end do

        deallocate (this%table)
        allocate (this%table(new_capacity))
        do j = 1, new_capacity
            this%table(j)%ref => table(j)%ref
        end do
        this%threshold = int(new_capacity*this%load_factor)
    end

    ! キーに対応するノードを削除する
    ! キーが存在しない場合は何もしない
    subroutine remove(this, key)
        class(t_hash_map), intent(inout) :: this
        integer, intent(in) :: key
        integer :: h, i
        type(t_entry), pointer :: e, prev, next
        h = hash(hash_code(key))
        i = index_for(h, size(this%table))
        prev => this%table(i)%ref
        e => prev
        do while (associated(e))
            next => e%next
            if (e%hash == h .and. e%key == key) then
                this%size = this%size - 1
                if (associated(prev, e)) then
                    this%table(i)%ref => next
                else
                    prev%next => next
                end if
                return
            end if
            prev => e
            e => next
        end do
    end

    ! 全要素を削除する
    subroutine clear(this)
        class(t_hash_map), intent(inout) :: this
        deallocate (this%table)
        allocate (this%table(default_initial_capacity))
        this%size = 0
    end

    ! 対応する値がvalに等しいキーが存在するかどうか
    logical function contains_val(this, val) result(res)
        class(t_hash_map), intent(in) :: this
        integer, intent(in) :: val
        integer :: i
        type(t_entry), pointer :: e
        do i = 1, size(this%table)
            e => this%table(i)%ref
            do while (associated(e))
                if (e%val == val) then
                    res = .true.
                    return
                end if
                e => e%next
            end do
        end do
        res = .false.
    end
end module mod_hash_map

program ABC303c
    use mod_hash_map
    implicit none
    integer(4) N, M, H, K
    integer(4) x, y, xy_heal, xy_current
    integer(4) i
    character(:), allocatable:: S
    type(t_hash_map) :: map
    map = hash_map()

    !入力
    READ (*, *) N, M, H, K
    allocate (character(N) :: S)
    READ (*, *) S
    do i = 1, M
        read (*, *) x, y
        xy_heal = (x*10**5 + y)
        call put(map, xy_heal, 1)
        !write (*, *) xy
    end do

    !マス移動
    xy_heal = 0
    x = 0; y = 0
    do i = 1, N
        !移動
        select case (S(i:i))
        case ('R'); x = x + 1
        case ('L'); x = x - 1
        case ('U'); y = y + 1
        case ('D'); y = y - 1
        end select
        xy_heal = (x*10**5 + y)
        !write (*, *) xy

        !HP判定B
        H = H - 1
        if (H < 0) then
            write (*, "(a)") 'No'
            stop
        end if

        !回復判定
        if (H < K) then
            xy_current = map%get(xy_heal)
            !write (*, *) z
            if (xy_current == 1) then
                !write (*, *) H, '<', K
                H = K
                call map%remove(xy_heal)
            end if
        end if
    end do
    write (*, "(a)") 'Yes'
end
```
</div></details>



## 余談
- 今回はB問題が正解できそうなところでコンテストが終了しました。
do分の範囲をけちって１減らしてしまい、全範囲を調べていなかった事が原因でした。
いよいよB問題が正解できそうなところまで成長できて嬉しいです。