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")
コメント