[ABC276 Python]AtCoder Beginner Contest 276 A～C問題Python解説

2022年11月6日 01:00

こんばんは。
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:１～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
となります。

これはどのような仕組みになっているかというと、
１～Nまでの整数の中で、上位の位で既に使った整数は
既に使えないので、それ以外の数字で下位の位を求めていくことになります。
例えば百の位の候補を見ていた時に、
候補全体としては、1,2,3,4,5が考えられますが、
それまでに4と2は既に使っているので、
本当の候補は1と3と5になります。

なので、入力されたPを先頭から見ていき、
１～P[i]の中で既出のものを除いた分の個数、
iの階乗を追加します。
これで入力されたPが何番目かを取得できました。

ではP=P-1として、(2)を見ていきます。
(2)は以下のページを参考にしてください。

この例題がすごく分かりやすいので、
説明は省略しますが、
商と余りを求めつつ、
余りから順列を求めることができます。

証明もその下に掲載されているので、
是非ご覧ください。

[::-1]はリストを逆にする、リスト.pop()は
指定したインデックスの値を取得しながら
リストから削除することができます。

この記事が気に入ったらサポートをしてみませんか？