2022-02-25

東工大2022 数学第3問

(1)

$x$ 軸正の方向と直線 $\mathrm{AP}, \mathrm{BP}$ がなす角の大きさはそれぞれ $\frac{\pi}{2}+t-\alpha, t-\alpha$ である．

$t=\alpha$ のとき， $\mathrm{P}(\sin\alpha,\cos\alpha)$ である．

$t\ne\alpha$ のとき，直線 $\mathrm{AP}, \mathrm{BP}$ の式はそれぞれ以下の通りである．

$y=\tan(\frac{\pi}{2}+t-\alpha)(x-\sin t)=-\frac{1}{\tan(t-\alpha)}(x-\sin t)$ ,
$y=\tan(t-\alpha)x+\cos t$ .

これら二式から $x$ を消去すると，

$\tan(t-\alpha)x+\cos t=-\frac{1}{\tan(t-\alpha)}(x-\sin t)$ , $\tan^2(t-\alpha)x+\cos t\tan(t-\alpha)=-x+\sin t$ , $(1+\tan^2(t-\alpha))x=\sin t-\cos t\tan(t-\alpha)$ ,
$\frac{1}{\cos^2(t-\alpha)}x=\frac{\sin\alpha}{\cos(t-\alpha)}$ ,
$x=\sin\alpha\cos(t-\alpha)$ .

よって， $P$ の $x$ 座標は $\sin\alpha\cos(t-\alpha)$ である．

同様に $y$ 座標も求めることで， $\mathrm{P}(\sin\alpha\cos(t-\alpha),\cos\alpha\cos(t-\alpha))$ を得る．

したがって， $P$ は直線 $y=\frac{x}{\tan\alpha}$ 上に存在し，これは $t=\alpha$ の時も成り立つ．

以上より，求める直線の方程式は $y=\frac{x}{\tan\alpha}$ である．

(2)

$f(t)=\cos(t-\alpha)$ とおくと， $f'(t)=-\sin(t-\alpha)$ より，

$t$	$0$	$\cdots$	$\alpha$	$\cdots$	$\frac{\pi}{2}$
$f'(t)$		$+$		$-$
$f(t)$	$\cos\alpha$	$\nearrow$	$1$	$\searrow$	$\sin\alpha$

のような増減表を得る．

$\cos\alpha$ と $\sin\alpha$ の大小に注意し(1)の結果をふまえると，求める道のりは，

直線 $y=\frac{x}{\tan\alpha}$ の $\sin^2\alpha\le x\le \sin\alpha$ の範囲（ $0\lt\alpha\le\frac{\pi}{4}$ ）
直線 $y=\frac{x}{\tan\alpha}$ の $\sin\alpha\cos\alpha\le x\le \sin\alpha$ の範囲（ $\frac{\pi}{4}\le\alpha\lt\frac{\pi}{2}$ ）

である．

(3)

すべての $0\le t\le\frac{\pi}{2}$ に対し，

$x^2-x+y^2=\cos(t-\alpha)(\cos(t-\alpha)-\sin\alpha)=f(t)(f(t)-\sin\alpha)$

または

$x^2+y^2-y=\cos(t-\alpha)(\cos(t-\alpha)-\cos\alpha)=f(t)(f(t)-\cos\alpha)$

が $0$ 以上であることを示せば良い．

(2)で求めた $f(t)$ の増減表から，

$0\le t\le\alpha$ のとき， $f(t)\ge\cos\alpha>0$ より， $x^2+y^2-y\ge 0$ が成り立つ．
$\alpha\le t\le\frac{\pi}{2}$ のとき， $f(t)\ge\sin\alpha>0$ より， $x^2-x+y^2\ge 0$ が成り立つ．

以上より，題意は示された．

$\square$

2022-02-25

東工大2022 数学第2問

(1)

$x=a+b+c,y=bc+ca+ab,z=abc$ とおく．

$\mathrm{gcd}(x,y,z)=1$ を背理法で示す．

$\mathrm{gcd}(x,y,z)\ne1$ と仮定すると，ある素数 $p$ が存在して $x,y,z$ はすべて $p$ の倍数である．

特に， $z=abc$ が $p$ の倍数であることから， $a,b,c$ のいずれか一つは $p$ の倍数である．

$a$ が $p$ の倍数であるとして一般性を失わない．

このとき，

$b+c=(a+b+c)-a=x-a$ , $bc=(bc+ca+ab)-a(b+c)=y-a(b+c)$

より， $b+c,bc$ はともに $p$ の倍数である．

特に， $bc$ が $p$ の倍数であることから， $b,c$ のいずれか一つは $p$ の倍数である．

$b$ が $p$ の倍数であるとして一般性を失わない．

このとき， $c=(b+c)-b$ も $p$ の倍数となるが， $a,b,c$ がすべて $p$ の倍数となるため $\mathrm{gcd}(a,b,c)=1$ に矛盾する．

したがって， $\mathrm{gcd}(x,y,z)=1$ である．

$\square$

(2)

$v=a^2+b^2+c^2,w=a^3+b^3+c^3,\mathrm{gcd}(x,v,w)=K$ とおく．

$v=(a+b+c)^2-2(bc+ca+ab)=x^2-2y$ , $w=(a+b+c)(a^2+b^2+c^2-bc-ca-ab)+3abc=x^3-3xy+3z$

より， $K=\mathrm{gcd}(x,x^2-2y,x^3-3xy+3z)$ が成り立つ．

(i)

$K$ が $4$ の倍数であると仮定すると， $x,x^2-2y,x^3-3xy+3z$ はすべて $4$ の倍数である．

$2y=x^2-(x^2-2y)$ であり，右辺は $4$ の倍数なので， $y$ は $2$ の倍数である．

$3z=(x^3-3xy+3z)-x(x^2-3y)$ であり，右辺は $4$ の倍数なので， $z$ は $4$ の倍数である．

以上より， $x,y,z$ はすべて $2$ の倍数となるが，これは(1)で示した $\mathrm{gcd}(x,y,z)=1$ に矛盾する．

したがって， $K$ は $4$ の倍数でない．

(ii)

$K$ が $9$ の倍数であると仮定すると，(i)と同様の議論により $x,y,z$ はすべて $3$ の倍数となり $\mathrm{gcd}(x,y,z)=1$ に矛盾する．

