AtCoder Regular Contest 107 (A,B,C) 感想 - 平凡な社会人の日記

ARC107、いつも通り全然できませんでした！問題は画像として貼り付けてあります。先に解きたい人は解いてから見てねー。（定型文）

A問題(Simple Math)
B問題
C問題(Shuffle Permutation)
感想
- Reference

A問題(Simple Math)

f:id:physics-heibon:20201101001223p:plain
$10^9\times 3$ 回の足算を繰り返せばいいんじゃないんですか！？そうすると間に合わないので、式変形します。 $\sum_a\sum_b\sum_c abc = \left(\sum_a a \right) \left(\sum_b b \right) \left(\sum_c c\right)$ となるので、先に計算しといて掛ければいいです。（この問題、difficulty 82って本当ですかAtCoder Problemsさん‥。）

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

mod = 998244353
a = A*(A+1)//2
b = B*(B+1)//2
c = C*(C+1)//2

print(a*b*c%mod)

B問題

f:id:physics-heibon:20201101001439p:plain

全然わかりませんでした。半分全列挙という典型問題らしいです。 $a + b = K + c + d$ と式変形してやります。例えば $a + b = x ~(1\leq a\leq N,~ 1\leq b \leq N)$ を満たすような自然数 $a,b$ の組は $min(N-1,~2N+1-x )$ 個あります。(これが思いつけば後は一瞬なのですが、思いつきませんでした。) $x$ を固定して考えると、 $a+b = x$ となるような $a,b$ の組みを求めて、それに $c+d = x-K$ となるような $c,d$ の組みをかければいいでしょう。後は $x \in [2,2N$ ] の範囲を走らせれば終わりです。

def f(N,x):
    return min(x-1,2 * N + 1 - x)

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

ans = 0
for i in range(2,2*N+1):
    if 2*N >= i-K >= 2:
        ans += f(N,i) * f(N,i - K)
    
print(ans)

C問題(Shuffle Permutation)

f:id:physics-heibon:20201101003425p:plain

まず、行と列のスワップは独立に行えます。（この行とあの行を入れ替えたら、あっちの列とこっちの列のスワップが可能になったー！なんて事はありません。）したがって、以下は行について考えます。まず、スワップ可能な行を探します。
そうしてスワップできる行を線で結んだりしていろいろいじってると、次のようなことが分かります。例えば、1行目と2行目の直接のスワップが不可能で、1と3、2と3がスワップ可能の時、[1,2,3]→[3,2,1]→[2,3,1]→[2,1,3] として、結果的に1と2をスワップしたことになります。したがって、スワップできる行同士をグループにすれば、その要素数の階乗分だけ新しい行列が作れます。グループ化は、コストなしの向行グラフなのでUnionFindで管理してやればいいです。

from collections import defaultdict
from math import factorial
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members

    def __str__(self):
        return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())

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

a = [ [] for _ in range(N)]
mod = 998244353
for i in range(N):
    a[i] = (list(map(int, input().split())))

Tate = UnionFind(N)
Yoko = UnionFind(N)

for i in range(N):
    for j in range(i+1,N):
        tmp = 0
        for k in range(N):
            if a[i][k] + a[j][k] > K:
                break
            tmp += 1
        if tmp == N:
            Yoko.union(i,j)
        #print(Yoko)

for i in range(N):
    for j in range(i+1,N):
        tmp = 0
        for k in range(N):
            if a[k][i] + a[k][j] > K:
                break
            tmp += 1
        if tmp == N:
            Tate.union(i,j)

ans = 1
for i in range(Tate.group_count()):
    tmp = list(Tate.all_group_members().values())
    #print(tmp)
    ans *= factorial(len(tmp[i]))%mod

for i in range(Yoko.group_count()):
    tmp = list(Yoko.all_group_members().values())
    # print(tmp)
    ans *= factorial(len(tmp[i]))%mod


# print(Tate.all_group_members())
# print(Yoko.all_group_members())
print(ans%mod)