【AtCoder 緑色を目指して】ABC367【競技プログラミング】

技術ブログ 競技プログラミング

はじめに

こんにちは、駒嶺です。今回はAtCoder Beginner Contest 367の所感です。
今回もPythonで解いていきます。

A – Shout Everyday

AtCoder 王国の住民はA時になるとたこ焼きへの愛を叫ぶことになっています（？？）
毎日B時に就寝しC時に起床する場合、A時に愛を叫ぶことができるでしょうか？

A, B, C = map(int, input().split())

if B < C:
    print("Yes" if A < B or C < A else "No")
else:
    print("Yes" if C < A < B else "No")

BとCのどちらが大きいかで分岐させました。
B < Cの時、A < B or C < Aで高橋君が起きているか判定しましたが、 B < A < Cと書いた方がB < Cでない時の式と対称になって美しかったですね。

B – Cut .0

小数点以下のの末尾の0をすべて消します。
小数点以下がすべて消えた場合小数点も消します。
つまり12.340なら12.34、0.000なら0を出力します。

解答

print(input().rstrip("0").rstrip("."))

rstrip()で末尾の特定の文字を消せます。いわゆるtrimですね。

C – Enumerate Sequences

総和がKの倍数となる長さNの整数列を辞書順で出力します。
ただし、整数列のi番目の要素は1以上Ri以下です。

Nの最大値は8、Riの最大値は5と制約は緩めです。

解答

N, K = map(int, input().split())
R = list(map(int, input().split()))

def saiki(i,arr):
    if i >= N:
        if (sum(arr)) % K == 0:
            print(*arr)
    else:
        for j in range(1,R[i] + 1):
            ar = arr + [j]
            saiki(i+1, ar)

saiki(0,[])

制約が緩いので全列挙で問題ないですね。
各桁の値をすべて試す処理を再帰関数で実装しました。
上の桁から順に値を配列に格納していき、すべての桁の値を格納しおえたらそれらの総和がKの倍数になっているか判定します。

D – Pedometer

湖を1周するようにN個の休憩所があり、それぞれ次の休憩所までの歩数が与えられます。
ある休憩所から別の休憩所まで時計回りで歩いた時、歩数がMの倍数となる組み合わせは何通りあるでしょうか？

解答(TLE)

import itertools
N, M = map(int, input().split())
A = list(map(int, input().split()))
A_ac = [0] + list(itertools.accumulate(A))

cnt = 0
for i in range(1,N):
    for j in range(i + 1, N + 1):
        if (A_ac[j - 1] - A_ac[i - 1]) % M == 0:
            cnt += 1
        if (A_ac[-1] - (A_ac[j - 1] - A_ac[i - 1])) % M == 0:
            cnt += 1

print(cnt)

前回記事にしたABC366のD問題でも使った累積和を使えば簡単な話…と思っていたのですがこの実装では実行時間2215 msと惜しくもTLE1でした。
累積和を作る段階で大きな数の足し算2を行っており、おそらくそこで時間がかかっていたのだと思います。
解説のコードでは累積和の作成を自前で実装しており、累積和作成時点でmodを取ることでM以上の値を扱わないようにしていました。

しかしコンテスト中の私は上記の実装で実行時間2215 msと惜しかったので、これはC++なら通るのでは？と思いChatGPT3にC++へ変換してもらうことにしました。過去にそういったことがあったのです。
しかし変換してもらったコードを提出してもWA4となってしまいました。手元にC++の実行環境がないためデバックもできずAIとの問答を行いながら提出を何度か行いましたが徒労に終わりました。

コンテスト結果

今回も悔しい結果になりました。初のレーティングマイナスです。
実はC問題の実装がぱっと思いつかなかったのでD問題に先に取り掛かったのですが、結局D問題も解けずコンテスト終了ギリギリでC問題の解答を提出しギリギリ3完で踏みとどまりました。
実装がぱっと思いつかないのはやはり精進5不足でしょう。精進します。

おわりに

次回はABC368の記事を投稿します。
本ブログを通じて私と一緒に競技プログラミングの世界を楽しんでいただければ幸いです。
また、各種ご支援させていただきますので、お気軽に「お問い合わせフォーム」よりお問い合わせください。

お問い合わせ
　業務実績　
  1. Time Limit Exceeded 実行時間超過 ほとんどの問題で実行時間制限は2秒に設定されている ↩︎
  2. Pythonでは数値の大きさに制限はありませんが数値が大きくなると計算に時間がかかります。 ↩︎
  3. 生成AIの使用はAtCoderのルール上認められています。 ※ただし問題を直接生成AIに渡すのはNG ↩︎
  4. Wrong Answer 出力結果が間違っていること ↩︎
  5. 過去問を解くことを意味する競プロ界隈のスラング ↩︎

関連記事