Python初心者のためのABC206

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

A問題

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)

きゃねろぐ

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

Python初心者のためのABC206

A問題

B問題

C問題

D問題