競プロ備忘録過去問編#1 ABC042

• ABCは毎週やるみたいではないので過去問も解いていく
• なんだかんだそこまで時間とれなそうで悲しい

AtCoder Beginner Contest 042

• なぜか4問しかなかった。4問目までだったので易し目だった

A.和風いろはちゃんイージー

３つの数字A,B,Cが与えられるので、それを並び替えて5・7・5にできるかどうか判断する問題

入力
A B C

出力
できるなら"YES"、できないなら"NO"を出力

• A,B,Cを順番に見てって、5または7ならそれぞれカウント
• 最後に5のカウントが2、7のカウントが1なら"YES"、そうでないなら"NO"を出力

解答

myList=input().split()
five=0
seven=0

for i in range(3):
  if int(myList[i])==5:
    five+=1
  elif int(myList[i])==7:
    seven+=1
if five==2 and seven==1:
  print("YES")
else:
  print("NO")

B.文字列大好きいろはちゃんイージー

長さがLの文字列がN個ある。これらを並び替えて繋げたもののうち、一番辞書順で小さいものを求めよという問題

入力
$ N\quad L\ $
$ S_1\ $
$ S_2\ $
$ S_3\ $
$ \vdots\ $
$ S_N $

出力
答えを出力

• 辞書順に小さいものからつなげていけば終了
• list.sort()で辞書順にリストを並び替える
• sorted(list)で辞書順に並び替えたリストを返す

解答

N,L=map(int,input().split())
S=[]
for i in range(N):
  S.append(input())

S.sort()
ans=""
for i in range(N):
  ans+=S[i]

print(ans)

C.こだわり者いろはちゃん

Kこの数字が与えられる。その数字を含まない数字のうちでN以上の数字のうち一番小さい数字を答えよという問題

入力
N K
$ D_1\quad D_2\quad \cdots\quad D_K\quad$

出力
答えを出力せよ

• 数学の問題ではにのでどうプログラムを走らせれば良いのか考える
• 虱潰しは立派な方法
• Nから初めて、各数値で1桁目から調べていく。cntで何桁目までオッケーかカウントしておいて答えかどうか判別
• while文とbreak組み合わせてもいけそう

解答

N,K=map(int,input().split())
D=input().split()

for i in range(N,100000):
  cnt=0
  for j in D:
    if str(j) in str(i):
      break
    else:
      cnt+=1

  if cnt==len(D):
    print(i)
    break

D.いろはちゃんとマス目

縦H、横Wマスのマス目がある。下からAマス以内かつ左からBマス以内のマス目には入れない。左上から出発して左か下にのみ移動する時、右下にたどり着く道は何通りあるかという問題。答えは$10^9+7$で割った余りで求める。

入力
H W A B

答え
答えを$10^9+7$で割った余りを出力

• 単純なマス目であればよくある数学の問題で、H+W-2会の移動のうち、W-1回の下への移動を何回目で行うかを求める問題、つまりH+W-2からW-1を選ぶ組み合わせの問題
• 今回もこれを応用
• いかなる道であれ、上からH-A-1マス目で左からBマス目より右のマスのどこかを通る。
• よって左上を(0,0)として、(0,0)→(H-A-1,i)→(H-A,i)→(H-1,W-1)(B≦i≦W-1)の順番に通る道順を数えて、それぞれ足していけばいい。
• 組み合わせは$\frac{n!}{r!(n-r)!}$で計算
• やっぱり数字がごっちゃになるのでちゃんと図を書く、かつ例題は1のような小さいのではなく、2のような中くらいの大きさの方が頭の整理しやすいかも
• 階乗はmath.factorial(n)で計算できる。ループで回すよりははるかに早い
• ただし正面から計算すると数字が大きくなりすぎてオーバーフローする
• よって逆元を利用する
• 逆元とはa÷b=a×b^{-1}(mod p)となるようなb^{-1}でb^{p-2}(mod p)(pは素数)で求められる
• 逆元について、詳しくはググって
• 先にx!とその逆元を求めるとコスパ良し
• 冪剰余はpow()の第3引数を設定することで効率よく求められる。自作でやるとめっちゃ重い処理になるので注意
• pow()の返り値はfloat型なので注意
• 全部求めるならx!はいちいちmath.factorial(x)で求めないで、fact[x-1]*xで求めれば良い

解答

H,W,A,B=map(int,input().split())

fact=[[]for i in range(H+W-2)]
inv=[[] for i in range(H+W-2)]
fact[0]=1
inv[0]=1
ans=0

for i in range(1,H+W-2):
  fact[i]=fact[i-1]*i%(10**9+7)
  inv[i]=pow(fact[i],10**9+5,10**9+7)

for i in range(B,W):
  ans+=(fact[H-A+i-1]*fact[A+W-i-2]*inv[i]*inv[H-A-1]*inv[A-1]*inv[W-i-1])
  ans=ans%(10**9+7)

print(int(ans))