ABC358参加後振り返り

前書き

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

ABC 358 振り返り

全体を通しての感想

今回はA, B, C の3完でした。良かったこともあり、悪かったこともあってこの結果だったと受け止めています。でも、もっとパフォーマンスを出せたと思っているので内心忸怩たる思いです。

さて、まず良かった点ですが、C問題について、解き始める時点で全探索でも十分間に合うことを意識できていたことです。指数時間でも間に合う場合があるというABC356のC問題での学びが生きたと思います。

悪かった点は、デバッグのやり方です。
C問題を解く際にロジックでの間違いばかりを疑ってしまったために、
変数の取り違えの可能性に思い至るまでにコンテスト時間の大半を使ってしまいました。（その上D問題でも同じ過ちを重ねて提出できずじまいに。。。）そういえば直近の業務でも、他人の書いたスクリプトのデバッグをする際に変数名の書き間違いの可能性を考慮できずにハマるという経験をしていて、めちゃくちゃデジャビュでした。経験に学べというプログラミングの神（？）の思し召しでしょうか。

手を付ける時間がありませんでしたが、E問題は有限体上の二項係数の計算の問題でしたね。ぼちぼちD,E問題に挑戦することもあると思うので、有限体上の計算用のライブラリはそのうち作らないとですね。

A問題 - Welcome to AtCoder Land

問題
A - Welcome to AtCoder Land

問題文の引用ブロックの部分でストーリーの説明があるのは面白かったです。こういうストーリー性がある問題セットがたまにあるとワクワク感があって嬉しいですね。

答案①（AC）
素直な実装のつもりだったのですが、冷静に振り返ると無駄が多いですね。
（とくに、input().split()がもともとリスト型なのにlist()で無駄なキャストをしているところはイケてないです。）
（約2分）

#input
ST=list(input().split())

#process & output
if ST[0]=="AtCoder" and ST[1]=="Land":
    print("Yes")
else:
    print("No")

答案②（AC）
この内容ならワンライナーで実装できますね。

print("Yes" if input() == "AtCoder Land" else "No")

B問題 - Ticket Counter

問題
B - Ticket Counter (atcoder.jp)

答案（AC）
シュミレーションで解きました。
チケットカウンターで順番待ちをしている人がいるかいないかによって、処理を場合分けするのが実装のポイントです。（約5分）

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

#process & output
ans = 0
for t in T:
    #Ticket Counterで順番待ちの人がいない場合
    if ans < t:
        ans = t + A
        print(ans)
    #Ticket Counterで順番待ちの人がいる場合
    else:
        ans += A
        print(ans)

C問題 - Popcorn

問題
C - Popcorn (atcoder.jp)

前書きにてデバッグでハマった話をしましたが、他にもハマったポイントはあって、Pythonの or 演算子と | 演算子の違いにハマりました。
自分の検索用に or 演算子と | 演算子の違いを整理しておきます：

# or 演算子... 論理評価としてのorの短絡評価を実行する。
5 or 3     # 5 （Pythonでは0以外の整数が真なので、5 or 3 を短絡評価して 5 を返す）

# | 演算子 ... bit演算のorを実行する。
5 | 3      # 7 （0b101と0b011のbit演算としての or を実行し、0b111 を返す）

答案①（AC）
主な制約は$${0\leq N, M \leq 10}$$であり、$${O(N\cdot 2^N)}$$の処理は充分高速に動作します。
解法は全探索です。
特定のフレーバーの有無をバイナリで管理することにすると、
「売り場の中に特定のフレーバーがあること」
と
「bit演算で or をとったら 特定のフレーバー有無を管理する桁が 1」
になることが同値なので、これを用いて全てのフレーバーをコンプリートしているか判定することができます。
テストケースをビットカウントすることで回った売り場の数を求められるのでこの min を（逐次的に）取ることで答えが得られます。

ちなみに、デバッグでハマった点ですが、NとMを1箇所書き間違えたために
WAが2個だけ発生して「???????」となりました。修正大変だった。。。

