きゃねろぐ

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

Beginning of Beginners Contest 002 解説

BoBコン

A問題

各桁の数に興味がある場合には，入力を整数ではなく文字列として受け取ると，実装が簡単になることが多いです．

（別解）入力を整数として受け取り， 10 で割った商と余りを利用する．

N = input()
ans = 0

for x in N:
  ans = max(ans, int(x))
  
print(ans)

B問題

\mathrm{mex} は見慣れない演算かもしれませんが，ゲームの勝敗を判定するGrundy数の計算などに用いられます． \mathrm{mex}(S) を求めるためには， x=0,1,2,\dots について順に x が S に含まれるかどうかを判定し， S に含まれないものがあれば x を出力し計算を終了すれば良いです．

\mathrm{mex}(S) の計算量を考えてみます． x が S に含まれるかどうかを判定するために， S に含まれる要素1つ1つについて x と比較する場合，最悪で O(|S|^2) の計算量がかかります．しかし，setなどのデータ構造を利用することで，計算量を O(|S|) や O(|S|\log |S|) に改善することができます．

以上をふまえ，今回の問題を考えてみます． R_i を計算する場合には |S|=W， C_j を計算する場合には |S|=H となるので， H 個の R_i と W 個の C_j を求めるために要する計算量は， O(HW) または O(HW\log HW) になります． \mathrm{mex} の計算量を改善しない場合には，計算量は O(HW(H+W)) となりTLEしてしまいます．

H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]

def mex(S):
  for x in range(1001):
    if x not in S:
      return x
    
R = []
for i in range(H):
  S = set()
  for j in range(W):
    S.add(A[i][j])
  R.append(mex(S))
  
C = []
for j in range(W):
  S = set()
  for i in range(H):
    S.add(A[i][j])
  C.append(mex(S))
  
print(*R)
print(*C)

C問題

排他的論理和（XOR）は，AND，ORなどと同じ論理演算の仲間です．計算は少しややこしいですが，以下のような性質を持っています．

  • 逆元は自分自身： x\oplus x=0
  • 演算の順番を変えても結果は変わらない（結合法則および交換法則が成り立つ）

以上の性質を用いることで， A_1=A_2\oplus A_3\oplus\cdots\oplus A_N\oplus K が成り立つことが分かります．

上記のような性質を知らない場合でも，コンテスト中に「競プロ 排他的論理和 性質」のように検索することが大事です．

（別解）各ビットごとに注目する． A_2,A_3,\dots,A_N,K のうち，第 i ビット目が 1 であるものの個数を c_i とする． c_i が奇数のとき， A_1 の第 i ビット目は 1 であり， c_i が偶数のとき， A_1 の第 i ビット目は 0 である．

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

ans = K
for a in A:
  ans ^= a

print(ans)

D問題

m=\min(x,y,z) とすると， \mathrm{gcd}(x,y,z)\le m が成り立ちます．また，各 k=1,2,\dots,m に対して， (x,y,z)=(k,k,k) とすると \mathrm{gcd}(x,y,z)=k が成り立ちます．さらに， x,y,z はそれぞれ X,Y,Z 以下という条件を満たします．よって， \mathrm{gcd}(x,y,z) が取り得る値は 1,2,\dots,m の m 通りです．

この解法は，

  • 各 k に対し， \mathrm{gcd}(x,y,z)=k となるための条件は何か？
    → x,y,z がそれぞれ k の倍数であれば良い．
  • x,y,z がそれぞれ k の倍数であるような x,y,z は存在するか？
    → 1\le x\le X， 1\le y\le Y， 1\le z\le Z それぞれの範囲に k の倍数が含まれれば良い．
    → 最小の k の倍数である k が含まれるかどうかのみを考えれば良い．

という考察から発想に至ることができます．

（別解） \mathrm{gcd}(x,y,z) は \mathrm{gcd}(x,y) の約数に限られるので， x,y について全探索を行い， \mathrm{gcd}(x,y) の各約数 k について \mathrm{gcd}(x,y,z)=k が成り立つような z が存在するか判定する．この判定は k\le Z により O(1) で可能である． \mathrm{gcd}(x,y)\le 2000 より，前もって 2000 以下の整数について約数列挙を行うことで，計算量を削減することができる．

