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

UNICORNプログラミングコンテスト2021(AtCoder Beginner Contest 225)の参加記録です。
コンテスト主催のUNICORNさんありがとうございます。

レート600前後のPython3を使用しているユーザです。
ABC225のA-C問題までを振り返る記事です。

A – Distinct Strings

標準入出力と条件分岐が書けるかが問われる問題。
私はコンテスト中はサボって、itertools.permitatoins() を使用しました。

3つの文字すべてが同じ場合、3つの文字の内2文字が異なる場合、3つの文字すべてが異なる場合について、それぞれ場合分けして答えを出力したらOKですね。

ここで、3つの文字の内、何個が同じかを確認する方法はいくつかありますね。
私であれば、set() を使って、setの要素の個数で判定すると思います。

# UNICORNプログラミングコンテスト2021(AtCoder Beginner Contest 225)
# A - Distinct Strings

S=set(input())
l=len(S)
if l == 1:
    print(1)
elif l == 2:
    print(3)
else:
    print(6)

3つの文字が、1種類の場合は、比較的簡単ですが、2種類、3種類の場合は判定式を書く分量が多くなって嫌ですね。

3つの文字が2種類からなっている場合は、ソートしてから、前二つが同じか、または、後ろ二つが同じかを判定したら、少しコードする分量が減って楽かもしれません。

S=list(input())
S.sort()
if S[0]==S[1]==S[2]:
    print(1)
elif S[0]==S[1] or S[1]==S[2]:
    print(3)
else:
    print(6)

私がコンテスト中に提出したコードは以下のコードです。場合分けをすることなく、ACすることが出来ました。

import itertools 

S=list(input())

p=set(itertools.permutations(S))

print(len(p))

B – Star or Not

繰り返し処理と、書かれている条件を満たすかどうかを判定すればよい問題ですね。
とはいっても、B問題でグラフが出てくるとは思いませんでした。

上にも書いた通り、書かれている条件を満たすかどうかを判定すればよいのですが、「うわっ。木とか知らんよ。」ってなった方も多いのではないかなと思います。

グラフをどう表すか。が一番の問題かと思います。
私は、『 アルゴリズム実技検定 公式テキスト[エントリー~中級編] 』 (通称PAST本) で学びました。

頂点に接続している辺の数がN-1の頂点があるかを判定すればよいですね。

# UNICORNプログラミングコンテスト2021(AtCoder Beginner Contest 225)
# B - Star or Not

N=int(input())

G=[[]for i in range (N)]
for _ in range (N-1):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

for v in G:
    if len(v) == N-1:
        print("Yes")
        exit()

print("No")

C – Calendar Validator

条件に合う行列Aと、入力で与えられる行列Bを比較して、行列Bが行列Aから切り出された行列であるかを確認する問題。

行列Aとは、1行目には1から7までの数字が書かれており、2行目には8から14まで、3行目は15から21まで…と続く行列です。

以下、この問題を解く方針を以下の通り考えました。

• 行列Bの左上の数字と、N,Mから、行列Aのどの部分かを調べます。
• N=1, M=2 で、B = [ 7, 8 ]　といった行列の場合にNG判定しないとダメなことに注意します。
  (この判定が不十分でWAを出しました。)
• あとは、左上を揃えたM個の要素を持つ配列Aを作成し、行列Bの1行目が一致しているかを判定する。
• 2行目以降も同様に判定していく。
• 途中でNG判定をした際には、”No”を出力してプログラムを終了させる。
• 最後までNG判定にならなかったら”Yes”を出力する。

以上を丁寧にコードに書いていくとACします。

# UNICORNプログラミングコンテスト2021(AtCoder Beginner Contest 225)
# C - Calendar Validator

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

# 行列Bの1行目を読み込む
B_row1 = list(map(int,input().split()))
left_top = B_row1[0]
# 行列Bが行列Aのどの位置から開始しているかを調べる
# d : 開始行
# m : 開始列
d,m = divmod(left_top, 7)

# 行列Bが存在するはずの列より、Mが大きい場合は"No"を出力して終了
if m == 0:
    if M > 1:
        print("No")
        exit()
if M > 8 - m:
    print("No")
    exit()


# 行列Aのd行目(列幅はM)を作成して、行列Bの1行目と一致するか確認
A_row1 = []
for i in range (M):
    A_row1.append(d*7+m+i)
if A_row1 != B_row1:
    print("No")
    exit()


# 行カウンターを次(2行目)に進める
d += 1

# 行列Bの2行目以降を確認していく
for i in range (N-1):
    Ai = []
    for j in range (M):
        Ai.append(d*7+m+j)
    input_line = list(map(int,input().split()))
    if Ai == input_line:
        d += 1
        continue
    else:
        print("No")
        exit()

# 全ての入力で"No"と判定されていない場合は"Yes"を出力
print("Yes")