（約 65 + 2WA 分）

#define
# o, x を 1, 0 に変換するサブルーチン
def convert_to_binary(s):
    binary_string = ""
    for char in s:
        if char == 'o':
            binary_string += '1'
        elif char == 'x':
            binary_string += '0'
    return int(binary_string, 2)

#input
N,M = map(int,input().split())
# 入力時に、S はバイナリに変換しておく。
S = [convert_to_binary(input()) for i in range(N)]

#process
ans = N
# i で寄った売店を管理する。例えば、0b011 に 「S_1 と S_2 に寄った」ケースを対応させる。
for i in range(2**N):
    # temp でフレーバーのコンプリート状況を管理する。
    temp = 0
    for j in range(N):
        # j 個右シフトして、 1 でマスクすることで 2^jの位の 0 or 1 を取り出す。
        # 1 なら売店S_{j+1}に寄っているので、S[j]とbit演算（or）をする。
        if(i>>j)& 1:
            temp = temp | S[j]

    # 全てのフレーバーをコンプリート出来た場合に、寄った売店数の最小値の更新をする。
    if temp == 2**M-1 and ans > bin(i).count('1'):
        ans = bin(i).count('1')

#output
print(ans)

D問題 - Souvenirs

問題
D - Souvenirs (atcoder.jp)

答案①（AC ※コンテスト後）
順々に人になるべく小さい箱を渡した結果が答えとなることに気が付けば、後はそれを実装するだけです。

以下は最初にACを取ったコードを少し見栄えを良くしたものです。
途中で不可能となる場合の処理は気を付けないと簡単にSegmentation Faultを引き起こすのが厄介ですね。

#input
N,M = map(int,input().split())
A = list(map(int,input().split())) # 箱の価格＝内容物の個数リスト
B = list(map(int,input().split())) # 人に渡す個数リスト

#process
A.sort(reverse=True)
B.sort()

ans = 0
for b in B:
    # 人b に渡すには中身が少なすぎる箱をすべてpopする。
    while len(A) != 0 and A[-1] < b:
        A.pop()
    # 人b に箱を渡せない場合の処理
    if len(A) == 0:
        ans = -1
        break
    # 人b に箱を渡す処理
    else:
        ans += A[-1]
        A.pop()

#output
print(ans)

答案②（AC ※コンテスト後）
もちろん、慎重にロジックを組むことでSegmentation Faultを起こさないということは実行不可能ではないですが、考える必要があること・コードの記述がどちらも増えてしまいます。そんな問題を回避するために、例外処理を上手く使ってシンプルに記述していきたいですね。
今後のコンテストでは積極的に例外処理を使えるように、練習をしていきたいと思います。

#input
N,M = map(int,input().split())
A = list(map(int,input().split())) # 箱の価格＝内容物の個数リスト
B = list(map(int,input().split())) # 人に渡す個数リスト

#output
A.sort(reverse=True)
B.sort()

ans = 0
for b in B:
    #まだ人がいるのに渡せる箱がなくなってしまった場合は、まとめて例外で処理。
    try:
        while A[-1] < b:
            A.pop()
        ans += A[-1]
        A.pop()
    except IndexError:
        ans = -1
        break

#output
print(ans)

後書き

レーティングについてはこれまでブログでは触れてきませんでしたが、300台に乗って、もう少しで茶色というところまで来ました。入茶まではコンテストを続けて、そのあとはどうしようか、といったところです。
（入緑するには、ちょっと知識・演習不足を感じますし、他にも勉強すべきことはいろいろあります。）
コンテストの参加記録ではなく直近の茶～水diff演習の振り返りを行ったり、資格勉強の演習とか、その他に興味があることについて書くようになるかもしれません。
なんにせよ茶色まではもうちょいのはずで、それまでは精一杯やっていきますのでよろしくお願いします。
来週のコンテスト（ABC359）は、休日出勤なので状況次第です。順調に仕事が終わることを祈っていただけると嬉しいです。