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

目次

• A - Christmas Present
• B - Christmas Trees
• C - Socks 2

A - Christmas Present

問題

バットかグローブのうち、値段が高い方を出力します。

制約

1. B,G は 1 以上 1000 以下の相異なる整数

詳細はこちらです。

解説

バットとグローブの値段を比較して、金額の大きい方を出力します。

プログラム例

program abc333a
    !B:バットの値段
    !G:グローブの値段
    implicit none
    integer B, G

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

    !出力
    if (B > G) then
        write (*, *) "Bat"
    else
        write (*, *) "Glove"
    end if
end program abc333a

B - Christmas Trees

問題

東西に無限に伸びる道路があり、座標が A である地点を基点にして M m おきにクリスマスツリーを立てます。
座標L,R (L≤R)の間にあるクリスマスツリーの本数を求めてください。

制約

1. $−10^{18}≤A≤10^{18}$
2. $1≤M≤10^9$
3. $−10^{18}≤L≤R≤10^{18}$
4. 入力は全て整数

詳細はこちらです。

解説

座標Aを原点にL,Rの位置を考えて間にあるツリーの数を数えます。
座標Aは$−10^{18}≤A≤10^{18}$であるため、L、Rの座標は座標Aの分だけオフセットします。

またL,Rの範囲は$−10^{18}≤L≤R≤10^{18}$であるため、値の正負の組み合わせは「正正」、「正負」、「負負」の３パターンあります。
３パターン分の計算を考えるのは大変なので、L、Rにはあらかじめ大きい数を足しておき、値の正負の組み合わせを「正正」のみにしておきます。

プログラム例

program abc333b
    !L：高橋君の位置
    !R：青木君の位置
    !A：基点になる座標
    !M：ツリーを建てる間隔
    implicit none
    integer(16) A, M, L, R, X, ans

    !入力
    read (*, *) A, M, L, R

    !クリスマスツリーの本数計算
    L = L - A; R = R - A
    X = 10.0**18
    L = L + X*m; R = R + X*m
    ans = (R/M) - ((L - 1)/M)

    !結果出力
    write (*, *) ans
end program abc333b

C - Socks 2

問題

N 組の靴下のうち、色 $A _1,A_2,…,A_K$の靴下を 1 枚ずつなくしました。
残った靴下を組み合わせて、新しく靴下の組みを作り直します。

異なる色からなる靴下の組に「奇妙さ」という指標を設けます。
奇妙さは$∣i−j∣ $で定義されます。

靴下の組み合わせを作り直す時、奇妙さの総和が最小でいくつになるか求めてください。
ただし、無くした靴下が奇数の場合はどの組にも含まれない靴下が 1 枚存在することに注意してください。

制約

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

詳細はこちらです。

解説

なくしていない色の靴下はその色同士で組を作るのが最適です。

なくした色の靴下の組み合わせは、無くした靴下の数が偶数か奇数かによって異なります。

偶数の場合、奇妙さの総和が小さくなる様に隣同士の靴下$A_i、A_{i+1}$で組み合わせを作成し、奇妙さの総和を計算します。

奇数の場合は使わない靴下を1つ選ぶ必要があります。
使わない靴下を選んだ後は、偶数の場合と同様に隣同士の靴下$A_i、A_{i+1}$で組み合わせを作成し、奇妙さの総和を計算します。

ただし、使わない靴下を変える度に奇妙さの総和を計算し直すとTLEとなります。
対策として使わない靴下を$A_1$から順番に選んでいき、変更した差分のみを計算することで計算量を削減します。

プログラム例

program abc333c
    !N      ：靴下の組数
    !K      ：無くした靴下の数
    !A      ：無くした靴下の種類
    !min_Ans：奇妙さの最小値
    !Ans    ：奇妙さの計算
    implicit none
    integer N, K
    integer i, Ans, min_Ans
    integer, allocatable::A(:)

    !入力
    read (*, *) N, K
    allocate (A(K))
    read (*, *) A(:)
    Ans = 0

    !最小の奇妙さの計算
    if (mod(K, 2) == 0) then !無くした靴下が偶数個の場合
        do i = 1, K - 1, 2
            Ans = Ans + (A(i + 1) - A(i))
        end do
        min_Ans = Ans
    else !無くした靴下が奇数個の場合
        !1番目の靴下を使わない
        do i = 2, K - 1, 2
            Ans = Ans + (A(i + 1) - A(i))
        end do
        min_Ans = Ans
        !3~K番目の靴下を使わない
        do i = 3, K, 2
            Ans = Ans - (A(i) - A(i - 1))
            Ans = Ans + (A(i - 1) - A(i - 2))
            min_Ans = min(min_Ans, Ans)
        end do
    end if

    !結果の出力
    write (*, *) min_Ans
end program abc333c