NECプログラミングコンテスト2021(ABC229)参戦記

NECさん主催のABC229の参戦記です。

最近は、企業主催のABCが多くなってきていますね。主催の各企業さん、運営のAtCoderさんありがとうございます。

このブログ記事は、レート600台の私が自分の理解を書いていくものです。使用言語はPython3です。C問題までのACコード付きです。

A – First Grid

標準入出力と条件分岐が書けるかが問われる問題。

最近、A問題が難しくなっているように思うのですが、どうなのでしょうかね。
この問題も状況を整理しないと解けないと思います。

4マスしかないため、全てのパターンについて確認するのが一番早いと思います。

"""

'#'が4つの場合
##
##

'#'が3つの場合
##  ##  #.  .#
#.  .#  ##  ##

'#'が2つの場合
##  ..  .#  #.  #.  .#
..  ##  .#  #.  .#  #.

"""

このうち、Noを出力するケースは、上記の最後の2パターンだけですね。

つまり、
S1が ” #. ” の場合は、S2が ” .# ” の時
S1が ” .# “の時は、S2が ” #. ” の時
これらの場合に”No” を出力すればOKです。

私がコンテスト中に出したのは、以下のようなコードで通しています。

# NECプログラミングコンテスト2021(AtCoder Beginner Contest 229)
# A - First Grid

S1=input()
S2=input()

if S1==".#":
    if S2=="#.":
        print("No")
    else:
        print("Yes")
elif S1=="#.":
    if S2==".#":
        print("No")
    else:
        print("Yes")
else:
    print("Yes")

if文がネストして読みにくいですね。もう少し整理して、読みやすくしました。

S1=input()
S2=input()

if (S1=="#." and S2==".#") or (S1==".#" and S2=="#."):
    print("No")
else:
    print("Yes")

B – Hard Calculation

繰り返し処理が書けるかが問われる問題。

私は、この問題は以下の方針で解きました。

• AとBを受け取る。この際、str型で受け取る。(後で、str型の処理をするため。)
• 桁のサイズを合わせるために、大きいほうの桁のサイズを取得する。
• 桁のサイズを合わせる。(足りない分は0で埋める。( str.zfill() を利用する。)
• 数値として扱うために、各桁をint型にして、配列でデータを持つ。
• AとBの各桁を足した数が10以上になっていたら繰り上がりがある計算として “Hard” を出力して、プログラムを終了( exit() )する。

# NECプログラミングコンテスト2021(AtCoder Beginner Contest 229)
# B - Hard Calculation

# 文字列で受け取る
A,B=map(str,input().split())

# 大きい桁数を取得する
maxlen=max(len(A),len(B))

# 桁数を合わせる(0埋めする)
AA=A.zfill(maxlen)
BB=B.zfill(maxlen)

# intとして、listにデータを持つ
AA=list(map(int,AA))
BB=list(map(int,BB))

for i in range (maxlen):
    # それぞれのi番目を足す
    c = AA[i] + BB[i]
    # 10以上なら"Hard"を出力しexit()する
    if c >=10:
        print("Hard")
        exit()

# 最後まで"Hard"ではなければ"Easy"を出力
print("Easy")

C – Cheese

貪欲に答えを更新していく問題。

好きな種類のチーズから順に可能な限り使用していくのが最適です。
ナップサックDPを選択しそうになりますが、1g単位でもチーズを使用できるため、好きなチーズを貪欲に使用していけば良いですね。

以下、この問題を解く方針です。

• チーズを好きな順番にソートする。
• 以下の繰り返し処理を行う。
  • そのチーズ全部を使用してもW以下なら全部使う。
    • 使って得られる美味しさを答え用の変数に加える。
  • 全部使うとWを越してしまう場合には、Wになるまで使う。
    • 使って得られる美味しさを答え用の変数に加える。
• 答えを出力する。

# NECプログラミングコンテスト2021(AtCoder Beginner Contest 229)
# C - Cheese

N, W=map(int,input().split())

cheese=[]
for i in range (N):
    A, B=map(int,input().split())
    cheese.append([A,B])

cheese.sort()

now_W = 0
ans = 0

while now_W < W :
    if len(cheese) == 0:
        break

    cA, cB = cheese.pop()
    if now_W + cB <=W:
        now_W += cB
        ans += cA*cB
    else:
        cB = W - now_W
        now_W += cB
        ans += cA*cB

print(ans)