モノグサプログラミングコンテスト2022（ABC238）参戦記

仕事やAHC008に時間を割いていて、ABCの復習を怠っていたため、ABC238からの復習をすすめます。
本記事は、モノグサさんが主催のABC238の参加記録です。
使用言語はPython3、レートは800程度です。(参加時点では緑、書いている時点では茶です。)
私が理解できる内容でしか書いていないので、高度なことは書けません。

A – Exponential or Quadratic

標準入出力と、正しく条件分岐が書けますか。が問われる問題。
(Python3の言語特性(？)を知っていますか。が問われる問題でもあると思います。）

問題文に書いてある通りの条件式である if 2N > N2: これが、Trueの時、”Yes” を出力し、False の時、”No”を出力すればOKですね。

n = int(input())
if 2**n > n**2:
    print("Yes")
else:
    print("No")

但し、このプログラムをPython3で提出すると、TLE(実行時間超過)により、AC(正解)出来ません。Python3の言語特性ですね。
同じコードのまま、PyPy3や、Cythonで提出するとACします。

より、正しく(？)答えを判定するためには、2ⁿ > n² となる条件を探せばよいですね。

手で計算しても良いですし、for文が書ければプログラムで上記の条件を探すプログラムを書いてみれば良いですね。

for i in range(50):
    print("{} : 2^N > N^2 ? => {} (2^N={}, N^2={})".format(str(i).zfill(2),2**i>i**2,2**i,i**2))
# 00 : 2^N > N^2 ? => True (2^N=1, N^2=0)
# 01 : 2^N > N^2 ? => True (2^N=2, N^2=1)
# 02 : 2^N > N^2 ? => False (2^N=4, N^2=4)
# 03 : 2^N > N^2 ? => False (2^N=8, N^2=9)
# 04 : 2^N > N^2 ? => False (2^N=16, N^2=16)
# 05 : 2^N > N^2 ? => True (2^N=32, N^2=25)
# 06 : 2^N > N^2 ? => True (2^N=64, N^2=36)
# 07 : 2^N > N^2 ? => True (2^N=128, N^2=49)
# 08 : 2^N > N^2 ? => True (2^N=256, N^2=64)
# 09 : 2^N > N^2 ? => True (2^N=512, N^2=81)
# 10 : 2^N > N^2 ? => True (2^N=1024, N^2=100)
# 11 : 2^N > N^2 ? => True (2^N=2048, N^2=121)
# 12 : 2^N > N^2 ? => True (2^N=4096, N^2=144)
# 13 : 2^N > N^2 ? => True (2^N=8192, N^2=169)
# 14 : 2^N > N^2 ? => True (2^N=16384, N^2=196)
# 15 : 2^N > N^2 ? => True (2^N=32768, N^2=225)
# 16 : 2^N > N^2 ? => True (2^N=65536, N^2=256)
# 17 : 2^N > N^2 ? => True (2^N=131072, N^2=289)
# 18 : 2^N > N^2 ? => True (2^N=262144, N^2=324)
# 19 : 2^N > N^2 ? => True (2^N=524288, N^2=361)
# 20 : 2^N > N^2 ? => True (2^N=1048576, N^2=400)
# 21 : 2^N > N^2 ? => True (2^N=2097152, N^2=441)
# 22 : 2^N > N^2 ? => True (2^N=4194304, N^2=484)
# 23 : 2^N > N^2 ? => True (2^N=8388608, N^2=529)
# 24 : 2^N > N^2 ? => True (2^N=16777216, N^2=576)
# 25 : 2^N > N^2 ? => True (2^N=33554432, N^2=625)
# 26 : 2^N > N^2 ? => True (2^N=67108864, N^2=676)
# 27 : 2^N > N^2 ? => True (2^N=134217728, N^2=729)
# 28 : 2^N > N^2 ? => True (2^N=268435456, N^2=784)
# 29 : 2^N > N^2 ? => True (2^N=536870912, N^2=841)
# 30 : 2^N > N^2 ? => True (2^N=1073741824, N^2=900)
# 31 : 2^N > N^2 ? => True (2^N=2147483648, N^2=961)
# 32 : 2^N > N^2 ? => True (2^N=4294967296, N^2=1024)
# 33 : 2^N > N^2 ? => True (2^N=8589934592, N^2=1089)
# 34 : 2^N > N^2 ? => True (2^N=17179869184, N^2=1156)
# 35 : 2^N > N^2 ? => True (2^N=34359738368, N^2=1225)
# 36 : 2^N > N^2 ? => True (2^N=68719476736, N^2=1296)
# 37 : 2^N > N^2 ? => True (2^N=137438953472, N^2=1369)
# 38 : 2^N > N^2 ? => True (2^N=274877906944, N^2=1444)
# 39 : 2^N > N^2 ? => True (2^N=549755813888, N^2=1521)
# 40 : 2^N > N^2 ? => True (2^N=1099511627776, N^2=1600)
# 41 : 2^N > N^2 ? => True (2^N=2199023255552, N^2=1681)
# 42 : 2^N > N^2 ? => True (2^N=4398046511104, N^2=1764)
# 43 : 2^N > N^2 ? => True (2^N=8796093022208, N^2=1849)
# 44 : 2^N > N^2 ? => True (2^N=17592186044416, N^2=1936)
# 45 : 2^N > N^2 ? => True (2^N=35184372088832, N^2=2025)
# 46 : 2^N > N^2 ? => True (2^N=70368744177664, N^2=2116)
# 47 : 2^N > N^2 ? => True (2^N=140737488355328, N^2=2209)
# 48 : 2^N > N^2 ? => True (2^N=281474976710656, N^2=2304)
# 49 : 2^N > N^2 ? => True (2^N=562949953421312, N^2=2401)
# 50 : 2^N > N^2 ? => True (2^N=1125899906842624, N^2=2500)

上記を確認すると、nが十分大きくなれば 2ⁿ のほうが n² より大きくなることがわかります。

問題文の条件である、2ⁿ > n² がFalseになるnの範囲は、2以上4以下であることも分かります。

この場合分けを出力すればPythonでもACします。

print("No") if 2<=int(input())<=4 else print("Yes")

私は、コンテスト中は、nが10以上の場合は、”Yes”を出力し、それ以外の場合は、条件式を問題文にある通り判定するプログラムを書いて提出しました。

# モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 238）
# A - Exponential or Quadratic

n = int(input())

if n > 10:
    print("Yes")
else:
    if 2**n > n**2:
        print("Yes")
    else:
        print("No")

B – Pizza

愚直なシミュレーションが出来るかが問われる問題。

ここ最近のB問題の中でも特別難しいように思いました。

私が取った方針は、切れ目の入っている角度が入っている配列を用意して、次に進むたびに、配列の中身全てに回転した角度を足していく。切れ目がすべて入ったら、角度の差の最大値を求め、それを出力する。というものです。

# モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 238）
# B - Pizza

N = int(input())
A = list(map(int,input().split()))

cuts = [0]

# Aに入っている要素をa度回転させていく。
for a in A:
    # 今までの切れ目をa度回転させる
    for i in range (len(cuts)):
        cuts[i] += a
        cuts[i] %= 360
    cuts.append(0)

# 最後のピースが終わる角度を追加
cuts.append(360)
cuts.sort()

# 角度の差の最大値を更新していく。
ans = 0
for i in range (len(cuts)-1):
    ans = max(ans, abs(cuts[i+1]-cuts[i]))

print(ans)

あとから知りましたが、切る角度自体を更新していって、切れ込みを入れる方針のほうが賢いですね。

N = int(input())
A = list(map(int,input().split()))

cuts = []
nowdeg = 0
cuts.append(nowdeg)
for a in A:
    nowdeg += a
    nowdeg %= 360
    cuts.append(nowdeg)

# 最後のピースが終わる角度を追加
cuts.append(360)
cuts.sort()

# 角度の差の最大値を更新していく。
ans = 0
for i in range (len(cuts)-1):
    ans = max(ans, abs(cuts[i+1]-cuts[i]))

print(ans)

C – digitnum

もっと賢い方法があることも見ましたが、私が理解できる文章にはできなかったため、愚直に場合分けする方針で書きます。

桁数が同じ場合だけで考えたく、桁数が同じ場合は、等差が1の等差数列なので、合計は N*(N+1)//2 で求まりますね。あとは、ひたすら桁を同じにするための場合分けを書いて、下位の桁については、再帰させて答えを求めました。

# モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 238）
# C - digitnum

"""
桁数が同じ部分に関してだけ考えたい。
下位の桁に関しては、下位の桁に問題を分割して考える。
"""

def f(n):
    mod = 998244353
    res = 0

    # 1桁の時
    if n < 10:
        res += (n*(n+1))//2
        res %= mod

    # 2桁の時
    elif n < 100:
        res += f(9)
        n -= 9
        res += (n*(n+1))//2
        res %= mod

    # 3桁の時
    elif n < 1000:
        res += f(99)
        n -= 99
        res += (n*(n+1))//2
        res %= mod

    # 4桁の時
    elif n < 10000:
        res += f(999)
        n -= 999
        res += (n*(n+1))//2
        res %= mod

    # 5桁の時
    elif n < 100000:
        res += f(9999)
        n -= 9999
        res += (n*(n+1))//2
        res %= mod

    # 6桁の時
    elif n < 1000000:
        res += f(99999)
        n -= 99999
        res += (n*(n+1))//2
        res %= mod

    # 7桁の時
    elif n < 10000000:
        res += f(999999)
        n -= 999999
        res += (n*(n+1))//2
        res %= mod

    # 8桁の時
    elif n < 100000000:
        res += f(9999999)
        n -= 9999999
        res += (n*(n+1))//2
        res %= mod

    # 9桁の時
    elif n < 1000000000:
        res += f(99999999)
        n -= 99999999
        res += (n*(n+1))//2
        res %= mod

    # 10桁の時
    elif n < 10000000000:
        res += f(999999999)
        n -= 999999999
        res += (n*(n+1))//2
        res %= mod

    # 11桁の時
    elif n < 100000000000:
        res += f(9999999999)
        n -= 9999999999
        res += (n*(n+1))//2
        res %= mod

    # 12桁の時
    elif n < 1000000000000:
        res += f(99999999999)
        n -= 99999999999
        res += (n*(n+1))//2
        res %= mod

    # 13桁の時
    elif n < 10000000000000:
        res += f(999999999999)
        n -= 999999999999
        res += (n*(n+1))//2
        res %= mod

    # 14桁の時
    elif n < 100000000000000:
        res += f(9999999999999)
        n -= 9999999999999
        res += (n*(n+1))//2
        res %= mod

    # 15桁の時
    elif n < 1000000000000000:
        res += f(99999999999999)
        n -= 99999999999999
        res += (n*(n+1))//2
        res %= mod

    # 16桁の時
    elif n < 1000000000000000:
        res += f(99999999999999)
        n -= 99999999999999
        res += (n*(n+1))//2
        res %= mod

    # 17桁の時
    elif n < 10000000000000000:
        res += f(999999999999999)
        n -= 999999999999999
        res += (n*(n+1))//2
        res %= mod

    # 18桁の時
    elif n < 100000000000000000:
        res += f(9999999999999999)
        n -= 9999999999999999
        res += (n*(n+1))//2
        res %= mod

    # 19桁の時(念のため)
    elif n < 1000000000000000000:
        res += f(99999999999999999)
        n -= 99999999999999999
        res += (n*(n+1))//2
        res %= mod

    return res


N = int(input())
print(f(N))