AtCoder Beginner Contest (ABC) 225 Pythonで参戦しました。 AB二完 C問題まで解説あり
前回の参戦
こんにちは。メリーです。
今回も参戦しましたAtCoder Beginner Contest (abc) 225。
結果はABまで解けて、C問題は解けませんでした。
なんか、WAが5つくらい出て、原因が特定できず・・・・。
C問題の問題量足りないのかなぁ。。。
というわけでレポート＆解説記事です。
言語はPython、提出はPyPyです。
目次
A問題
問題文
3文字からなる文字列が与えられ、それを並び替えてできる文字列は何通りあるかという問題。
これをもうちょっと難しくした問題をどこかのC問題あたりで見た気がするなぁ。
「馬鹿正直にfor文で全パターン作ればええやん」、と思うと、入力例1や2のパターンの時に重複した文字列が作られてしまう。
なので、何種類の文字が使われているかを数える必要がある。
この場合は、1種類、2種類、3種類の3通りしかないので、単純な場合分けでもok。
また、数学が得意なのであれば、同じものを含む順列を計算してもok。
なので方針は、
1. inputした文字列に含まれる文字列の種類を数える。
2. 種類によって場合分けして出力
2'. 同じものを含む順列を出力
という感じでやりました。
実際のコードがこちら。
ver. 場合分け
s = input()
s = set(s)
if len(s) == 1:
print(1)
elif len(s) == 2:
print(3)
else:
print(6)
考えられるのは、
文字の種類が1種類、2種類、3種類の場合のみ。
各場合における並び替えて得られる文字列は、それぞれ、
1つ、3つ、6つ。
※入力例にそれぞれのパターンの具体例載ってます。
なので、場合分けして出力して終了。
ver. 順列
import math s = input() s = set(s) a = -1 ans = math.factorial(3) // math.factorial(4-len(s)) print(ans)
同じものを含む順列の計算方法は、
n! ÷ (p!q!r!) // nは文字の総数。p,q,rはそれぞれの文字の数
で表される。
例えば、与えられた文字列が「aab」の場合、
3文字なので、
n = 3
aが2文字、bが1文字なので
p = 2, q = 1, r =0
よって、求めるのは
3! ÷ (2!1!0!) = 3
となる。
この問題では、nが固定(3)で、分母のp!q!r!が変化していく。
文字が3種類のときは1!、2種類の時は2!、1種類の時は3!になるように分母を変化させていく。
それをコードにすると、math.factorial(4-len(s))で表せる。
※math.factorial(n)でn!を表す。
そして、それを計算して出力して終了である。
B問題
問題文
N個の点とN-1個の線分が与えられます。
スターは存在するかどうか判別してください。という問題。
スターというのは、1つの点から他のすべての点に線分が引いてあるものです。
ということを問題文では、専門用語の木を使って表現してるってことですね。
正直、木って言われて頭の中「？？？？？？？？」でした。
そして、問題文をよくよく読んでいくと、線分がN-1本しか引けなく、頂点がN個しかないのであれば、スターである場合、線分の両端のどっちかには必ず共通した点が存在するはずです。
余分な線分を引いてる余裕がないのです。
赤線が引けるのであれば、点1が他の点すべてに線分を引けてるので、スターなのですが、線は3本までしか引けないので`スターにはなり得ません。
なので、全ての線分の両方をチェックして、1つでも点1が含まれない線があれば、点1から他のすべての点に線が引いてあるスターではないのです。
これを利用して、全ての点おいて調べる（全探索）すれば、スターかどうか判別できます。
よって、方針は、
1. すべての点において全探索する。
2. ある点について、全ての線分について全探索する。
3. 条件を満たした(すべての線分で、両端のどちらかにある点があった)場合フラグを立てる
4, フラグによって出力を変化
という形です。
というわけでコード↓
n = int(input())
a = []
b = []
for i in range(n-1):
A,B = map(int,input().split())
a.append(A)
b.append(B)
flg = 0
for i in range(1,n+1):
for j in range(n-1):
if a[j] != i and b[j] != i:
break
else:flg = 1
if flg:
print("Yes")
else:
print("No")
コードのメインはここです。
for i in range(1,n+1):
for j in range(n-1):
if a[j] != i and b[j] != i:
break
else:flg = 1
最初のfor文のiは各点についての全探索をしてます。
各点が1始まりなので、rangeが1から始まってます。
次のfor文のjは各線分についての全探索です。
点iが線分の両端どちらにもなければ、（if a[j] != i and b[j] != i:を満たせば、）breakで、次の点i+1にうつります。
また、全ての辺のどちらかに点iが存在した場合、（for j のループが正常に終了し、elseが実行されるとき）flgを1にします。
そして、最後にflgが1の場合(すべての辺のどちらかに点iが存在した場合)はYes、flgが0の場合はNoを出力して終了です。
C問題 コンテスト中編
問題文
どでかい行列Aが存在する。
また、それよりは小さい行列Bも与えられる。
さて、行列Bは行列Aの一部でしょうか？？
という問題。
これ、コンテスト中にACできなかったんですよね・・・。
コンテスト中にやったコードがこちら。
n,m = map(int,input().split())
b = []
for i in range(n):
B = list(map(int,input().split()))
b.append(B)
flg = 1
for i in range(n):
if flg == 0:
break
for j in range(m):
if j < m-1:
if b[i][j+1] - b[i][j] != 1:
flg = 0
break
else:
if i < n-1:
if (b[i+1][0] - b[i][0] != 7):
flg = 0
break
if flg:
print("Yes")
else:
print("No")
このコードでやったことは、
1. 1つ横の要素と比較して、差が1であること
2. 1つ下の要素と比較して、差が7であること
3. 1,2のどちらでもないとき、flgを0にする
4. flgによって出力を変化
です。
問題を見る感じ、行列Aは縦を比較すると差が7で、横を比較すると差が1になるようです。
なので、行列Bも、縦と横を比較していって、それぞれ差が7と1になれば行列Aと同じだよな～～って思って、このコードにしました。
んで、このコードで提出したんですけど、なぜかWAが5個くらい出てきました。
うーん、何が間違ってるんだろう・・・。
考えたけどわからなかったので、諦めました。
C問題 コンテスト後編
というわけでコンテストが終わり、解説を見てみました。
自分に足りなかったのは以下の点でした。
- 一番右側の縦の要素以外で、7の倍数があってはいけない
この制約を問題文から読み取ることができませんでした。
実は、この問題、行列Aはこんな感じになっていたのです。
なので、以下のような行列Bは許されないのです。
この行列Bは、行列Aの一部分ではないですよね。
なので、こう言った行列をはじくために、制約
- 一番右側の縦の要素以外で、7の倍数があってはいけない
が、必要なのです。
というわけで、改めて、方針は
1. 1つ横の要素と比較して、差が1であること
2. 1つ下の要素と比較して、差が7であること
3. 7の倍数が含まれる場合、一番右の要素であること
4. 1,2,3のどれでもないとき、flgを0にする
5. flgによって出力を変化
という方針です。
というわけで、7の倍数か否かチェックを入れてACになったコードがこちら。
n,m = map(int,input().split())
b = []
for i in range(n):
B = list(map(int,input().split()))
b.append(B)
flg = 1
for i in range(n):
if flg == 0:
break
for j in range(m):
if j < m-1:
if b[i][j+1] - b[i][j] != 1:
flg = 0
break
if j > 0:
if b[i][j-1] % 7 == 0:
flg = 0
break
else:
if i < n-1:
if (b[i+1][0] - b[i][0] != 7):
flg = 0
break
if flg:
print("Yes")
else:
print("No")
追加したのはこの部分
if j > 0:
if b[i][j-1] % 7 == 0:
flg = 0
break
j>0の条件は、これがないと、b[i][-1]つまり、一番右の要素も7の倍数か否かチェックしてしまうからです。
という感じで僕のAtCoder Beginner Contest (ABC) 225は終了しました。
パフォーマンスは303でした。C問題解けてたらなぁ・・・。
次こそは頑張るぞい！！
どれでは。
