Python初心者のためのABC207

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

A問題

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

# 解法１
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)

きゃねろぐ

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

Python初心者のためのABC207

A問題

B問題

C問題

D問題

E問題