LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@onodera

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

Posted at

A - Chord

問題

英大文字からなる長さ3の文字列 S が与えられます。
SがACE、BDF、CEG、DFA、EGB、FAC、GBD のいずれかと等しいとき Yes を、そうでないとき No を出力します。

制約

  1. $S$は英大文字からなる長さ 3 の文字列

詳細はこちらです。

解説

【フローチャート】
入力したSに対して、順番にACE、BDF、CEG、DFA、EGB、FAC、GBD のいずれかに当てはまるかを調べます。

【補足】
※1
Sに対して、順番にACE、BDF、CEG、DFA、EGB、FAC、GBD のいずれかに当てはまるかを判定します。
当てはまる文字列が見つかった時点でYesを出力し、プログラムを終了します。

プログラム例

program ABC312a
    implicit none
    character(3) :: S

    !入力
    read (*, *) S

    !判定
    if (S == 'ACE') then
        write (*, *) 'Yes'
        stop
    end if
    if (S == 'BDF') then
        write (*, *) 'Yes'
        stop
    end if
    if (S == 'CEG') then
        write (*, *) 'Yes'
        stop
    end if
    if (S == 'DFA') then
        write (*, *) 'Yes'
        stop
    end if
    if (S == 'EGB') then
        write (*, *) 'Yes'
        stop
    end if
    if (S == 'FAC') then
        write (*, *) 'Yes'
        stop
    end if
    if (S == 'GBD') then
        write (*, *) 'Yes'
        stop
    end if
    write (*, *) 'No'
end program abc312a

B - TaK Code

問題

縦 N マス、横 M マスのグリッドが、以下の条件に当てはまる場合は Yes,そうでない場合は No を出力します。

条件(TaK Code)

  1. 縦 9 マス 横 9 マスの領域である
  2. 左上及び右下の縦 3 マス、横 3 マスの領域に含まれる計 18 マスは全て黒である
  3. 左上及び右下の縦 3 マス、横 3 マスの領域に八方位で隣接する計 14 マスは全て白である

制約

  1. $9≤N,M≤100$
  2. N,M は整数である
  3. $S_i$は . および # のみからなる長さ M の文字列である

詳細はこちらです。

解説

【フローチャート】
１マスずつ起点とする位置をずらしながら、 TaK Code　が成立するエリアがあるかを調べます。

【補足】
※1
TaK Codeの条件2を満たしているかの判定を行います。
判定はany関数を使用します。
any関数は複数の変数を一括して判定にかけることができ、1つでも当てはまらない変数がある場合にはNoとなります。
Noとなった場合にはTaK Codeの不成立が確定するので、cycle文で次のループへ進みます。

※2
TaK Codeの条件3を満たしているかの判定を行います。
判定はany関数を使用します。
Noとなった場合にはTaK Codeの不成立が確定するので、cycle文で次のループへ進みます。

※3
ここまでの判定で条件1~3を満たしているため、TaK Codeが成立しており、成立ケース(i,j)の出力を行います。
(i,j) の組は辞書順の昇順に出力する必要がありますが、本フローチャートでは(1,1)から随時成立ケースを検証、出力することになるため、並び替えは不要となります。

プログラム例

program ABC312b
    implicit none
    integer i, j
    integer N, M
    character(1), allocatable::  S(:, :)

    !初期化
    i = 0; j = 0
    N = 0; M = 0
    !入力
    read (*, *) N, M
    allocate (S(N, M))
    do i = 1, N
        read (*, '(*(a1))') (S(i, j), j=1, M)
    end do

    !判定
    do i = 1, N
        do j = 1, M
            !黒マス判定
            if (any(S(i:i + 2, j:j + 2) /= '#')) cycle
            if (any(S(i + 6:i + 8, j + 6:j + 8) /= '#')) cycle
            !シロマス判定
            !縦
            if (any(S(i:i + 2, j + 3) /= '.')) cycle
            if (any(S(i + 6:i + 8, j + 5) /= '.')) cycle
            !横
            if (any(S(i + 3, j:j + 3) /= '.')) cycle
            if (any(S(i + 5, j + 5:j + 8) /= '.')) cycle
            !結果の出力(随時)
            write (*, '(i0,1x,i0)') i, j
        end do
    end do
end program abc312b

C - Invisible Hand

問題

りんご市場に N 人の売り手と M 人の買い手がいます。
りんごを X 円で売ってもよいと考える売り手の人数が、りんごを X 円で買ってもよいと考える買い手の人数以上である最小の金額を調べます。

制約

  1. 入力は全て整数
  2. $2≤N≤2×10^5$
  3. $1≤A_i≤N$
  4. $A_i \neq i$

詳細はこちらです。

解説

【注意点】

  • $1≤A_i,B_i≤10^9$であるため、1円ずつ条件の成立を調べていくとTLEとなってしまいます。

【フローチャート】
条件の成立、不成立の変化は$A_i$と$B_i+1$円で発生するため、調べる範囲を絞ってプログラムを回します。

【補足】
※1
条件の成立、不成立の変化は$A_i$と$B_i+1$円で発生するため、入力したA,Bから売買の成立判定に使う読み出し順eventsを作成します。

※2
売買の成立する最小金額を知りたいので、読み出し順eventsをソートします。
ソートにはクイックソートを使用します。

※3
eventsを順番に読み込み、売り買いの人数を増減させます。

※4
売買の成立判定を行います。
売り手の人数 >= 買い手の人数　であれば売買の成立となります。
売買が成立している場合には、結果events(i)を出力し、プログラムを終了します。

プログラム例

program ABC312c
    implicit none
    integer(8) i, j, cnt_A, cnt_B, start
    integer(8) N, M
    integer(8), allocatable::  A(:), B(:), events(:)
    character(1), allocatable::events_AB(:)

    !初期化
    i = 0; j = 0

    !入力
    read (*, *) N, M
    allocate (A(N), B(M))
    allocate (events_AB(N + M), events(N + M))
    read (*, *) A(:)
    read (*, *) B(:)

    !読み出し順の作成
    B = B + 1
    events(1:N) = A; events(N + 1:M) = B
    events_AB = 'B'; events_AB(1:N) = 'A'
    start = 1
    call quicksort(events, events_AB, start, N + M)

    !判定
    cnt_A = 0; cnt_B = M
    do i = 1, N + M
        if (events_AB(i) == 'A') then
            cnt_A = cnt_A + 1
        else
            cnt_B = cnt_B - 1
        end if
        if (cnt_A >= cnt_B) then
            write (*, '(i0)') events(i)
            stop
        end if
    end do

contains
!sub:クイックソート
    recursive subroutine quicksort(a, b, first, last)
        implicit none
        integer(8) a(:), i, j, t
        character(1) b(:), t2
        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

            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
end program abc312c

感想

  • A,B問題WAなしで回答できました。良い。
  • 残りの時間でC問題を解いていたら終わりました。
  • (時間が確保できず、記事更新が大幅に遅れてしまいました....。みなさんはどうやって時間を確保しているのでしょうか。)
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?