Xenous の精進記録

AtCoder関連他、学習したことの記録です。

ABC206 参加記録

  • 3完0ペナ 8分でした
  • Dに関してはサンプルの値に引っ張られすぎて、正しい考察ができていなかったのが反省です。
  • E問題は AND 条件を分割して考えることを意識しようと思います。

A - Maxi-Buying

 N 円に 1.08 倍して小数点以下を切り捨てます。その値と 206 を比較して、問題文にあるような出力をします。

from math import floor

N = int(input())
res = floor(N * 1.08)
if res > 206: print(":(")
elif res == 206: print('so-so')
else: print('Yay!')

B - Savings

 10^{5} から  10^{6} の間の加算を行うだけでも、 10^{10} は超えます。( 10^{5} 9\times 10^{5} 加算することになるので)

したがって順に足していき、初めて  N を超えたら終了させれば良いです。

N = int(input())
res = 0
for i in range(1, 10**8+1):
    res += i
    if res >= N:
        print(i)
        break

C - Swappable

 A_i \neq A_j となる (i,j) の組の数は、全体(全ての  (i, j) の組の数)から  A_i = A_j となる (i, j) の組の数を引いて求めることができます。

 A_i = A_j となる (i, j) の組の数は、 A の要素の出現回数をカウントして、「同じ数を2つ選ぶ」場合を考えれば求めることができます。

N = int(input())
A = list(map(int, input().split()))
counterA = Counter(A)
ans = (N*(N-1))//2
res = 0
for _, cnt in counterA.items():
    if cnt >= 2: res += (cnt*(cnt-1))//2
ans -= res
print(ans)

D - KAIBUNsyo

解説AC です。

まず、サンプルで考えてみると、以下のように、回文になっていないところを確認することができます。

f:id:Xenous:20210620152647p:plain
回文になっていないところをペアにした図

ここで、5 と 3 と 2 は数珠繋ぎになっています。5 と 3 と 2 のうち、どれかひとつの数字に全て変換しないと回文にすることができません。この場合の答えは、回文にならない数字の集合の大きさから1引いたものになります。

さて、以下の場合はどうでしょうか。

f:id:Xenous:20210620153249p:plain
回文になっていないところをペアにした図 その2

この図では、2と6、1と3と5 をまとめて同じ数字にする必要はなく、それぞれのグループで、ひとつの数字に変換させれば良いです。

グループの管理は unionfind を使えばできます。制約より  A_i \leq 2\times 10^{5} なので、 A の値でグループ管理します。 あとは各グループの大きさから1引いたものが最小回数になります。

本番ではこのパターンが抜けていました。。気づけなかったのが残念すぎます。

D問題 提出コード

# UnionFind は細部を省略して記載
class UnionFind():
        """
        Parameters:
        -----------
        n: int
            要素数
        parents: list
            各要素が属する親の要素番号
        grouping: set
            親番号の集合
        rank: list
            親の rank を保持するためのリスト
        size: list
            親の size を保持するためのリスト
        """

    def find(self, x:int) -> int:
        """
        要素 x の親の要素を見つけるメソッド
        """

    def union(self, x:int, y:int) -> None:
        """
        要素 x, y の属するグループを結合するメソッド
        """

    def msize(self, x:int) -> int:
        """
        要素 x の属するグループの大きさを返すメソッド
        """