X,Y,Z = map(int,input().split())
print(min(X,Y,Z))

E問題

多倍長整数を扱うことができるPythonと言えども， M_{10^{18}} のような極めて大きな数を扱うことはできません．しかし，このような大きな数が含まれる場合には， L の値は 10^{18} を超えることが予想されます．実際， B\ge 60 のとき， \mathrm{lcm}(M_A,M_{A+1},\dots,M_B)\ge M_B\ge M_{60}=2^{60}-1>10^{18} より， L の値は必ず 10^{18} を超えてしまいます．

よって， B\ge 60 のときは-1を出力し， B\lt 60 のときは \mathrm{lcm}(M_A,M_{A+1},\dots,M_B) を通常通り計算すれば良いです．言語によってはオーバーフローに気をつけてください．

from math import gcd

def lcm(x,y):
  return x * y // gcd(x,y)

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

if B>=60:
  print(-1)
  exit()
  
L = 1
for x in range(A,B+1):
  L = lcm(L,2**x-1)
  if L>10**18:
    print(-1)
    exit()
    
print(L)

F問題

考えられる解法をいくつか紹介します．

解法１

X_1,X_2,\dots,X_{2N} から Y_{11},Y_{12},Y_{21},Y_{22},\dots,Y_{N1},Y_{N2} への並び替えを全探索します．考えられる場合の数は (2N)! 通りであり， N=6 の場合だと 479001600 通りにもなるため，TLEしてしまいます．

解法２

X_1,X_2,\dots,X_{2N} の順に， Y_1,Y_2,\dots,Y_N のうちのどのペアに割り当てるかを決めていきます．ただし，すでに2つの要素が決まっているペアについては割り当てないようにします．こうすることで， (X_i,X_j) がペアであるときには必ず i\lt j が成り立ち， (X_i,X_j) と (X_j,X_i) の区別をなくすことで場合の数の削減につながります（これらのペアは， \min を考えたときの結果が同じであるため，どちらか一方について考えれば十分です）．実際，考えられる場合の数は \frac{(2N)!}{2^N} 通りであり， N=6 の場合だと 7484400 通りになります．解法１と比べて探索数はかなり減少しましたが，それでもTLEしてしまうと思います．

N,K = map(int,input().split())
X = list(map(int,input().split()))

Y_list = [[] for _ in range(N)]

# i番目のXをj番目のYに割り当てる再帰関数
def rec(i):
  if i==2*N:
    if sum([min(Y) for Y in Y_list])==K:
      print('Yes')
      exit()
    return
  for j in range(N):
    if len(Y_list[j])<2:
      Y_list[j].append(X[i])
      rec(i+1)
      Y_list[j].pop()

rec(0)
print('No')

解法３

解法２について，ペアの順番を入れ替えても結果は変わらないため， X_1 は必ず Y_1 に割り当てられるようにします．こうすることで， X_1 が Y_2,Y_3,\dots,Y_N に割り当てられる場合の探索を削減できます．考えられる場合の数は \frac{(2N)!}{N\cdot 2^N} 通りであり， N=6 の場合だと 1247400 通りになります．この程度の探索数であれば，ACを獲得できると思います．

N,K = map(int,input().split())
X = list(map(int,input().split()))

Y_list = [[] for _ in range(N)]
Y_list[0].append(X[0])

# i番目のXをj番目のYに割り当てる再帰関数
def rec(i):
  if i==2*N:
    if sum([min(Y) for Y in Y_list])==K:
      print('Yes')
      exit()
    return
  for j in range(N):
    if len(Y_list[j])<2:
      Y_list[j].append(X[i])
      rec(i+1)
      Y_list[j].pop()

rec(1)
print('No')

解法４

