サントリープログラミングコンテスト2024（AtCoder Beginner Contest 357）

都合により不参加

atcoder.jp

A - Sanitize Hands
B - Uppercase and Lowercase
C - Sierpinski carpet
D - 88888888

A - Sanitize Hands

リンク：A - Sanitize Hands (atcoder.jp)

概要：宇宙人の手を消毒しよう！

いくつか方針が考えられますが、私は以下で解きました。

宇宙人の手の本数で累積和をつくる
累積和を順に見ていって消毒液のほうが多い場合は答えを更新する
その地点の一つ前を出力する

他にはwhile文で消毒液を消費していって量がマイナスになったら答え出力とかできそうです。

#ABC357 A - Sanitize Hands
N, M = map(int, input().split())
H = list(map(int, input().split()))
s = 0
ruiseki = [0]
for i in range(N):
    s += H[i]
    ruiseki.append(s)
ans = 0
for i in range(N+1):
    if ruiseki[i] <= M:
        ans = max(i, ans)
print(ans)

提出リンク：提出 #54457944 - サントリープログラミングコンテスト2024（AtCoder Beginner Contest 357）

B - Uppercase and Lowercase

リンク：B - Uppercase and Lowercase (atcoder.jp)

概要：文字列 $S$ の小文字と大文字の数を比較してね

pythonではisupper・islowerで大文字・小文字を判定できます。

またS.upper()で文字列 $S$ を大文字に変換できます。

#ABC357 B - Uppercase and Lowercase
S = input()
small = sum(map(str.islower, S))
large = sum(map(str.isupper, S))
if small > large:
    ans = S.lower()
else:
    ans = S.upper()
print(ans)

提出リンク：提出 #54458028 - サントリープログラミングコンテスト2024（AtCoder Beginner Contest 357）

C - Sierpinski carpet

リンク：C - Sierpinski carpet (atcoder.jp)

概要：独特な模様のカーペットをつくろう

再帰で解けそうな気がしましたが辛くなったので周期性を探しました。

レベル1のときは中心(1,1)だけ白になります。

レベル2のときは中心(4,4)まわりの3×3マスが白くなります。

レベル3のときは中心(13,13)まわりの9×9マスが白くなります。

中心座標を見ると1, 1+3, 1+3+9,……のように3進数が見えてきます。

方針として以下のようにしました。

n=1, 2,……の順にみる。
中心点のために $s = \displaystyle \sum_{k=1}^{n} 3^{k}$ を計算する。また前回の値をpreとして保持しておく。
中心点まわりの(-pre, +pre)の範囲を白く塗る。

これが灰diffってマジですか・・・いや問題文通りの実装なんだけども

#ABC357 C - Sierpinski carpet
N = int(input())
if N == 0:
    print('#')
    exit()
carpet = [[0 for _ in range(3**N)] for _ in range(3**N)]
s = 0
for n in range(1, N+1):
    pre = s
    s += 3**(n-1)
    for i in range(s, 3**N, 3**n):
        for j in range(s, 3**N, 3**n):
            for dy in range(-pre, pre+1):
                for dx in range(-pre, pre+1):
                    carpet[i+dx][j+dy] = 1
for i in range(3**N):
    out = ''
    for j in range(3**N):
        if carpet[i][j] == 0:
            out += '#'
        else:
            out += '.'
    print(out)

提出リンク：提出 #54481731 - サントリープログラミングコンテスト2024（AtCoder Beginner Contest 357）

D - 88888888

リンク：D - 88888888 (atcoder.jp)

概要：整数 $N$ を $N$ 個つなげた数 $V_N$ を998244353で割った数を出力してね

$V_N$ は等比級数の和として表すことができます。

具体的には $N$ の桁数を $k$ とすると $V_N = N \times \dfrac {10^{k \times N}-1}{10^{k}-1}$ で表せます。

また $\dfrac {a}{b}mod(M)$ は $a(mod(M)) \times b^{M-2}(mod(M))$ で表すことができます。

鍵となるのは $10^{k \times N}$ の高速な計算だと思います。

pythonではpow()で繰り返し二乗法による高速な計算が使え、またpow()の第3引数を使うと都度modをとってくれます。

方針をまとめると下記になります。

$V_N$ を等比級数の和として表現する
フェルマーの小定理より割り算modを掛け算の形で計算する
pow()で桁数の多いべき乗計算を高速に行う。同時にmodをとる

#ABC357 D - 88888888
N = int(input())
k = len(str(N))
mod = 998244353
a = pow(10, k*N, mod)-1
b = pow(10**k - 1, mod-2, mod)
ans = (N*a*b)%mod
print(ans)

提出リンク：提出 #54461153 - サントリープログラミングコンテスト2024（AtCoder Beginner Contest 357）