def main():
    N = int(input())
    A = list(map(int, input().split()))
    uf = UnionFind(max(A)+1)
    ans = 0
    for i in range(N//2):
        if A[i] != A[N-i-1]:
            uf.union(A[i], A[N-i-1])
    for g in uf.grouping:
        ans += uf.msize(g)-1
    print(ans)


if __name__ == "__main__":
    main()

ちなみに、もし  A の値が  10^{9} まで取り得るときでも、 A の値を圧縮する(要素の大きさの順位を  A の要素にする)ことで、unionfind で扱える大きさに縮小させて、以下同様に解くことができます。

E - Divide Both

解説AC です。本番では D がイマイチ解けなさそうだったので逆転を狙って E に取り組んでいました。

まず「最大公約数」とか言われると扱いにくいので、基本的な言い換えをします。

  •  \gcd(x, y) = g が成り立つ( x y の最大公約数が  g)」なら、「 x y g の倍数」

これは逆は成り立たないことに注意します。

さて、問題文の条件について見てみます。

  •  L \leq x, y \leq R
  •  g x y の最大公約数とすると、以下が成り立つ
    •  g \neq 1 ... ① かつ  \frac xg \neq 1 ... ② かつ  \frac yg \neq 1 ... ③

① は最大公約数が 1 でないことを意味します。 x, y はともに何かしらの 1 でない自然数の倍数になっているということになります。

②③は、最大公約数  g x または  y が同じ値にならない、と言えます。例えば  x = 6, y = 12 のとき、  \gcd(x,y) = 6 になりますが、これは②を満たしていません。

次にどのように組み立てていくかですが、まずは  g によって場合分けします。すなわち、最大公約数が 2 のときの  (x, y) の組の数、最大公約数が 3 のときの  (x, y) の組の数、... と見ていきます。そこで  (x, y) の組の数を洗い出して、②③を満たさないものを除いていきます。

最初の言い換えを使って、  \gcd(x, y) = 2 だから、 x, y は 2 の倍数。 (x, y) の組の数は( L, R の範囲内の)2の倍数の組み合わせだ、とやりたいところですが、例えば  x = 8, y = 12 はどちらも 2 の倍数でありながら  \gcd(x,y) = 4 になります。このようなパターンは不適です。

数えたいのは、 \gcd(x, y) がちょうど  2 になる  (x, y) の組の数です。先程の求め方では、 \gcd(x, y) = 4, 6, 8, ... = 2k のパターンが含まれています。したがって、大きい方から順に計算していき、除いていくのが良さそうです。

以上より、まずは最大公約数  g の大きい方から  (x, y) の組の数を洗い出していきます。 L, R の範囲だけ考えればよく、最大公約数は  R が最大ですから、 R から  2 (①より  1 の場合は考えなくて良い)まで見ていきます。

 \gcd(x, y) = R となるのは、( x y R の倍数と言えるので) (R,R) だけになります。 \frac R2 まではこのように 1 通りになります。

 \gcd(x, y) = k については、 k の倍数で構成された数字の組が候補になります。 R までの  k の倍数の数字の個数を  Z_k とおくと、候補の組は  Z_k^{2} 個あります。ちょうど  \gcd(x, y) = k となるには、今まで計算した  \gcd(x, y) = mk m は2以上の整数)の場合の数を除きます。

例えば、下記の例で、例えば  \gcd(x, y) = 3 を考えます。候補の数字は、3の倍数なので、3と6です。 これらの数字を使ったペアの作り方は (3, 3), (3, 6), (6, 3), (6, 6) の4通りあります。各  g について計算すれば  Z_g^{2} の行が埋まります。

そして、ちょうど  \gcd(x, y) = 3 となる組の数を調べるため、最後の行の後ろから埋めていきます。8から5までは2倍すると  R を超えるので 1 通りのままです。 \gcd(x, y) = 4 は、 \gcd(x,y) = 8 の場合に 1 通りダブりが生じるので、それを除いて、3 通りです。 \gcd(x, y) = 3 も同じ要領で計算して 3 通りとわかります。

 \gcd(x, y) = 2 となる組みも同様に、 \gcd(x, y) = 4, 6, 8 となる場合にダブりが生じているのでそれを除いて 4 通りになります。

f:id:Xenous:20210620230542p:plain
計算のイメージ

次に、②③の条件を満たさないものを除きます。

②③の条件は、 g = x または  g = y となる場合で、これは  g L, R に含まれているときに除外する必要があります。 除くのは  (g, g) と、 (g, kg) k = 2, 3, \cdots)とその逆の場合です。

以上で全ての条件を満たした  (x, y) の組を数え上げることができました。

実装では、 \gcd(x, y) = g を調べる部分をエラトステネスの篩の要領でテーブルを作ることができます。計算量は  O(R\log{R}) です。

E問題 提出コード

def main():
    L, R = map(int, input().split())
    table = [0] * (R+1)
    for k in range(2, R+1):
        cnt = 0; i = 1
        while k*i <= R:
            if L <= k*i <= R: cnt += 1
            i += 1
        table[k] = cnt
    gcnt = [c**2 for c in table]
    
    for g in range(R, 1, -1):
        i = 2
        while g*i <= R:
            gcnt[g] -= gcnt[g*i]
            i += 1
    
    ans = 0
    for g, t in enumerate(gcnt):
        if g < L: ans += t
        elif L <= g <= R:
            if t <= 1: continue
            ans += t - (table[g]-1)*2 - 1
    print(ans)


if __name__ == "__main__":
    main()