[ABC276 Python]AtCoder Beginner Contest 276 A~C問題Python解説
こんばんは。
ABC276の解説記事です。
もしミス等ありましたらコメントお願いいたします。
A問題
S = input()
ans = -1
for i in range(len(S)):
if S[i] == "a":
ans = i-1
print(ans)
いろいろな解き方が考えられますが、
上記が一番スマートかなと思います。
文字列Sの先頭から順番に見ていき、
もし"a"が現れたらSのindexをansとして更新していきます。
よって最後に出力されるのは
最後に現れる"a"ということになります。
"a"がなければansは更新されず、
そのまま-1が出力されるので問題文に適しています。
B問題
N, M = map(int, input().split())
from collections import defaultdict
d = defaultdict(list)
for i in range(M):
A, B = map(int, input().split())
d[A].append(B)
d[B].append(A)
for i in range(1, N+1):
print(len(d[i]),*sorted(d[i]))
この問題は辞書型を使うのがいいでしょう。
辞書型の中でもdifaultdictがおすすめです。
辞書型が分からない方は以下等を参考にしてください。
概略としては繋がっている都市を保存していく形になります。
入力がAとBで
AとBは繋がっていますので、
Aとつながっていることを示すリストにBを入れ、
Bとつながっていることを示すリストにAを入れます。
問題文からi:1~NについてA[i]とつながっている
都市Bを出力しろと書いているので、
上記のように保存することで、回答することができます。
difaultdictを使う理由としては、
都市A[i]がどこともつながっていない場合、
エラーを出さないようにするためです。
最後にlen(d[i])で何個の年が繋がっているか、
sorted(d[i])で昇順に繋がっている都市を出力できます。
C問題
import math
N = int(input())
P = list(map(int, input().split()))
J = [_ for _ in range(1, N+1)]
factorialed_J = [math.factorial(_) for _ in range(N)]
factorialed_J.sort(reverse=True)
num = 0
published_num = []
for i in range(N):
for j in range(1, P[i]):
if j not in published_num:
num += factorialed_J[i]
published_num.append(P[i])
num -= 1
surplus = []
for i in range(1, N+1):
surplus.append(num%i)
num = num//i
surplus = surplus[::-1]
ans = []
for i in range(N):
ans.append(J[surplus[i]])
J.pop(surplus[i])
print(*ans)
すごい長いコードになってしまいました。
順に説明していきます。
最初に説明しますが、順列をitertools.permulations()などで
全出力するとTLEになりますので、注意が必要です。
この問題は、数学Aの知識を使って高速化していく問題でした。
この問題とすごく似た数学の問題がありましたので、
こちらを参考にして解いていきます。
基本的には参考ページにあり通り、
(1)入力されたPが何番目にあるか。
(2)その一つ前は何か。
の2問を解くことで回答できます。
ではまず⑴を解きましょう。
基本的には上記のページの(1)をご覧ください。
42513までには
1○○○○,2○○○○,3○○○○
41○○○
421○○,423○○
が考えられます。
個数は丸の数の階乗になりますので、
3×4!+1×3!+2×2!+1=83
となります。
これはどのような仕組みになっているかというと、
1~Nまでの整数の中で、上位の位で既に使った整数は
既に使えないので、それ以外の数字で下位の位を求めていくことになります。
例えば百の位の候補を見ていた時に、
候補全体としては、1,2,3,4,5が考えられますが、
それまでに4と2は既に使っているので、
本当の候補は1と3と5になります。
なので、入力されたPを先頭から見ていき、
1~P[i]の中で既出のものを除いた分の個数、
iの階乗を追加します。
これで入力されたPが何番目かを取得できました。
ではP=P-1として、(2)を見ていきます。
(2)は以下のページを参考にしてください。
この例題がすごく分かりやすいので、
説明は省略しますが、
商と余りを求めつつ、
余りから順列を求めることができます。
証明もその下に掲載されているので、
是非ご覧ください。
[::-1]はリストを逆にする、リスト.pop()は
指定したインデックスの値を取得しながら
リストから削除することができます。
この記事が気に入ったらサポートをしてみませんか?