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

A - First ABC 2

問題

A , B , C からなる長さ N の文字列 S が与えられます。
S の中で 部分文字列 ABC が出現する位置を探してください。

ABC が見つかる場合、A の出現位置を出力してください。
ただし、ABC が複数見つかる場合には、最も初めに見つかった ABC が対象になります。
S の中に ABC が見つからない場合、-1 を出力します。

制約

1. $3≤N≤100$
2. S は A, B, C からなる長さ N の文字列

詳細はこちらです。

解説

【フローチャート】
1文字目から順番にABCが出現する位置を探します。

【補足】
※1
do文を用いて探索する部分をずらしながら、ABC が連続している部分を探します。
ABC は長さ 3 文字なので、S に収まり切るには N-2 文字目にある必要です。
Aの開始位置の上限を考慮して、探索範囲は　1 〜 N-2　までとなります。

※2
A B C が連続しているかを判定します。
連続している文字列なので１文字ずつ比較せず、ABCを一塊として見て比較します。

プログラム例

program abc322a
    implicit none
    integer i, N
    character(:), allocatable :: S

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

    !A,B,Cのカウント
    do i = 1, N - 2
        !write (*, *) S(i:i + 2)
        if (S(i:i + 2) == 'ABC') then
            write (*, *) i
            stop
        end if
    end do
    write (*, *) - 1
end program abc322a

B - Prefix and Suffix

問題

英小文字からなる文字列 S,T が与えられます。
S が T の 接頭辞、接尾辞であるかを判定してください。

接頭辞、接尾辞の判定によって以下のとおり出力します。

結果の出力
S が T の接頭辞、接尾辞の場合は 0 を出力します。
S が T の接頭辞の場合は 1 を出力します。
S が T の接尾辞の場合は 2 を出力します。
S が T の接頭辞、接尾辞でない場合は 3 を出力します。

制約

1. $1≤N≤M≤100$
2. S は英小文字からなる長さ N の文字列
3. T は英小文字からなる長さ M の文字列

詳細はこちらです。

解説

【フローチャート】
if文を用いて接頭辞、接尾辞の判定結果によって出力を制御します。

【補足】
※1
接頭辞と接尾辞かの判定により、check1とcheck2の値を変化させます。
「1の場合は該当する」、「0の場合は該当しない」とします。

※2
check1とcheck2の値によって出力の該当ケースを振り分け、結果を出力します。
出力の該当ケースの振り分けにはif文を使用します。

プログラム例

program abc322b
    implicit none
    integer N, M
    character(:), allocatable :: S, T
    integer check1, check2

    check1 = 0; check2 = 0

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

    !接頭辞、接尾辞の判定
    if (T(1:N) == S(1:N)) check1 = 1
    if (T(M - N + 1:M) == S(1:N)) check2 = 1

    if (check1 == 1) then
        if (check2 == 1) then
            write (*, *) 0
        else
            write (*, *) 1
        end if
    else if (check2 == 1) then
        write (*, *) 2
    else
        write (*, *) 3
    end if
end program abc322b

C - Festival

問題

N 日間のお祭りが開催されます。
お祭り期間中は、$A_1,A_2,...A_M$日目に花火が上がります。

お祭り期間中の i 〜 N 日目の各日において、次に花火が上がる日は何日後となるかを求めます。

制約

1. $1≤M≤N≤2×10^5$
2. $1≤A_1<A_2<⋯<A_M=N$
3. 入力は全て整数

詳細はこちらです。

解説

【フローチャート】
$A_M=2×10^5$ なので、$A_1$から順番に最も近い花火の打ち上げ日を検索するとTLEとなります。

【補足】
※1
花火打ち上げ日のリスト $A_1 〜 A_M$ から i 日に最も近い日を探します。
$1≤M≤2×10^5$ なので、$A_1$から順番に検索するとTLEとなります。

結果はお祭り 1 日目から昇順に求めていくので、i 日目の結果は i - 1 目の結果より前の結果になることはありません。

花火打ち上げ日をどこまで調べているかを変数 checkで管理し、i - 1 目からの差分だけ調べてる方法を用いてTLEを回避します。

プログラム例

program abc322c
    implicit none
    integer(8) N, M, check, i, ans
    integer(8), allocatable::A(:)

    !読み込み
    read (*, *) N, M
    allocate (A(M))
    read (*, *) A(1:M)

    !次の花火の日検索
    check = 1
    do i = 1, N
        call search_ff(i, check, A)
        ans = A(check) - i
        write (*, *) ans !, check
    end do
contains
    subroutine search_ff(i, check, A)
        implicit none
        integer(8) i, check, j
        integer(8) A(:)
        do j = check, size(A)
            if (i <= A(j)) then
                check = j
                return
            end if
        end do
    end subroutine search_ff
end program abc322c

感想

• 30分強でC問題まで解けました。
  難易度によるところがあると思いますが、とっても嬉しいです。(うれしい)
• D問題は配列を回転するプログラムを持っておらず、１から作ると間に合わなそうなので諦めました。