したがって， $K$ は $9$ の倍数でない．

(iii)

$5$ 以上の素数 $p$ に対し $K$ が $p$ の倍数であると仮定すると，(i),(ii)と同様の議論により $x,y,z$ はすべて $p$ の倍数となり $\mathrm{gcd}(x,y,z)=1$ に矛盾する．

したがって， $K$ は $p$ の倍数でない．

(i)〜(iii)より， $K$ としてあり得る値は $1,2,3,6$ のいずれかである．

実際，

$(a,b,c)=(1,1,3)$ のとき， $\mathrm{gcd}(a,b,c)=1,K=\mathrm{gcd}(5,11,29)=1$ , $(a,b,c)=(1,1,2)$ のとき， $\mathrm{gcd}(a,b,c)=1,K=\mathrm{gcd}(4,6,10)=2$ , $(a,b,c)=(1,1,1)$ のとき， $\mathrm{gcd}(a,b,c)=1,K=\mathrm{gcd}(3,3,3)=3$ , $(a,b,c)=(1,1,4)$ のとき， $\mathrm{gcd}(a,b,c)=1,K=\mathrm{gcd}(6,18,66)=6$ ,

となることから， $K=1,2,3,6$ はすべてあり得る．

以上より，求める値は $1,2,3,6$ である．

2021-07-13

Beginning of Beginners Contest 002 解説

BoBコン

A問題
B問題
C問題
D問題
E問題
F問題
- F2問題

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')

2021-06-29

Beginning of Beginners Contest 001 解説

BoBコン

A問題
B問題
C問題
D問題
E問題
F問題

A問題

$A+B>C$ が成り立つかどうかで場合分けをすれば良いです．出力文のタイプミスには注意してください（サンプルの出力をコピペすると確実です）．

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

if A+B>C:
  print('Correct :)')
else:
  print('Wrong :(')

B問題

各 $i$ に対して愚直に $S_i=A_1+A_2+\cdots+A_N$ を計算すると，全体で $O(N^2)$ 回の計算を行う必要があるためTLEしてしまいます．

そこで， $S_i=S_{i-1}+A_i$ であることを利用すれば，計算量を削減し $O(N)$ で解くことができます．

N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

ans = 0
S = 0

for a in A:
  S += a
  S %= MOD
  ans += S
  ans %= MOD

print(ans)

もしくは， $\displaystyle\sum_{i=1}^{N}S_i=\sum_{i=1}^{N}(N+1-i)\,A_i$ であることを利用して $O(N)$ で解くことができます．

N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

ans = 0

for i in range(N):
  ans += A[i]*(N-i)
  ans %= MOD
  
print(ans)

C問題

$N$ を素因数分解して，2番目に大きい正の約数を求めれば良いです．

$2$ 以上 $N$ 以下の整数 $x$ について， $N$ が $x$ で割り切れるかどうかを調べようとすると，最悪の場合に $O(N)$ の計算量がかかりTLEしてしまいます．

ここで，仮に $N$ が $p>\sqrt{N}$ を満たす約数 $p$ を持つならば， $N/p$ も $N$ の約数であり $N/p\lt\sqrt{N}$ が成り立ちます．言い換えれば， $N$ が $2$ 以上 $\sqrt{N}$ 以下のすべての整数で割り切れなければ， $N$ は $1$ か $N$ でしか割り切れない素数であることが分かります．

よって， $2$ 以上 $\sqrt{N}$ 以下の整数 $x$ について $N$ が $x$ で割り切れるかどうかを調べれば良いので， $O(\sqrt{N})$ の計算量で問題を解くことができます．

また，今回は2番目に大きい正の約数にしか興味がないので，正の約数すべてを列挙する必要はなく，

$N$ が素数のとき， $1$
$N$ が素数でないとき， $N$ の最小の素因数を $p$ として， $N/p$

を答えれば良いです．

N = int(input())

