ABC357参加後振り返り

前書き

2024/3からAtCoderを始めました。
現職は、2年目の新人インフラSEです。
業務中では、実際に手を動かすとなると時間がかかるという場面が多く、
AtCoderを通して高パフォーマンスを出せるように実装力を磨きます。
使用言語はPython3です。

ABC 357 振り返り

全体を通しての感想

今回はA, B, C の3完でした。
C問題は、再帰的にカーペットを構成する関数を実装をする解法を選択して無事ACできました。問題を解くためにサブルーチンを書くこと自体になれていないので、再帰的な関数の実装をすることと合わせてとても良い演習になったと思います。
D問題については、過去に$${\mathbb F_p}$$の演算を実装したことがなかったので流用可能なソースが手元にない（※今回のコンテスト後に調べたところ”998244353"は素数なので、$${\mathbb Z / 998244353 \mathbb Z}$$は有限体となります。）時点ですでに辛かったのですが、問題を見た瞬間に等比級数の和の公式を使えば解けると閃かなかったのが（個人的な自身への評価の）大減点ポイントでした。反省。

A問題 -Sanitize Hands

問題
A - Sanitize Hands (atcoder.jp)

答案①（AC）
問題文の最後の一文の意味することがすぐに汲み取れなかったため、A問題の割にはてこずってしまいました。
ACしたコードでは、宇宙人が順に手を1本ずつ消毒していく様子をシミュレートする実装をしました。
（約12分）

#input
N,M=map(int,input().split())
H = list(map(int,input().split()))

#process
H2 = list(reversed(H)) #popで手の消毒が完了した宇宙人を列から外すために逆順にする。

#シミュレーション
for i in range(M):
    if len(H2) != 0 and H2[-1] > 1:
        H2[-1] -= 1
    elif len(H2) != 0:
        H2.pop()
    else:
        break

ans = len(H) -len(H2)

print(ans)

シミュレーション部分は（例外を扱う観点で順序依存する）andとelifで書くのではなく、以下のように実装するほうが読みやすいですが、実装を考えているときの思考はそうじゃないという点が不思議なところです。

シミュレーション
for i in range(M):
    if len(H2) != 0:
        if H2[-1] > 1:
            H2[-1] -= 1
        else:
            H2.pop()
    else:
        break

B問題 -Uppercase and Lowercase

問題
B - Uppercase and Lowercase (atcoder.jp)

答案（AC）
標準ライブラリで大文字に統一や小文字に統一といった操作ができるので、
大文字の文字数と全体の文字数を使って多数派を求めて条件分岐すればよいです。（約4分）

#define
#大文字の文字数を数えるサブルーチンを定義する。
def count_uppercases(string):
    return sum(1 for char in string if char.isupper())

# input
S = input()

# process & output
if count_uppercases(S) > len(S)// 2: #len(S)は奇数なので、S//2より多いほうが多数。
    print(S.upper())
else:
    print(S.lower())

C問題 - Sierpinski carpet

問題
C - Sierpinski carpet (atcoder.jp)

これです。
シェルピンスキーのカーペット - Wikipedia
レベル$${N=0,1,2}$$ぐらいでの近似では白い部分を囲う黒い部分があったりするので意外に思う人もいるのではないかと思うのですが、（一辺の長さが有限な）シェルピンスキーのカーペットは黒い部分の面積が（ルベーグ測度で）0です。実際、辺の長さを固定するとレベルが$${1}$$増えるごとに黒い部分面積が$${\dfrac 8 9}$$になるので、レベルを無限に大きくすれば黒い部分の面積は$${0}$$へと収束することが分かりますね。

答案①（AC）
主な制約は$${0\leq N \leq 6}$$であるため、$${O(9^N))}$$程度の処理は制限時間内で実行可能です。
以下のように再帰的にカーペットを構成する実装では、$${O(9^N))}$$の計算量でカーペットを生成して出力することができます。
（約 27 分）

# define
#与えられたレベルのカーペットを再帰的に生成するサブルーチンを定義する。
#カーペットのデータ型は、文字列の（1次元）リストとする。
def larger_carpet(level):
    if level == 0:
        return "#"
    else:
        temp=[]
        #carpetとして一つ下のレベルのカーペットを取得する。
        carpet = larger_carpet(level-1)
        
        #carpetを用いて与えられたレベルのカーペットを生成する。
        for i in range(len(carpet)):
            temp.append(carpet[i]+carpet[i]+carpet[i])
        for i in range(len(carpet)):
            temp.append(carpet[i]+('.'*len(carpet))+carpet[i])            
        for i in range(len(carpet)):
            temp.append(carpet[i]+carpet[i]+carpet[i])
        return temp

# input
N = int(input())

# process & output
#（Atcoderの空白は何でもよいが、）テスト実行時の見栄えのため改行区切りで結果を出力する。
print(*larger_carpet(N), sep='\n') 

後書き

D問題については、$${\mathbb F_p}$$の基本的な演算の実装をする際に取り組みます。（最近平日は忙しいけど何とか次のコンテストまでには間に合わせたい。。。）
拍手コメントを題材にした出題とニコニコへの大規模攻撃が重なったのは奇妙な偶然です。。。どうにか無事に復旧できますように。
あと来週のコンテスト（ABC358）は、当日の仕事の状況次第で不参加になるかもしれないです。順調に仕事が片付くといいなあ。