解法２について，各 X_1,X_2,\dots,X_{2N} の割り当てを考える際に，まだ空のペアに割り当てる場合には，空のペアの中で番号が最も小さいものに割り当てるようにします．こうすることで，必ず Y_{11}\lt Y_{21}\lt\cdots\lt Y_{N1} が成り立つため，ペアの順番による無駄な探索を削減することができます．考えられる場合の数は \frac{(2N)!}{N!\cdot 2^N} 通りであり， N=6 の場合でも 10395 通りとなり，余裕でACを獲得することができます．

N,K = map(int,input().split())
X = list(map(int,input().split()))

Y_list = []

# i番目のXをj番目のYに割り当てる再帰関数
def rec(i):
  if i==2*N:
    if sum([min(Y) for Y in Y_list])==K:
      print('Yes')
      exit()
    return
  for j in range(len(Y_list)):
    if len(Y_list[j])<2:
      Y_list[j].append(X[i])
      rec(i+1)
      Y_list[j].pop()
  if len(Y_list)<N:
    Y_list.append([X[i]])
    rec(i+1)
    Y_list.pop()

rec(0)
print('No')

解法５

X_1,X_2,\dots,X_{2N} のうち，どの N 個をSakkyさんが購入することになるかを考えます．その後，決められた N 個をSakkyさんが購入するようなペアの選び方が実際に存在するかを判定します．この判定は，すべての k=1,2,\dots,2N に対し，

  • 価格が安い方から k 番目までの商品に注目したとき，Sakkyさんが購入する商品の個数が，購入しない商品の個数以上である

が成り立つかどうかで判定できます．考えられる場合の数は {}_{2N}\mathrm{C}_N 通りであり， N=6 の場合でも 924 通りとなり，余裕でACを獲得することができます．

from itertools import combinations

N,K = map(int,input().split())
X = list(map(int,input().split()))
X.sort()

for v in combinations(range(2*N),N):
  ok = True
  cnt = 0
  for i in range(2*N):
    cnt += 1 if i in v else -1
    if cnt<0:
      ok = False
      break
  if ok and sum([X[i] for i in v])==K:
    print('Yes')
    exit()

print('No')

F2問題

F問題におけるAC解の探索数は，それぞれ

  • 解法３： \frac{(2N)!}{N\cdot 2^N} 通り
  • 解法４： \frac{(2N)!}{N!\cdot 2^N} 通り
  • 解法５： {}_{2N}\mathrm{C}_N 通り

でした． N\le 6 の場合は探索数は小さかったですが， N\le 14 の場合だと

  • 解法３：約 7 \times 10^{23} 通り
  • 解法４：約 2\times 10^{14} 通り
  • 解法５：約 4\times 10^{7} 通り

となってしまい，どれもTLEしてしまいます．

解法５では，Sakkyさんが購入する商品の組み合わせ {}_{2N}\mathrm{C}_N 通りを探索しましたが，中には実際にはペアが構成できず実現不可能な組み合わせも含まれていました．実現可能な組み合わせだけを探索することはできないでしょうか．

解法６

解法５で用いたペアの選び方の判定条件を応用することで，ある N 個の商品の組み合わせに対し，Sakkyさんがその N 個の商品を購入するようなペアの選び方が存在するための必要十分条件は，

  • 長さ 2N の文字列 S の第 k 文字目を，価格が安い方から k 番目の商品をSakkyさんが購入するならば(，購入しないならば)とするとき， S がvalidな括弧列になっている

であることが分かります．こうすることで，長さ 2N のvalidな括弧列を探索する問題に帰着されます．考えられる場合の数は \frac{1}{N+1}{}_{2N}\mathrm{C}_N 通り（カタラン数）であり， N=14 の場合でも 2674440 通りとなり，ACを獲得することができます．

N,K = map(int,input().split())
X = list(map(int,input().split()))
X.sort()

def rec(i,c,s):
  if i==2*N:
    if s==K:
      print('Yes')
      exit()
    return
  if c<=2*N-i:
    rec(i+1,c+1,s+X[i])
  if c>0:
    rec(i+1,c-1,s)

rec(0,0,0)
print('No')