# 小数の丸め誤差を考慮して，念のため√N+1まで調べる
for x in range(2,int(N**0.5)+2):
    if N%x==0:
        print(N//x)
        exit()

# Nが素数の場合
print(1)

D問題

この問題でやっていることはバブルソートそのものであることに気付ければ，条件を満たすかどうかは転倒数から判定できることが分かります．転倒数とは $i\lt j$ かつ $h_i>h_j$ を満たす $(i,j)$ の個数であり，愚直に計算すれば $O(N^2)$ の計算量がかかりますが，BITなどのデータ構造を用いれば $O(N\log N)$ で求めることができます．

しかし，今回の場合はソート回数が3回までと限定されているので，愚直なシミュレーションを行うことが可能です．数列を順に見ていき入れ替えるべきところ（ $h_{i}>h_{i+1}$ となっているところ）を見つけたら，そこを入れ替えるという操作を3回まで行うようにすれば良いです．計算量は $O(N)$ です．

N = int(input())
h = list(map(int,input().split()))

for k in range(3):
    for i in range(N-1):
        if h[i]>h[i+1]:
            h[i],h[i+1] = h[i+1],h[i]
            break

ok = True
for i in range(N):
    if h[i]!=i+1:
        ok = False
        break

if ok:
    print('Yes')
else:
    print('No')

E問題

$X$ を $10$ で割った商と余りをそれぞれ $d,r$ とすると， $X$ 円を支払う際には1円硬貨を $r$ 枚，10円硬貨を $d$ 枚を使用することになります．よって， $d+r=N$ を満たす $X$ の個数を求める問題であると言い換えることが出来ます．

考えられる $X$ の値は最大で $10^{18}$ になるため，全探索ではTLEしてしまいます．

しかし， $X$ の値からある程度それぞれの硬貨の使用枚数に目星をつけられることが分かります．

$X\lt 10\,(N-10)$ のとき，10円硬貨を $N-10$ 枚より多く使うと支払額が $10(N-10)$ 円を超えるため，10円硬貨は高々 $N-10$ 枚までしか使われず，さらに1円硬貨は高々 $9$ 枚までしか使われないため，硬貨の使用枚数は $N$ 枚より少ない．
$X>10N$ のとき，10円硬貨は最低 $N$ 枚使う必要があり，加えて1円硬貨または10円硬貨を $1$ 枚以上使うことになるので，硬貨の使用枚数は $N$ 枚を超える．

以上をふまえると， $10(N-10)\le X\le 10N$ の範囲のみを調べれば良いことが分かります．この範囲内に整数は高々 $101$ 個しか存在しないため，全探索が可能です．

N = int(input())

ans = 0
for x in range(max(1,10*N-100),10*N+1):
  if (x//10)+(x%10)==N:
    ans+=1

print(ans)

よりスマートな解法を示します．ポイントは，1円硬貨は高々 $9$ 枚までしか使用されないことと，1円硬貨の使用枚数と $N$ が決まれば，10円硬貨の使用枚数と $X$ も一意に決まることです．

$N\le 9$ のとき，

$X=N+9\times 0$ （1円硬貨を $N$ 枚，10円硬貨を $0$ 枚）
$X=N+9\times 1$ （1円硬貨を $N-1$ 枚，10円硬貨を $1$ 枚）
　　　︙
$X=N+9\times N$ （1円硬貨を $0$ 枚，10円硬貨を $N$ 枚）

の $N+1$ 通りが考えられます．

$N\ge 10$ のとき，

$X=10N-9\times 9$ （1円硬貨を $9$ 枚，10円硬貨を $N-9$ 枚）
$X=10N-9\times 8$ （1円硬貨を $8$ 枚，10円硬貨を $N-8$ 枚）
　　　︙
$X=10N-9\times 0$ （1円硬貨を $0$ 枚，10円硬貨を $N$ 枚）

の $10$ 通りが考えられます．

よって，求める答えは $\min(N+1,10)$ です．

N=int(input())
print(min(N+1,10))

F問題

$X_K$ は $X_0$ に関して単調増加になっているので，二部探索で答えを求めることができます．計算量は $O(K\log N)$ です．

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

l = 1
r = 10**18
while r-l:
  mid = (l+r)//2
  X = mid
  for i in range(1,K+1):
    X = ((X-1)//i+1)*i
  if X>=N:
    r = mid
  else:
    l = mid+1

print(l)

2021-06-27

Python初心者のためのABC207

AtCoder

A問題
B問題
C問題
D問題
E問題

A問題

atcoder.jp

お好きなやり方でどうぞ．

# 解法１
A,B,C = map(int,input().split())
print(max(A+B,B+C,C+A))

# 解法２
L = list(map(int,input().split()))
print(sum(L)-min(L))

# 解法３
L = sorted(list(map(int,input().split())))
print(L[1]+L[2])

B問題

atcoder.jp

操作回数を $k$ とすると， $kB+A\le kCD$ すなわち $k(CD-B)\ge A$ が成り立つ必要があります．

$CD-B\le 0$ のとき，条件をみたす $k$ は存在しません．
$CD-B>0$ のとき，条件をみたす最小の $k$ は $\lceil\frac{A}{CD-B}\rceil$ です．

$\lceil\frac{x}{y}\rceil = \lfloor\frac{x-1}{y}\rfloor +1$ を用いれば，整数同士の計算のみで完結するため誤差の心配はありません．

A,B,C,D = map(int,input().split())
print((A-1)//(C*D-B)+1 if C*D-B>0 else -1)

C問題

atcoder.jp

開区間はちょっとだけ幅を狭めた閉区間だと思って処理すれば良いです．制約が $N\le 2000$ と小さいため，すべての区間のペアについて条件を満たすか確認する $O(N^2)$ の全探索が可能です．

N = int(input())
D = []

for _ in range(N):
  t,l,r = map(int,input().split())
  l += 0.1 if t in [3,4] else 0
  r -= 0.1 if t in [2,4] else 0
  D.append([l,r])

ans = 0
for i in range(N):
  li,ri = D[i]
  for j in range(i+1,N):
    lj,rj = D[j]
    if li<=rj and lj<=ri:
      ans += 1  
print(ans)

D問題

ここでは，複素数を用いた解法を紹介します．

Step１：特殊ケースの例外処理①

$N=1$ のとき，平行移動のみで $S$ と $T$ は必ず一致します．以降は $N>1$ の場合を考えます．

Step２：重心に注目した平行移動

公式解説にある通り， $S$ と $T$ が一致するならば両者の重心も一致しており，回転移動では重心の位置は変わりません．よって， $S$ と $T$ の重心が一致するような平行移動が必要であり，かつ，それ以外の平行移動は許されないことが分かります．両者の重心が原点に一致するように平行移動させることで，後は回転移動のみを考えれば良いことになります．

Step３：特殊ケースの例外処理②

$S$ の代表点（ $s_0$ とします）を一つ選び， $T$ に含まれる点のうち $s_0$ と一致させる点（ $t_0$ とします）を決めれば，回転角度は一意に決まります．しかし， $s_0$ が原点と一致する場合には，対応する $t_0$ は原点以外ありえません．そのため， $S$ か $T$ のいずれか一方にのみ原点が含まれる場合には，その時点で $S$ と $T$ を一致させることは不可能であると判定できます．また， $S$ と $T$ の両方に原点が含まれる場合には，それぞれから原点を削除した残りの $N-1$ 点について一致するかどうかを考えれば良いです．後々の操作を考慮して，このようなケースに対応する処理を加えておきます．

Step４：複素数を用いた回転移動

複素数平面を考えることで各点を複素数に対応させます．すなわち， $(x,y)\mapsto x+iy$ とします．

$S$ の代表点 $s_0$ を適当に選びます．なお，

Step１によって $N>1$ が保証されている
Step３によって $S$ の長さが $N-1$ に減少している可能性がある

を考慮すると，この時点で $S$ の長さは必ず $1$ 以上であるため， $S$ が空だったことによるREの心配はありません．

$s_0$ に対応する $T$ の点 $t_0$ を全探索します． $s_0$ を $t_0$ に一致させるような回転移動は， $\theta=\frac{t_0}{s_0}$ として $z\mapsto\theta z$ と一意に定まります．ただし，これが回転移動であるためには $|\theta|=1$ が成り立つ必要があります．なお，

Step３によって $s_0\ne0$ が保証されている

を考慮すると，ゼロ除算によるREの心配はありません． $\theta$ が決まれば，後は各 $s\in S$ に対して $\theta s=t\in T$ となるかを判定すれば良いです． $S$ と $T$ それぞれについて同一の点は含まれないという仮定から，対応する点が重複する心配はありません．

※ 実装上の注意

$x+iy$ はPythonの複素数型を用いて complex(x,y) と表されます． $\theta$ を求める際に複素数同士の割り算を行うため，誤差に注意する必要があります．特に， $|\theta|=1$ および $\theta s=t$ の処理では完全一致 $z=z_0$ が求められますが，条件を緩和した $|z-z_0|\lt\varepsilon$ などに置き換えてやると良いです．

この解法の計算量は，Step４における $t_0,s,t$ の全探索がボトルネックとなり $O(N^3)$ です．

N = int(input())
S = [list(map(int,input().split())) for _ in range(N)]
T = [list(map(int,input().split())) for _ in range(N)]

# Step１
if N==1:
  print('Yes')
  exit()
  
# Step２
cx = 0
cy = 0
for x,y in S:
  cx += x
  cy += y
cx /= N
cy /= N
S = [complex(x-cx,y-cy) for x,y in S]

cx = 0
cy = 0
for x,y in T:
  cx += x
  cy += y
cx /= N
cy /= N
T = [complex(x-cx,y-cy) for x,y in T]

# Step３
if 0 in S and 0 not in T or 0 not in S and 0 in T:
  print('No')
  exit()
if 0 in S and 0 in T:
  S.remove(0)
  T.remove(0)
  
# Step４
s0 = S[0]
eps = 1e-10
for t0 in T:
  theta = t0/s0
  if abs(abs(theta)-1)>eps:
    continue
  ok = True
  for s in S:
    ok_s = False
    for t in T:
      if abs(theta*s-t)<eps:
        ok_s = True
        break
    if not ok_s:
      ok = False
      break
  if ok:
    print('Yes')
    exit()
print('No')

E問題

atcoder.jp

Step１：解法に目処を立てる

「数列が与えられていて $N\le 3000$ という制約なので， $O(N^2)$ の動的計画法（DP）で解きましょう」と言いたいところですが，さすがに乱暴すぎるので思考を少し説明します．DPの本質は「ある問題を解くときに，より規模の小さい問題の答えを利用する」という点にあります．今回の場合，

数列 $A$ の第 $K$ 項までを考えようとしたときに，第 $1$ 項まで，第 $2$ 項まで，…，第 $K-1$ 項までの結果が使えそうな気がする

という直感からDPを選択します．実際にこれが合っているかどうかは以降の考察によって確認されることになるのですが，とりあえずは直感を信じて考察を進めてみます．

Step２：状態数・遷移の定式化

DPの問題が解けるかどうかは，きちんと状態数を決められるかどうかが最初のポイントです．今回の場合，とりあえず問題を見たときに自然に思いつく状態数は

$A_1,\dots,A_i$ を見ていることを表す $i$
$B_1,\dots,B_j$ に分割していることを表す $j$

の2つがあります．さらに， $N\le 3000$ という制約から計算量は $O(N^2)$ であることも予想がついているので，状態数は高々2つです．よって，おそらく上記の2つが正しい状態数になっていそうです．以降では，

$dp[i][j]$ ： $A_1,\dots,A_i$ を $B_1,\dots,B_j$ に分割する場合の数

を考えることにします．

次に，状態の遷移を考えましょう．簡単な例として， $A=(3,1,4,1,5,9)$ に対する $dp[6][3]$ を考えてみます． $A$ の末尾から連続する何項かが $B_3$ に分割されているはずです． $B_3$ に含まれる数の和は $3$ の倍数でなければならないことから， $B_3$ として $(A_6)=(9)$ ， $(A_4,A_5,A_6)=(1,5,9)$ の2通りが考えられます．

f:id:kyaneko999:20210627173451p:plain

$B_3=(A_6)$ という条件の下， $A_1,\dots,A_6$ を $B_1,B_2,B_3$ に分割する場合の数は，残りの $A_1,\dots,A_5$ を $B_1,B_2$ に分割する場合の数 $dp[5][2]$ に等しいです．また， $B_3=(A_4,A_5,A_6)$ という条件の下， $A_1,\dots,A_6$ を $B_1,B_2,B_3$ に分割する場合の数は，残りの $A_1,A_2,A_3$ を $B_1,B_2$ に分割する場合の数 $dp[3][2]$ に等しいです．よって， $dp[6][3]=dp[5][2]+dp[3][2]$ と計算できます．

この結果を一般化すると，

$dp[i][j]=\displaystyle\sum_{k:j|A_{k+1}+\cdots+A_{i}} dp[k][j-1]$

が成り立ちます．なお， $k:j|A_{k+1}+\cdots+A_{i}$ は $A_{k+1}+\cdots+A_{i}$ が $j$ の倍数であるような $k$ を表します．以上により，問題をDPとして定式化することができました．

Step３：DPの高速化

$dp[i][j]$ を計算するために足し合わせる $dp[k][j-1]$ は最大で $O(N)$ 通りあるため，状態数 $O(N^2)$ の各遷移が $O(N)$ の計算量を要し，全体では $O(N^3)$ となってTLEしてしまいます．状態数を減らすことは難しそうなので，各遷移の計算量を $O(1)$ に抑えられないでしょうか．

ここで，連続部分列の要素和に対する典型テクニックである

$A_{k+1}+\cdots+A_{i}=S_{i}-S_{k}$

と表せることを用います．なお， $S_{0}=0$ ， $S_{n}=A_1+\cdots+A_n$ です．これにより， $k:j|A_{k+1}+\cdots+A_{i}$ は $k:S_{k}\equiv S_{i}\ (\mathrm{mod}\ j)$ と同値であることが分かります．よって，

$fact_{i,j}[r]$ ： $k=0,\dots,i-1$ のうち， $S_k$ を $j$ で割った余りが $r$ であるような $k$ についての $dp[k][j-1]$ の和

を用意すれば， $dp[i][j]=fact_{i,j}[S_i\%j]$ と $O(1)$ で計算できます．問題の $fact_{i,j}$ ですが， $j$ を固定すれば $i$ の小さい順に $O(1)$ で更新していくことが出来ます．

Step４：答えの導出

以上により，計算量 $O(N^2)$ のDPを構成することができました．求めたい答えは $\displaystyle\sum_{j=1}^{N} dp[N][j]$ です．計算を行うたびに $10^9+7$ で割った余りを求めることを忘れないようにしましょう．

N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

dp = [[0]*(N+1) for _ in range(N+1)]
dp[0][0] = 1

for j in range(1,N+1):
    fact = [0]*j
    fact[0] = dp[0][j-1]
    S = 0
    for i in range(1,N+1):
        S += A[i-1]
        S %= j
        dp[i][j] = fact[S]
        fact[S] += dp[i][j-1]
        fact[S] %= MOD

ans = 0
for j in range(1,N+1):
  ans += dp[N][j]
  ans %= MOD
print(ans)

2021-06-19

Python初心者のためのABC206

AtCoder

A問題
B問題
C問題
D問題

A問題

atcoder.jp

print文をタイプミスしないように気をつけましょう．サンプルの出力をコピペすると確実です．

N = int(input()) * 108 // 100

if N < 206:
  print('Yay!')
elif N > 206:
  print(':(')
else:
  print('so-so')

B問題

atcoder.jp

$X$ 日目の夜に確認する額が

$1+2+\cdots+X=\frac{X(X+1)}{2}$

であることがポイントです．今回の制約 $N\le 10^9$ では $X\le 10^5$ の範囲を調べれば十分なので全探索が可能です．

N = int(input())
money = 0
for i in range(1,10**5):
  money += i
  if money >= N:
    print(i)
    exit()

もちろん上記の式を使っても良いです．方程式を解いても良いですが誤差には注意しましょう．

C問題

atcoder.jp

条件をみたさない組を数えて全体から引くことを考えます．すなわち，

$1\le i\lt j\le N$
$A_{i}=A_{j}$

となる $(i,j)$ の個数を求めて全体の場合の数 ${}_{N}\mathrm{C}_2=N(N-1)/2$ から引きます．

この問題，どっかで見たことないですか…？

ABC200-Cを思い出してください．これは

$1\le i\lt j\le N$
$A_{i}\%200=A_{j}\%200$

となる $(i,j)$ の個数を数える問題でした．このときは各要素の個数をリストで管理することで解くことができました．しかし，今回の問題では $1\le A_i\le 10^9$ という制約のため，同じようにリストを使うことができません．その代わりに使えるのがdefaultdict(int)です．

from collections import defaultdict

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

# 要素aの個数：D[a]
for a in A:
  D[a] += 1
  
ans = N*(N-1)//2

# Dに記録された各要素の個数を取得（要素自体の値には興味なし）
for v in D.values():
  ans -= v*(v-1)//2

print(ans)

defaultdict(int)は，通常のdictとは違って存在しないキーが呼び出されたときに対応する値を0で初期化する機能を持っています（通常のdictではエラーになります）．

D問題

atcoder.jp

Step１：愚直なシミュレーションを考える

求める値は最小の操作回数ですが，とりあえず最適性は忘れて条件を達成できるような手順を考えてみましょう．入力例１では

1 5 3 2 5 2 3 1

という数列が与えられます．愚直に先頭から見ていきましょう．

$A_1=1$ は $A_8=1$ と一致する必要があります．現時点ですでに一致しているので操作は不要です．
$A_2=5$ は $A_7=3$ と一致する必要があります． $(5,3)$ について一方から他方へ置き換える必要がありそうです．
$A_3=3$ は $A_6=2$ と一致する必要があります． $(3,2)$ について一方から他方へ置き換える必要がありそうです．
$A_4=2$ は $A_5=5$ と一致する必要があります． $(2,5)$ について一方から他方へ置き換える必要がありそうです．
$A_5$ 以降に関しては，対応する値についてすでに調べ終わっている（例えば， $A_5$ に対応するのは $A_4$ ）ので，これ以上調べる必要はありません．

よって， $(5,3), (3,2), (2,5)$ がすべて同じ数字のペアになるように操作をすれば良さそうです．

Step２：操作の意味を考える

Step１で操作が必要な数字のペアが求まりました．これらのペアに操作を施すことのアルゴリズム的な解釈を考えます．ここで思いつくのがグラフに置き換えることです（この発想に至るには経験を積んで慣れるしかないです）．各数字を頂点としてペアの頂点同士を辺で結ぶことにします．そうすると，各操作は辺を1つ選んで辺が結ぶ2つの頂点を1つにまとめること（辺の縮約）に相当します．

f:id:kyaneko999:20210621124814p:plain

この操作を繰り返して辺が無くなれば条件を達成したことになります．

Step３：最小の操作回数を考える

辺で結ばれた頂点のグループ（連結成分）が複数ある場合，異なるグループ間で操作が行われることはないので，各グループごとに考えればいいです．操作を1回行うと頂点は1つ減ります．また，操作を行うことでグループが分離したり合体することはありません．よって， $N$ 頂点からなるグループに対しては必ず $N-1$ 回の操作を行うことになります．以上をふまえると，グラフの連結成分ごとに頂点数を求める問題に帰着されました．

Step４：実装上のテクニック

以上の操作を高速に行うことができるデータ構造がUnion-Find木です．Union-Find木では

グループの結合（グループの分解は不可能）
2つの要素が同グループに属するかの判定

を行うことができます．このようなデータ構造は，あらかじめ手元に準備しておくか，コンテスト中にインターネットで調べて有志が作成したコードを使うと良いです．その際には，必ず競プロ用に作成されたものを使うようにしましょう．そうでないものの中には，高速に動作しなかったり未検証のまま公開されていたりするものがあるので注意です．また，コードによって使い方や機能が違うので，自分に合ったものを選ぶようにしましょう．

def UnionFind(x):
  （x要素からなるUnion-Find木を構成）

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

# union(x,y)：xの属するグループとyの属するグループを結合
# same(x,y)：xとyが同じグループに属するかを判定
U = UnionFind(200001)

ans = 0
for i in range(N):
  if not U.same(A[i],A[N-1-i]):
    ans += 1
    U.union(A[i],A[N-1-i])
print(ans)

2021-06-13

Python初心者のためのABC205

AtCoder

A問題
B問題
C問題
D問題

A問題

atcoder.jp

算数の問題ですね．

$100:A=B:ans\quad\Longleftrightarrow\quad ans=\displaystyle\frac{AB}{100}$

A,B = map(int,input().split())
print(A*B/100)

B問題

atcoder.jp

実際に $A$ を昇順に並び替えて $(1,2,\dots,N)$ と一致するか判定しましょう．

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

if A==list(range(1,N+1)):
  print('Yes')
else:
  print('No')

リストを使って各値の出現回数を管理し， $1$ から $N$ までの値がそれぞれ1回ずつ現れるかどうかを判定しても良いです．

N = int(input())
A = list(map(int,input().split()))
cnt = [0]*(N+1)

for a in A:
  cnt[a] += 1

ok = True
for i in range(1,N+1):
  if cnt[i] != 1:
    ok = False
    
if ok:
  print('Yes')
else:
  print('No')

集合を用いても同様の判定ができます．

N = int(input())
A = list(map(int,input().split()))
S = set(A)
    
if len(S)==N:
  print('Yes')
else:
  print('No')

C問題

atcoder.jp

まず， $A,B$ は負の値を取ることもあり， $C$ は正の値に限られる点に注意しましょう． $A^C$ と $B^C$ を比較する問題ですが $C$ は共通しているので， $C$ を固定した時の関数 $f(X)=X^C$ の挙動を考えてみましょう．

$C$ が奇数のとき， $f(X)$ は狭義単調増加なので $A\lt B\ \Longleftrightarrow\ A^C\lt B^C$ が成り立ちます．
$C$ が偶数のとき， $f(X)$ は $X\ge 0$ の時は狭義単調増加で， $X\lt 0$ の時は $f(X)=f(-X)$ が成り立つので，まとめると $|A|\lt |B|\ \Longleftrightarrow\ A^C\lt B^C$ が成り立ちます．

以上より， $C$ の偶奇に関して場合分けをすると良いことが分かります．

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

def compare(X,Y):
  if X>Y:
    print('>')
  elif X<Y:
    print('<')
  else:
    print('=')
    
if C%2:
  compare(A,B)
else:
  compare(abs(A),abs(B))

D問題

atcoder.jp

各クエリに対して $O(X)$ の計算量がかかるとすると，全体の計算量は $O(QX)$ となります． $Q\le 10^5$ とそこそこ大きいので， $X=N$ などではTLEしてしまいます*1．何とか定数時間または $\log$ 時間に抑えられないでしょうか．

小さいケースで実験してみましょう． $A=(3,7,10)$ のとき小さい方から数えて $K$ 番目の数を $X$ とすると，

$K$	$X$	$X-K$
1	1	0
2	2	0
3	4	1
4	5	1
5	6	1
6	8	2
7	9	2
8	11	3
9	12	3
︙	︙	︙

のようになります．同様に実験することで，

$1\le K\lt A_1$ のとき $X=K$
$A_1\le K\lt A_2-1$ のとき $X=K+1$
$A_2-1\le K\lt A_3-2$ のとき $X=K+2$
　　　　　　　　︙
$A_{N-1}-(N-2)\le K\lt A_{N}-(N-1)$ のとき $X=K+N-1$
$A_{N}-(N-1)\le K$ のとき $X=K+N$

が成り立つことが分かります．よって，以下のようなコードでACできます．

from bisect import bisect_right

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

# 二分探索用のリスト
L = [A[i]-i for i in range(N)]

for _ in range(Q):
  K = int(input())
  X = K + bisect_right(L,K)
  print(X)

この解法における各クエリに対する計算量は $O(\log N)$ です．

別解として，以下のような二分探索が可能です．

from bisect import bisect_right

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

for _ in range(Q):
  K = int(input())
  l = 1
  r = 10**18+10**5
  while r-l:
    mid = (l+r)//2
    cnt = mid - bisect_right(A,mid)  #mid以下の自然数のうちAに含まれないものの個数
    if cnt>=K:
      r = mid
    else:
      l = mid+1
  print(l)

この解法における各クエリに対する計算量は $O(\log(\max(K_i)+N)\log N)$ です．

*1:C++だと間に合うらしいです…．

2021-06-07

Python初心者のためのABC204

AtCoder

A問題
B問題
C問題
D問題

A問題

atcoder.jp

3人の出す手を $x,y,z\in\{0,1,2\}$ （ $0,1,2$ がそれぞれグー，チョキ，パーに対応）とします．この問題は， $x,y$ が与えられたときにあいこになるような $z$ を求める問題です．公式解説では，

$x,y$ は高々9通りしかないので場合分け
$x=y$ のとき $z=x$ ， $x\ne y$ のとき $z=3-x-y$ を出力

という2つの解法を紹介しています．別解として，3人の手があいこになるときは $x+y+z$ が3の倍数になることを利用します．この性質に気づくことができれば，実装量は上記の2つの解法よりも少なく抑えられます．

x,y = map(int,input().split())
print(-(x+y)%3)

B問題

atcoder.jp

そのまま実装するだけです．A問題より簡単かもしれません．それぞれの木から収穫する木の実の個数は，生っている木の実が10個以下かどうかif文を使って場合分けしても良いですが，以下のような表し方も可能です．

N = int(input())
A = list(map(int,input().split()))
ans = 0
for a in A:
  ans += max(0, a - 10)
print(ans)

C問題

atcoder.jp

都市を頂点，道を有向辺とするグラフとみなすことができます．各頂点から探索（幅優先探索または深さ優先探索）を行うことで，その頂点をスタート地点とした場合のゴール地点の候補をすべて調べることができます．頂点数を $N$ ，辺数を $M$ とした場合の全頂点からの探索には $O(N(N+M))$ の計算量がかかり， $M$ は一般には最大で $O(N^2)$ 程度になるため，全体では $O(N^3)$ の計算量を要しTLEしそうな気がします．しかし，今回は $M\le 2000$ という追加制約によって時間制限に間に合うように設定されています．

問題文はよく読みましょう．（スミマセンでした）

from collections import deque

N,M = map(int,input().split())
node = [[] for _ in range(N+1)]
for _ in range(M):
  a,b = map(int,input().split())
  node[a].append(b)

# 幅優先探索
def bfs(v):
  q = deque()
  done = [0]*(N+1)  # すでに探索済かどうか
  q.append(v)
  done[v] = 1
  cnt = 1  # 到達可能な頂点数
  while q:
    x = q.popleft()
    for y in node[x]:
      if not done[y]:
        q.append(y)
        done[y] = 1
        cnt += 1
  return cnt

ans = 0
for v in range(1,N+1):
  ans += bfs(v)
print(ans)

D問題

atcoder.jp

誤った解法（貪欲法）

料理を時間がかかる順にオーブンを割り当てることを考えます．ある料理を割り当てたいとき，今までに割り当てたられた料理にかかる時間の合計が小さい方のオーブンに割り当てれば良さそうな気がします．

N = int(input())
T = list(map(int,input().split()))
T.sort(reverse=True)

oven1 = 0
oven2 = 0
for t in T:
  if oven1 <= oven2:
    oven1 += t
  else:
    oven2 += t

ans = max(oven1, oven2)
print(ans)

この解法はサンプルケースに対してはACですが，実際に提出するとWAになってしまいます．例えば，以下のようなケースが反例になります．

5
3 3 2 2 2

正解は6分（1つ目のオーブンで3分かかる料理を2つ，2つ目のオーブンで2分かかる料理を3つ調理するのが最適）ですが，上記のプログラムでは7分（1つ目のオーブンで3分，2分，2分の料理，2つ目のオーブンで3分，2分の料理を調理することになる）を出力してしまいます．このように，サンプルケースに対しては正解を出力しても解法が根本的に間違っている場合があるので注意しましょう．

正しい解法

$S=\sum_i T_i$ とします．1つ目のオーブンに割り当てる料理の調理時間 $S_1$ が決まると，2つ目のオーブンでの調理時間は自動的に $S-S_1$ と定まります．よって，考えられるすべての $S_1$ に対して $\mathrm{max}(S_1, S-S_1)$ の最小値が答えとなります．すべての $S_1$ を調べるには典型056 のテクニックが使え，計算量は $O(NS)$ であるため時間制限にも間に合います．

N = int(input())
T = list(map(int,input().split()))
S = sum(T)

# 合計調理時間がxになるような料理の割り当て方があるか
dp = [0]*(S+1)
dp[0] = 1

for t in T:
  nxt = [0]*(S+1)
  for x in range(S+1):
    if dp[x]:
      nxt[x] = 1
      if x+t<=S:
        nxt[x+t] = 1
  dp = nxt
        
ans = 3141592
for x in range(S+1):
  if dp[x]:
    ans = min(ans, max(x, S-x))
print(ans)

2021-05-31

Python初心者のためのABC203

AtCoder

A問題
B問題
C問題
E問題

A問題

atcoder.jp

if文を使って条件を素直に実装すると良いです．

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

if a==b:
  print(c)
elif b==c:
  print(a)
elif c==a:
  print(b)
else:
  print(0)

ソートを使って比較回数を減らすのも良いでしょう．

l = list(map(int,input().split()))
l.sort()

if l[1]==l[0]:
  print(l[2])
elif l[2]==l[1]:
  print(l[0])
else:
  print(0)

さらに簡潔に書くことも可能です．

a,b,c = map(int,input().split())
print(0 if (a-b)*(b-c)*(c-a) else a^b^c)

^はXOR演算子と呼ばれるもので詳細は割愛しますが，上記の回答は

結合法則 $(x\wedge y)\wedge z=x\wedge (y\wedge z)$ が成り立つ
$x\wedge x=0$

という性質を利用しています．

B問題

atcoder.jp

まず問題を見たときに考えるべきは愚直解（全探索，シミュレーション，等）が可能であるか？ということです．愚直解のメリットは，難しい思考やテクニックは何も必要とせず素直に実装すれば良い点です．一方のデメリットは，計算量が大幅にかかってしまうです．逆に言えば，計算量の課題さえクリアすれば愚直解が可能なので，計算量がどれくらいになるか見積もってみましょう．

今回の場合，愚直解はすべての $(i,j)$ の組について考える全探索になりますが，高々 $NK\le 9\times 9=81$ 通りしかないので計算量的には余裕です．よって，全探索で実装しましょう．問題はi0jという数値の表し方です．各桁を文字列に変換して結合した後に全体を整数に変換しても良いですが， $i0j = 100\times i + j$ を使うのが簡単でしょう．

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

ans = 0

for i in range(1,N+1):
  for j in range(1,K+1):
    ans += 100 * i + j
    
print(ans)

公式解説にある通り，数学の力を借りれば $O(1)$ で解くことも可能ですが， $O(1)$ の解法を思いついて実装するまでの時間よりも，難しい思考なしで全探索を実行する方が早いと思われます．

C問題

atcoder.jp

Step 1：愚直解の構成

まずは愚直解（シミュレーション）が可能であるかを考えましょう．太郎君は1円あたり1村進むので，すべての友達からお金を回収できるような場合に最大で $K+\sum_i B_i \le 10^9 + 10^9 \times (2\times 10^5) \simeq 10^{14}$ 村進みます．よって，シミュレーションは計算量的に不可能です．

Step 2：愚直解の改善

このシミュレーションに「無駄な計算」はないか考えてみましょう．例えば，

太郎君は現在 $M$ 円持っていて，次の友達がいる村までの距離は $D$ である

という状況では，次の友達がいる村にたどり着けないなら $M$ 回，たどり着けるなら $D$ 回のシミュレーションを行うことになります．しかし，よくよく考えてみると，次の友達がいる村にたどり着けるかどうかは $M$ と $D$ を比較すれば $O(1)$ で判定できます．この判定を行うことで，次に $M$ 回または $D$ 回のシミュレーションを行うことが分かっていれば，それらを1回のシミュレーションにまとめてしまえば良いです．

この方法により，シミュレーションの計算回数を削減することができます．具体的には，太郎君は見かけ上だと友達がいる村だけを飛び飛びで移動する（もしくは，友達がいる村にたどり着けず友達がいない村でシミュレーションが終了する）ことになるので，計算回数は $O(N)$ になります．

シミュレーション自体の計算量は $O(N)$ ですが，友達がいる村を番号が小さい順に探索するために $O(N\log N)$ の計算量をかけてソートする必要があります．

N,K = map(int,input().split())
friend = [list(map(int,input().split())) for _ in range(N)]

friend.sort()

X = 0  # 太郎君が現在いる村の番号
M = K  # 太郎君の所持金

for a,b in friend:
  
  # 太郎君が次の友達がいる村にたどり着くことができるか
  if a - X <= M:
    M += -(a - X) + b  # (a-X)村進んで(a-X)円失うが友達からb円もらえる
    X = a
    
  else:
    X += M
    print(X)
    exit()

# 最後の友達がいる村にたどり着いた後も太郎君は進み続ける
X += M
print(X)

問題を見たときに最初に愚直解を考える習慣をつけておくと，想定解が愚直解の場合に速やかに実装に取り組めるだけでなく，この問題のように想定解を構成するための原型となる解法を手に入れられる場合があります．

E問題

atcoder.jp

※難易度は青diffと初心者向きではないですが，解法を思いつきさえずれば実装は比較的簡単なので解説を書きました．

Step 1：愚直解の構成

まずは愚直解（シミュレーション）を考えます． $i$ が小さい順にすべての $j$ についてシミュレーションを行うので，計算回数は $O(N^2)$ 回です． $N\le 10^9$ なので到底間に合いません．

Step 2：愚直解の改善

C問題と同様，このシミュレーションに「無駄な計算」はないか考えてみましょう． $i+1$ 行目に黒のポーンが1つも置かれていないとします．この場合， $i$ 行目で白のポーンが置かれている可能性がある $j$ の集合を $S_i$ とすると， $S_i = S_{i+1}$ が成り立ちます．よって，

① 黒のポーンが1つも置かれていない行は削除してシミュレーションを行う

ことで，残る行は高々 $M$ 個になるため計算量を $O(NM)$ に減らすことができました．

現在は各行 $i$ に対してすべての列 $j$ についてシミュレーションを行っていますが，その必要はあるのでしょうか．例えば，0行目については $S_0=\{N\}$ です．1行目への遷移を考えるとき，そもそも $(0,j)$ に白のポーンが置かれている可能性がなければ $(0,j)$ からのシミュレーションを行う意味はありません．よって， $(0,N)$ からのシミュレーションのみを行えば良いことになります．同様に考えることで，

② $i$ 行目については $S_i$ に含まれる $j$ についてのみシミュレーションを行う

ようにすれば良いです．後の議論から $|S_i|\le M+1$ が成り立つため，全体の計算量を $O(M^2)$ に減らすことができます．

現在は白のポーン視点でシミュレーションを行っており，白のポーンが遷移する可能性がある列を探索することで $S_i$ を更新しています．一方で，黒のポーン視点で $S_i$ の更新を考えるとどうなるでしょうか．簡単のため， $i+1$ 行目には $j^\ast$ 列目にしか黒のポーンが置かれていない状況を考えてみます．すると， $j\ne j^\ast$ なる $j$ については

$j\in S_i \Longrightarrow j\in S_{i+1}$
$j\notin S_i \Longrightarrow j\notin S_{i+1}$

が成り立つことが分かります．よって， $S_i$ から $S_{i+1}$ への更新を考える上で変更（追加または削除）が行われる可能性がある要素は $j^\ast$ のみということになります．1行に複数個の黒のポーンが置かれている場合も同様に考えられるため，

③ $i$ 行目については黒のポーンが置かれている列 $j$ についてのみ $S_i$ に対する追加または削除を行う

ようにすれば良いです．これにより計算量は $O(M)$ に抑えられ時間制限に間に合うようになりました．

Step 3：実装上のテクニック

以上の議論から，①と③をふまえたプログラムを実装すれば良いことになりました．まず，①を実装するにあたっては，

黒のポーンが1つ以上置かれている行のみを抽出する
各行に置かれている黒のポーンの列番号を管理する

ような機能が必要です．これらはcollections.defaultdictによって同時に実現できます．defaultdict(func)は基本的に通常のdict()と同じですが，

辞書内に存在しないキーが呼び出されたときに，そのキーに対応する要素をfuncで初期化する

という違いがあります．funcには関数が入り，よく用いられるのはint（0で初期化），list（空のリストで初期化）などです．今回は集合を管理するためにdefaultdict(set)を使います．

from collections import defaultdict

N,M = map(int,input().split())
D = defaultdict(set)

# D[i]：i行目に置かれている黒のポーンの列番号の集合
for _ in range(M):
  x,y = map(int,input().split())
  D[x].add(y)

dictおよびdefaultdictには以下のようなメソッドがあります．

# 辞書の各要素は「キー：値」
Dict = {1:2, 'A':'B', 'list':[0,0,0]}

# 辞書のキーを出力
for k in Dict.keys():
  print(k)
> 1
> a
> list

# 辞書の値を出力
for v in Dict.values():
  print(v)
> 2
> B
> [0, 0, 0]

# 辞書の要素を出力
for k,v in Dict.items():
  print(k, v)
> 1 2
> A B
> list [0, 0, 0]

今回は，黒のポーンが1つ以上置かれている行の番号を小さい順に取得したいので，sorted(D.keys())を用いれば良いです．

次に，③の実装を考えます．実際には黒のポーンが1つ以上置かれている行しか考えないため行番号は飛び飛びになる可能性がありますが，便宜上 $S_i$ から $S_{i+1}$ への遷移を考えます．その際， $S_{i+1}$ は $S_i$ をコピーしてから $i+1$ 行目に置かれている黒のポーンを処理していけば良さそうですが，集合のコピーには計算時間がかかってしまいます．そこで，すべての行で同じ集合 $S$ を使い回すようにして，各行に関する遷移では

$S$ に新たに追加される要素
$S$ から削除される要素

を考えるようにします．

from collections import defaultdict

N,M = map(int,input().split())
D = defaultdict(set)

# D[i]：i行目に置かれている黒のポーンの列番号の集合
for _ in range(M):
    x,y = map(int,input().split())
    D[x].add(y)
    
S = set()  # 白のポーンが置かれている可能性がある列番号の集合
S.add(N)

for i in sorted(D.keys()):
    new = set()  # Sに新たに追加される列番号
    rem = set()  # Sから削除される列番号
    for j in D[i]:
        if j not in S and (j-1 in S or j+1 in S):
            new.add(j)
        if j in S and j-1 not in S and j+1 not in S:
            rem.add(j)
    for j in new:
        S.add(j)
    for j in rem:
        S.remove(j)

print(len(S))

辞書のキーのソートの部分がボトルネックとなり，全体の計算量は $O(M\log M)$ です．

2021-05-22

Python初心者のためのABC202

AtCoder

A問題
B問題
C問題
D問題

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)