【ABC347】AtCoder ABC347 Problem Cを解き直す

平目＠インフラエンジニア

AtCoder Beginner Contest 347で、今回AtCoderに初参加して来ました。

AB問題は解けたものの、C問題でWAを解決出来ずに挫折。1日経って改めて解き直して来たので、その経過をこちらに記載して行きたいと思います。言語はpython(CPython 3.11.4)を利用しています。


AtCoder ABC347 Problem C

問題内容は以下からご確認下さい。

提出1回目(コンテスト内)

指定された曜日での休日区間内に、標準入力の日付の曜日が全て収まるかどうかを判定するプログラムの作成が必要です。
まずはコンテスト中に提出したコードを以下に記載します。

def function():
# standard input
    N,A,B = map(int,input().split())
    D = list(map(int,input().split()))

# D mod(A+B) set again
    for i in range(N):
        D[i] = (D[i])%(A+B)

# condition max-min
    if(max(D)-min(D) < A):
        print('Yes')
    else:
        print('No')

if __name__ == "__main__":
    function()

上記のコードで提出してみましたが、1個WAという結果になりました。

WAが1個出た図

シンプルに解説すると、与えられた数値を全て1週間の日数(A+B)の余りに置き換えて配列上に配置し、その最大値と最小値の差を評価する事で、与えられた休日区間(A)以下であるかどうかを判定する様にしました。

このコードの何が問題かと言えば、週の折り返しを考慮出来ていない事です。

日曜を0とした週7日、週の休日を2日として考慮した時に、与えられた数値が土曜と日曜(6,0)だった場合にはMax(D)-Min(D)=6となり、同一休日区間外の判定になってしまいます。

上記パターンのイメージ

コンテスト内ではこの問題を解決出来ませんでしたが、ここから解き直していきます。

提出2回目

分かっているのは折り返しの問題なので、ここを解決していきます。まずDの重複を削除し、D_modに落とし込んでソートしました。
もし重複を削除した後の配列の長さが休日区間より長ければ、明らかに休日区間を超えるので、その場合は"No"をreturnします。

D_modの最小値と最大値の差が休日区間内A未満に収まっていれば与えられた全ての日付が休日区間内だと考える事が出来ますが、それだと上述のパターンを解決出来ないので、上記条件を満たさなかった場合は最小値にA+Bを加えて再評価する様に変更しました。

再評価するイメージ
def function():
    # standard input
    N,A,B = map(int,input().split())
    D = list(map(int,input().split()))

    # D mod(A+B) set again
    for i in range(N):
        D[i] = (D[i])%(A+B)
    
    # remove duplicate 
    D_set = set(D)
    D_mod = list(D_set)
    D_mod.sort()

    # check length
    if(len(D_mod) > A+1):
        print('No')
        return

    # check difference between the minimum and maximum values
    # if not meet the conditions, add a+b to the minimum value
    for i in range(len(D_mod)):
        if(max(D_mod)-min(D_mod) < A):
            print('Yes')
            return
        else:
            D_mod[i] += A+B
    
    # not meet the conditions
    print('No')    

if __name__ == "__main__":
    function()

これで問題だったパターンを掌握出来ているはずです。
しかしながら提出してみると、今度はTLEが頻発しました。

TLEが代わりに出た図

提出3回目

2回目の提出内容の反省点としては、配列D_modの長さが最大で2x10^5あるので、都度maxとminを算出する事が計算処理上で遅かった事です。
しかしながら、D_modは事前に昇順ソートしてあるので、ループ内でどんなにD_modの数値を変更しても、i=0以外は最小値はD_mod[i]で、最大値はD_mod[i-1]になるので、それを考慮して組み直しました。

def function():
    # standard input
    N,A,B = map(int,input().split())
    D = list(map(int,input().split()))

    # D mod(A+B) set again
    for i in range(N):
        D[i] = (D[i])%(A+B)
    
    # remove duplicate 
    D_set = set(D)
    D_mod = list(D_set)
    D_mod.sort()

    # check length
    if(len(D_mod) > A+1):
        print('No')
        return

    # check difference between the minimum and maximum values
    # if not meet the conditions, add a+b to the minimum value
    for i in range(len(D_mod)):
        if(i==0):
            if(D_mod[len(D_mod)-1] - D_mod[i] < A):
                print('Yes')
                return
            else:
                D_mod[i] += A+B
            continue

        if(D_mod[i-1] - D_mod[i] < A):
            print('Yes')
            return
        else:
            D_mod[i] += A+B
    
    # not meet the conditions
    print('No')    

if __name__ == "__main__":
    function()

このコードで、ようやくACとなりました。説明用にコメントを付けて提出しているのもありますが、コード長は長いですね。

AC通った図

通った後に改めて他の方のコードも眺めましたが、違うアプローチをしていた方も多かったので、そちらで再度組み直しました。

提出4回目

自分が作成したコードでの判定条件の要点は、対象の休日期間内に配列上の最大値と最小値が収まる事を条件としていましたが、
本条件を満たす場合は、ソートした時に連続した2要素間の値の差が、平日期間より大きくなる区間がある事に着目した方が居ました。こういう事ですね。

要素間の図

そちらでも記載してみる事にしました。

def function():
    # standard input
    N,A,B = map(int,input().split())
    D = list(map(int,input().split()))

    # D mod(A+B) set again
    for i in range(N):
        D[i] = (D[i])%(A+B)
    
    # remove duplicate 
    D_set = set(D)
    D_mod = list(D_set)
    D_mod.sort()

    # check length
    if(len(D_mod) > A+1):
        print('No')
        return
    
    # append D min value + A and B
    D_mod.append(D_mod[0]+A+B)

    # check difference between adjacent values
    for i in range(1,len(D_mod)):
        if(D_mod[i]-D_mod[i-1] > B):
            print('Yes')
            return
    
    # not meet the conditions
    print('No')    

if __name__ == "__main__":
    function()

このパターンだと、要素の最小値にA+Bを加えた値を配列の要素として加える事で、より簡単に週の折り返しを考慮する事が出来ますね。
直感的には少し考える必要がありますが、コーディング的にはこちらの方が可視性が高いですね。こちらのコードでもAC判定でした。

書き直して再提出、ACの図

こちらの方が実行時間も少し速いですね。

おわりに

初参加してみて、やはり難しいなと感じました。
しかしながら、解けなかった問題を改めて解き直す事で、パターン的な理解だったり、使い方だったりを学べたので、また次回も参加してみたいと思っています。

この記事が気に入ったらサポートをしてみませんか？