きゃねろぐ

とある「おひさま」の徒然日記

Python初心者のためのABC202

AtCoder

A問題

atcoder.jp

サイコロの出た面の数を x とすると，反対側の面の数は 7-x と表される．

a,b,c = map(int,input().split())

# サイコロの出た面と反対側の面の数
def f(x):
  return 7 - x

ans = f(a) + f(b) + f(c)
print(ans)

以下のように簡潔に書くこともできる．

print(21 - sum(map(int,input().split())))

B問題

atcoder.jp

ポイントは以下の２つである．

  • S の順番が逆になる
  • 6は9に，9は6に変換する（それ以外の文字は変わらない）

まず，文字列 S の順番を逆にするためには，S = S[::-1]とするのが最も簡単である． これはスライスと呼ばれる操作で，文字列だけでなくリストに対しても使うことができる．

S = '0123456'

# S[x]からスタートしてS[y]の手前までz文字ごとに出力する
print(S[x:y:z])

# S[1]からS[6]の手前まで2文字ごとに出力する
print(S[1:6:2])  
> '135'

# xを省略した場合は最初からスタートする
# zが負の場合はSの末尾が最初として扱われる
print(S[:4:1])
> '0123'

# yを省略した場合は最後まで出力する
# zが負の場合はSの先頭が最後として扱われる
print(S[5::-2])
> '531'

# x,y,zを複数省略することも可能
# 下の例だと，Sの最初から最後までを-1文字ごと＝逆向きに1文字ごとに出力する
print(S[::-1])
> '6543210'

次に，6を9に，9を6に変換するためには，Pythonに文字を反転させるような関数はないため， if文などを用いて一文字ごとに変換してやれば良い．

S = input()

# 文字列を反転
S = S[::-1]

ans = ''

# '6'を'9'に，'9'を'6'に変換
for s in S:
  if s=='6':
    ans += '9'
  elif s=='9':
    ans += '6'
  else:
    ans += s
    
print(ans)

文字列の変換にはS.replace(a, b)（ S 内に現れる文字列 a をすべて b に変換する）を使っても良い．以下のように簡潔に書くこともできる．

print(input()[::-1].replace('9', '*').replace('6', '9').replace('*', '6'))

ただし，S.replace('6', '9').replace('9', '6')のようにすると， 変換が左から順に行われるため6が9に変換されたあと再度6に戻ってしまうため注意．

C問題

atcoder.jp

D_j = B_{C_j} なる数列 D を考えると， A_i=D_j をみたす (i,j) の組の個数を求める問題に帰着される． これは ABC200のC問題 と似たような感じで，各値の出現回数を管理することで解くことができる．

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

D = [B[c-1] for c in C]

cntA = [0]*(N+1)
for x in A:
  cntA[x] += 1

cntD = [0]*(N+1)
for x in D:
  cntD[x] += 1
  
ans = 0
for x in range(1,N+1):
  ans += cntA[x] * cntD[x]
  
print(ans)

D問題

atcoder.jp

求めたい辞書順 K 番目の文字列を S とする．

入出力例２を見る限り全探索は無理そうなので，上手いやり方を考える必要がある． 文字列を辞書順に並べたとき，前半にaで始まる文字列が並び，後半にbで始まる文字列が並ぶのは簡単に予想がつく．

では，具体的に何番目までがaから始まる文字列なのだろうか？ 先頭の文字をaで固定したとき，文字列の残りは A-1 個のaと B 個のbが並ぶので， {}_{A-1+B}\mathrm{C}_{A-1} 通り考えられる． よって，辞書順で

1 番目から {}_{A-1+B}\mathrm{C}_{A-1} 番目までの文字列は先頭の文字がa
{}_{A-1+B}\mathrm{C}_{A-1}+1 番目以降の文字列は先頭の文字がb

であることが分かる． したがって， K と {}_{A-1+B}\mathrm{C}_{A-1} の比較により S の先頭の文字が分かる．

では，２文字目以降はどのようにして考えたら良いだろうか？

S の先頭の文字がaだった場合， S の辞書順は残りの A-1 個のaと B 個のbが並ぶ部分で決まる． 仮にこの部分を S_a とすると，以下の2つ

S_a の「 A-1 個のaと B 個のbが並ぶ文字列」の中での辞書順
S の「 A 個のaと B 個のbが並ぶ文字列」の中での辞書順

は一致する．よって，

「 A-1 個のaと B 個のbが並ぶ文字列」の中での辞書順 K 番目の文字列の先頭の文字

が， S の２文字目である．

S の先頭の文字がbだった場合， 先程と同様に S の辞書順は残りの A 個のaと B-1 個のbが並ぶ部分 S_b で決まる． しかし， S_b の「 A 個のaと B-1 個のbが並ぶ文字列」の中での辞書順が x 番目だとすると，

S の「 A 個のaと B 個のbが並ぶ文字列」の中での 辞書順は {}_{A-1+B}\mathrm{C}_{A-1}+x 番目

になる．これは，「 A 個のaと B 個のbが並ぶ文字列」の辞書順を考えると， aから始まる文字列が最初に {}_{A-1+B}\mathrm{C}_{A-1} 個並ぶためである． この点に注意すると， S の２文字目は，

「 A 個のaと B-1 個のbが並ぶ文字列」の中での 辞書順 K-{}_{A-1+B}\mathrm{C}_{A-1} 番目の文字列の先頭の文字

である．

以上のように１文字目，２文字目，…と順に考えることで，辞書順で x 番目の文字列の先頭の文字を求める問題に帰着される．

A,B,K = map(int,input().split())

# 二項係数
def comb(n,k):
  ans = 1
  for i in range(k):
    ans *= n - i
    ans //= i + 1
  return ans

ans = ''

while True:
  
  # AかBの値が0になったら残りの文字は自動的に決まる
  if A==0:
    ans += 'b'*B
    break
  if B==0:
    ans += 'a'*A
    break
  
  # 先頭の文字はどっち？
  if K <= comb(A+B-1, A-1):
    ans += 'a'
    A -= 1
  else:
    ans += 'b'
    K -= comb(A+B-1, A-1)
    B -= 1
    
print(ans)