2021-09-04

ABC217 参加記録

5完0ペナ 66分でした

A - Lexicographic Order

辞書順での比較は python では <、 > でできます。単純に比較して答えとします。

S, T = input().split()
if S < T: print('Yes')
else: print('No')

B - AtCoder Quiz

集合として持っておき、同じものを除いていき、残ったものを答えとします。

S = set(['ABC', 'ARC', 'AGC', 'AHC'])
tmp = input(); S.remove(tmp)
tmp = input(); S.remove(tmp)
tmp = input(); S.remove(tmp)
S = list(S)
print(S[0])

C - Inverse of Permutation

数列 $p$ で各要素の位置を持っておき、ソートした後に、その位置を出力すれば良いです。

N = int(input())
p = list(map(int, input().split()))
q = []
for i, pp in enumerate(p):
    q.append((i, pp))
q.sort(key=lambda x: x[1])
ans = []
for i, pp in q:
    ans.append(i+1)
print(*ans)

D - Cutting Woods

答えに辿り着くまで時間を要しました。

実装方針としては、分割していくよりも、逆に合体させていく方が考えやすかったので、そちらで実装します。具体的には、クエリを逆順に見て、

$c = 1$ なら、 $x$ で木材を結合する
$c = 2$ なら、 $x$ が含まれる木材の長さを答える。

となります。

まず分割が起こった $x$ をリストとして保持しておきます。これらに最後尾の $L$ を入れて、unionfind で結合を管理します。

f:id:Xenous:20210904233757p:plain — $x$ と unionfind と長さの対応づけ

unionfind の要素と、その木材の長さを対応づけしておきます。結合が発生したら、結合前の長さの和を、親の方に代入するような形で持っておきます。

次に、 $x$ が含まれる木材の長さですが、 $x$ が含まれる木材に対応する unionfind の要素番号を見つけて、そこから長さを参照するようにします。例えば $x_{d}$ を含む木材は、分割をした座標のリストを二分探索することで、unionfind の要素番号との対応づけをすることができます。

最後に、元とは逆の順序で木材の長さを答えているので、これを元に戻して出力すれば答えです。全体として $O(Q\log{Q})$ で実行できます。

提出コード

from bisect import *
import sys

input = sys.stdin.readline


class UnionFind():
    """
    unionfind を扱うクラス (0-index)

        Parameters:
        -----------
        n: int
            管理するデータの要素数
    """
    def __init__(self, n:int):
        """
        Parameters:
        -----------
        n: int
            要素数
        parents: list
            各要素が属する親の要素番号
        grouping: set
            親番号の集合
        rank: list
            親の rank を保持するためのリスト
        size: list
            親の size を保持するためのリスト
        """
        self.n = n
        self.parents = [-1]*n
        self.grouping = set(range(n))
        self.rank = [0]*n
        self.size = [1]*n


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

        Parameters:
        -----------
        x: int
            要素番号
        
        Returns:
        --------
        int
            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:int, y:int) -> None:
        """
        要素 x, y の属するグループを結合するメソッド
        
        Parameters:
        -----------
        x, y: int
            結合対象の要素番号
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            # rank(x)の方が小さい場合は, xをくっつけて, y を親にする
            self.size[y] += self.size[x]
            self.parents[x] = y
            self.grouping.difference_update(set([x]))
        else:
            # そうでないときは, y をくっつけて, x を親にする
            self.size[x] += self.size[y]
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.grouping.difference_update(set([y]))


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

        Parameters:
        -----------
        x: int
            要素番号
        
        Returns:
        --------
        int
            x の属するグループの大きさ(要素数)
        """
        return self.size[self.find(x)]


def main():
    L, Q = map(int, input().split())
    query = []
    div = [L]
    for _ in range(Q):
        c, x = map(int, input().split())
        query.append((c, x))
        if c == 1: div.append(x)
    
    N = len(div)
    div.sort()
    x_to_uf = dict()
    for i, x in enumerate(div):
        x_to_uf[x] = i
    uf = UnionFind(N)

    uf_to_dist = dict()
    bf = 0
    for i in range(N):
        af = div[i]
        uf_to_dist[i] = af - bf
        bf = af

    ans = []
    for _ in range(Q):
        c, x = query.pop()
        if c == 1: # 合体させる
            a = uf.find(x_to_uf[x]); b = uf.find(x_to_uf[x]+1)
            dist_a = uf_to_dist[a]; dist_b = uf_to_dist[b]
            uf.union(a, b)
            uf_to_dist[uf.find(a)] = dist_a + dist_b
        else: # 長さを答える
            a = uf.find(x_to_uf[div[bisect_left(div, x)]])
            ans.append(uf_to_dist[a])
    ans.reverse()
    print(*ans, sep='\n')


if __name__ == "__main__":
    main()

E - Sorting Queries

操作のうち、最後尾への追加、先頭の取り出しと削除については、deque を使用すれば $O(1)$ で実行可能です。しかしソートをそのままやってしまうと、ソート自体に $O(N\log{N})$ かかるので、全体で $O(QN\log{N})$ で実行時間に間に合わない場合が出てきます。（ $N$ は配列の要素数）

よくよく考えると、ソートした後取り出す数字は、小さい順になります。これはソート時の要素数の回数までは必ず成立します。したがって、この部分だけは heapq を使って、 $O(\log{N})$ で追加・取り出しを行うようにします。

ソートが起こったら、deque にある要素を heapq 側に入れていく、という操作になります。

全体として $O(Q\log{Q})$ となります。

提出コード

from collections import deque
from heapq import *

def main():
    Q = int(input())
    res_deque = deque([]); cnt = 0
    res_heap = []
    heapify(res_heap)
    for _ in range(Q):
        query = list(map(int, input().split()))
        if query[0] == 1:
            res_deque.append(query[1])
        elif query[0] == 2:
            if len(res_heap) == 0:
                ans = res_deque.popleft()
            else:
                ans = heappop(res_heap)
            print(ans)
        else:
            for _ in range(len(res_deque)):
                x = res_deque.popleft()
                heappush(res_heap, x)

if __name__ == "__main__":
    main()

F - Make Pair

区間DPで解けそうな問題でしたが時間が間に合わずでした。後日解きます。

2021-08-29

ABC216 参加記録

AtCoder コンテスト参加記録 ABC

5完1ペナ 92分でした

A - Signed Difficulty

. で分離して取得するのが簡単です。また、小数 $X.Y$ で必ず小数部分の $Y$ があるので例外処理など書かずに安心して取得できます。

出力に文字（ - や + ）を含める必要があるので、 $X$ は文字列として扱います。

X, Y = map(int, input().split('.'))
if Y <= 2: print(str(X)+'-')
elif Y <= 6: print(str(X))
else: print(str(X)+'+')

B - Same Name

誰が誰と重複したかなどは考えずに答えられそうです。

順に名前を取得していき、前に一致するものがあったら Yes として出力します。全て格納できたら No です。

また姓名の両方が一致している場合なので、特に分けて保存する必要もありません。

N = int(input())
nameset = set()
for _ in range(N):
    name = input()
    if name in nameset: 
        print('Yes')
        return
    else: nameset.add(name)
print('No')

C - Many Balls

よく出る典型の問題の易しめ版ですね。

$N$ から 0 にしていくことを考えます。今回は最短の方法が直感的にもわかりやすく、奇数だったら 1 を引く、偶数だったら 2 で割る、とすれば良いです。

行った操作を記録して、最終的に出力するときには逆順にして出せばOKです。

N = int(input())
ans = []
while N > 0:
    if N%2 == 0:
        N //= 2
        ans.append('B')
    else:
        N -= 1
        ans.append('A')
ans.reverse()
print(''.join(ans))

D - Pair of Balls

実装問題でした。

$M$ 本の筒は全体で持っておいて、実際に取り出すシミュレーションをする方針にしました。ちなみに取り出す順番は特に関係なく、見つけた順に取り出してしまって良いはずです（ダメな例を作れなかったという消極的な理由でした）。

それぞれの筒の一番上のボールにおいて、どの色が同じになるか？を $O(\log{M})$ 以下で見つける必要があります。私はどの色が何番めの筒にあるか？を辞書型で持っておき、取り出した後の色から取得できるようにしました。こうすることで筒の上のボールを探索することなく、この辞書から直接参照することができます。

ということで、シミュレーションは $O(N+M)$ で実行できました。各配列で、何もないのに取り出そうとするエラーには注意して実装します。

提出コード

from collections import deque
import sys

input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    colormap = dict()
    field = []
    checker = [0] * (N+1)
    que = deque([])
    for k in range(M):
        _ = int(input())
        C = list(map(int, input().split()))
        checker[C[0]] += 1
        if checker[C[0]] == 2: que.append(C[0])
        for c in C:
            if c not in colormap: colormap[c] = [k]
            else: colormap[c].append(k)
        C.reverse()
        field.append(C)
    
    # 同じ数字が同じ筒に入っていないかチェック
    for a, b in colormap.values():
        if a == b:
            print('No')
            return

    while que:
        # que を取り出す
        p = que.popleft()
        
        # 取り出した que から map を見て、pop する
        checker[p] -= 2
        j = colormap[p]
        field[j[0]].pop()
        field[j[1]].pop()
        # 次も同じ値なら一回入れてスキップ
        if len(field[j[0]]) > 0 and len(field[j[1]]) > 0:
            if field[j[0]][-1] == field[j[1]][-1]:
                que.append(field[j[0]][-1])
                checker[field[j[0]][-1]] += 2
                continue
        # そうじゃない場合
        for i in range(2):
            if len(field[j[i]]) > 0:
                a = field[j[i]][-1]
                checker[a] += 1

                # 筒のボールのチェックをする. 当たりならqueに入れる
                q, r = colormap[a]
                if q == j[i]: s = r
                else: s = q
                if field[s][-1] == a: que.append(a)

    # 残数チェック
    for l in field:
        if len(l) > 0:
            print('No')
            return
    print('Yes')


if __name__ == "__main__":
    main()

ABC215 参加記録

ABC AtCoder コンテスト参加記録

4完1ペナ 39分でした

A - Your First Judge

完全一致というところに気をつけて実装します。python では == で良いです。

S = input()
if S == 'Hello,World!': print('AC')
else: print('WA')

B - log2(N)

問題タイトルは計算量ですね。 $10^{18}$ であっても、 $2^{k}$ 側の $k$ は $60$ くらいで $10^{18}$ を超えます。従ってそれ以上の数でループさせて確かめれば良いです。

N = int(input())
for k in range(1000):
    if 2**k > N: break
print(k-1)

C - One More aab aba baa

$S$ は 8 文字なので、並び替えをしても間に合います。その後、重複を除いて $K$ 番目を指せば答えです。計算量は $O(S!)$ です。

S, K = input().split()
S = list(S)
K = int(K)
permS = list(set(permutations(S, len(S))))
permS.sort()
print(''.join(permS[K-1]))

D - Coprime 2

各 $i$ で $\gcd(A_i, k) = 1$ を満たすには、それぞれの $A_i$ の素因数を $k$ が持っていないようにしないといけないです。 $A_i$ を素因数分解して素因数の集合として持ちます。集合の大きさは、最大でも $10^{5}$ 以下の素数の個数分で 10000 個ほどになります。

あとは $k$ を回した際、この素因数の集合で割り切れないことを確認していけば良いです。最悪計算量は $10^{9}$ になってしまいますが、割り切れないことを確認する際にほとんどの数は 2, 3 個の素因数の集合の要素を見るだけでスキップされるので重くなりません。

提出コード

# 素因数分解
def prime_factorize(n:int) -> list:
    """
    素因数分解を O(\sqrt{n}) で行う

        Parameters:
        -----------
        n: int
            2以上の整数
        
        Returns:
        --------
        a: list
            n の素因数のリスト
        e.g.
            input: 2940
            output: [2, 2, 3, 5, 7, 7]
    """
    assert n > 1, 'assert n > 1'
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    divset = set()
    for a in A:
        if a == 1: continue
        divset.update(set(prime_factorize(a)))
    divlist = list(divset)
    divlist.sort()
    ans = []
    for k in range(1, M+1):
        flag = True
        for p in divlist:
            if k%p == 0:
                flag = False
                break
        if flag: ans.append(k)
    ans.sort()
    print(len(ans))
    print(*ans, sep='\n')


if __name__ == "__main__":
    main()

F - Dist Max 2

これも正直よく見る形かなと思います。後日復習したいと思います。

2021-08-14

ABC214 参加記録

AtCoder コンテスト参加記録 ABC

4完0ペナ 33分でした
最近全く精進できていませんでしたが結果オーライでよかったです。

A - New Generation ABC

新しい問題形式にちなんだ内容でしたね。記載通りのルールに従って実装します。

N = int(input())
if N <= 125:
    print(4)
elif N <= 211:
    print(6)
else:
    print(8)

B - How many?

見た目が難しい問題です。制約を見ると $a, b, c$ は非負整数で和が $100$ 以下になることがわかります。ということで、雑に $0 \leq a, b, c \leq 100$ としてループさせると計算量は $10^{6}$ くらいになるので、これで回して数え上げてしまいます。

S, T = map(int, input().split())
ans = 0
for a in range(101):
    for b in range(101):
        for c in range(101):
            if a + b + c > S or a*b*c > T:
                break
            ans += 1
print(ans)

C - Distribution

これもひと工夫要る問題でした。

宝石は高橋くんが配ります。そのタイミングと、宝石が隣の人から回ってくるタイミングを比較することが第一方針です。

「宝石が隣の人から回ってくるタイミング」について考えるために、高橋くんの宝石配布時間が最も早いものを考えてみます。例えば高橋くんが 1 番の人に最も早く宝石を渡すとき、2番の人は高橋くんから受け取るか、1番の人から回ってくるかのどちらかです。次の人は、これらのうち早いタイミングで来た方だけ考えれば良いことがわかります。

ということで、高橋くんの宝石配布時間が最も早いところから順繰りに比較することで、 $i$ 番目の人が初めて宝石をもらう時刻を調べることができます。これは $O(N)$ なので間に合います。

N = int(input())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
tidx = T.index(min(T))

ans = [float('inf')] * N
ans[tidx] = T[tidx]

for k in range(1, N):
    ans[(tidx+k)%N] = min(T[(tidx+k)%N], ans[(tidx+k-1)%N] + S[(tidx+k-1)%N])

print(*ans, sep='\n')

D - Sum of Maximum Weights

和の問題です。典型的なパターンを掴んだのか早めに解くことができました。

木の頂点2つ $u, v$ を選んだときの最短パス上に含まれる辺の重みの最大値 $f(u, v)$ について次の和を求めます。

$\sum_{i=1}^{N}\sum_{j=i+1}^{N} f(i, j)$

言い換えると、ある重み $w$ が最短パス上で最大の重みとして何回出てくるか？となります。

これを考えるにあたって、計算対象がパスの重みの最大値であることから、与えられた辺の重みの小さい方から考えていくのが良さそうです。下記の図のようなイメージです。

f:id:Xenous:20210814225238p:plain — 数え上げのイメージ

最も右の図において、 $f(u, v) = 20$ となるパスの数は、 $u, v$ の連結する前の頂点数の掛け算で計算できます。連結した頂点数の管理には unionfind を使えば良いです。全体の計算量は $O(N)$ です。

提出コード

class UnionFind():
    """
    unionfind を扱うクラス (0-index)

        Parameters:
        -----------
        n: int
            管理するデータの要素数
    """
    def __init__(self, n:int):
        """
        Parameters:
        -----------
        n: int
            要素数
        parents: list
            各要素が属する親の要素番号
        grouping: set
            親番号の集合
        rank: list
            親の rank を保持するためのリスト
        size: list
            親の size を保持するためのリスト
        """
        self.n = n
        self.parents = [-1]*n
        self.grouping = set(range(n))
        self.rank = [0]*n
        self.size = [1]*n


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

        Parameters:
        -----------
        x: int
            要素番号
        
        Returns:
        --------
        int
            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:int, y:int) -> None:
        """
        要素 x, y の属するグループを結合するメソッド
        
        Parameters:
        -----------
        x, y: int
            結合対象の要素番号
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            # rank(x)の方が小さい場合は, xをくっつけて, y を親にする
            self.size[y] += self.size[x]
            self.parents[x] = y
            self.grouping.difference_update(set([x]))
        else:
            # そうでないときは, y をくっつけて, x を親にする
            self.size[x] += self.size[y]
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.grouping.difference_update(set([y]))


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

        Parameters:
        -----------
        x: int
            要素番号
        
        Returns:
        --------
        int
            x の属するグループの大きさ(要素数)
        """
        return self.size[self.find(x)]


def main():
    N = int(input())
    edges = []
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        edges.append((u-1, v-1, w))
    
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(N)

    ans = 0
    for u, v, w in edges:
        ans += w * uf.msize(u) * uf.msize(v)
        uf.union(u, v)
    print(ans)


if __name__ == "__main__":
    main()

E - Packing Under Range Regulations

計算量が厳しく思いつきませんでした。

2021-07-25

バーチャル参加 ABC127

ABC バチャ参加記録

4完0ペナ 25分でした

A - Ferris Wheel

問題文に記載がある通りに実装します。

A, B = map(int, input().split())
if 6 <= A <= 12: print(B//2)
elif A <= 5: print(0)
else: print(B)

B - Algae

$x_{2000}$ が与えられているので、そこから定義通り順に計算することができます。

r, D, x = map(int, input().split())
for _ in range(10):
    x = r*x - D
    print(x)

C - Prison

色々な区間が与えられる中で、全ての区間に含まれる点の数を答える問題です。与えられた区間の左側の最大値と、右側の最小値を管理します。この2つの間にある番号のカードは全てのゲートを通過できます。

N, M = map(int, input().split())
Lmax = 1; Rmin = N
for _ in range(M):
    L, R = map(int, input().split())
    Lmax = max(L, Lmax)
    Rmin = min(R, Rmin)
ans = max(0, Rmin - Lmax + 1)
print(ans)

D - Integer Cards

与えられたカードを順番関係なく書き換えることができる権利がいくつか与えられ、書き換えた後の和が最大になるようにしたときの和の値を答える問題です。

元々のカードに書いてある数字とその個数、書き換えられるカードの数字とその回数を全てまとめてしまい、大きい方から $N$ 枚になるまでとってしまえば、状況は同じになります。

提出コード

from collections import Counter

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    counterA = Counter(A)
    for _ in range(M):
        B, C = map(int, input().split())
        if C in counterA: counterA[C] += B
        else: counterA[C] = B
    counterAitems = list(counterA.items())
    counterAitems.sort(key=lambda x: x[0], reverse=True)
    idx = 0; ans = 0
    for c, b in counterAitems:
        if N-idx < b: 
            ans += c*(N-idx)
            break
        else: 
            ans += c*b
            idx += b
    print(ans)


if __name__ == "__main__":
    main()

E - Cell Distance

2021/9/4 追記

解答を見てからしばらく経って自分で解いてみました。この手の問題は「言い換え（= 和をとる順番を変える）」で解けるパターンが多いですね。

まず、この問題を解く方針としてあり得そうなのが以下です。

$i$ と $j$ （もしくは $x$ 軸と $y$ 軸）を分離する
総和の順序を(可能な場合に)入れ替える
式変形して引き算の形にする（包徐原理）

第一ステップ：和の取り方を変える

ストレートに考えると、次のように計算したいです。

まず配置を固定する。
配置されたコマに番号を振って、それぞれ $|x_{i} - x_{j}| + |y_{i} - y_{j}|$ を計算して足す。

この方針の計算量は $O(K^{2})$ ですが、コマの数は $K \leq N \times M \leq 2 \times 10^{5}$ なので、間に合いません。

ここから、和の取り方を変えてみます。

配置を固定するのではなく、先に全て洗い出してしまいます。全ての配置がわかったら、距離 $d$ のものがいくつあるかを数えて足し合わせる、という風に考えます。

※ ここでまだ距離 $d$ が明確に定義していません。2点の $|x_{i} - x_{j}| + |y_{i} - y_{j}|$ は、本当はそれぞれの軸に分解して考えたいですが、今の段階でできるかわからないので、これを距離 $d$ だと一旦考えておくことにします。

f:id:Xenous:20210904105251p:plain — 和の考え方のイメージ

さて、和の取り方を変えてみたものの、まだ途方もない感じがします。さらに考えてみます。

距離 $d$ のものがいくつあるかを計算する際、 $K$ 個の配置のまま考えると大変そうですが、よくよく考えると2つのコマのペアだけ見ていれば良いです。

そして、「そのペアが何回現れるか」が知りたいことです。

f:id:Xenous:20210904111519p:plain — 2つのコマに注目するイメージ

ここから、「2つ配置する × それが全体の配置の中で現れる回数」に対して、距離を計算すると答えになることがわかります。式にすると $_{N\times M}C_{2} \times _{N\times M-2}C_{K-2}$ です。

$_{N\times M}C_{2}$ ：マス全体から2つ選んでコマを置く。
$_{N\times M-2}C_{K-2}$ ：選んだ2つを除いて、残りのコマを置く場合の数

以上より、和の計算方法を、配置を固定してからではなく、2つのコマが配置全体のうち何回現れるか？という取り方に変えました。

しかし、 $_{N\times M}C_{2}$ は $O((NM)^{2})$ です。まだ計算量の改善が必要です。

第二ステップ：軸で分ける

計算式 $|x_{i} - x_{j}| + |y_{i} - y_{j}|$ を、それぞれの軸だけで計算できないか考えます。

式から、 $x$ と $y$ は独立しています（互いに影響を及ぼさない）。全ての配置において $x$ について調べて、その後全ての配置においても $y$ について調べる、ということができます。

f:id:Xenous:20210904120459p:plain — $x$ 軸に注目した場合のイメージ

$x$ 軸に注目して、二つのコマを適当に配置したとき、実際は $y$ 軸方向にも空間があるので、実質 $N^{2}$ 通りを見ていることと同じになります。

二つのコマを配置する場合の数は $_MC_2$ で計算できますが、 $O(M^{2})$ なので場合によっては TLE します。単純に並べるのではなく、 $|x_{i} - x_{j}|$ ごとにグループ化すると良いです。これを $d = |x_{i} - x_{j}|$ とすると、

距離 $d$ で二つのコマを配置する場合の数は $M-d$ 通り

であることがわかります。これは $O(M)$ で計算できます。ゆえに、このときの計算の式は

$(M-d) \times d \times N^{2} \times _{N\times M-2}C_{K-2}$

となります。

$y$ 軸についても同様に計算することができます。以上より、これらを足し合わせたものを $10^{9}+7$ で割ったあまりが答えになります。

提出コード

MOD = pow(10,9)+7
def MODINV(n:int, MOD=MOD):
    return pow(n, MOD-2, MOD)


class common_combinations():
    """
    mod を含む combination を高速に求めるためのクラス

        parameters:
        -----------
        N : int
            nCk を求める n の範囲(mod 未満)の最大値を N に設定する
            デフォルトは 510,000
        MOD : int
            設定したい mod の値
            デフォルトは 1,000,000,007
    """
    def __init__(self, N=510000, MOD=10**9+7):
        """
        combination を O(1) で計算するための前処理
        """
        self.N = N
        self.MAX_NUM = self.N + 1
        self.MOD = MOD

        self.fac  = [0 for _ in range(self.MAX_NUM)]
        self.finv = [0 for _ in range(self.MAX_NUM)]
        self.inv  = [0 for _ in range(self.MAX_NUM)]

        self.fac[0]  = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1

        for i in range(2, self.MAX_NUM):
            self.fac[i] = self.fac[i-1] * i % self.MOD
            self.inv[i] = self.MOD - self.inv[self.MOD%i] * (self.MOD // i) % self.MOD
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.MOD


    def combinations(self, n:int, k:int) -> int:
        """
        combination を計算して返すメソッド

            Parameters:
            -----------
            n, k : int
                nCk に対応する整数 n, k.
            
            Returns:
            --------
            int
                nCk (mod) の計算結果.
                n または k が 0 より小さい場合は 0 を返す.
                n が k より小さい場合も 0 を返す.
        """
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return self.fac[n] * (self.finv[k] * self.finv[n-k] % self.MOD) % self.MOD


def main():
    N, M, K = map(int, input().split())
    cc = common_combinations(N*M+10)

    # x の計算
    ans = 0
    for d in range(M):
        ans += (((M-d)*d)%MOD) * (N**2%MOD) * cc.combinations(N*M-2, K-2)
        ans %= MOD
    
    # y の計算
    for d in range(N):
        ans += (((N-d)*d)%MOD) * (M**2%MOD) * cc.combinations(N*M-2, K-2)
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

F - Absolute Minima

三分探索での解法を思いつきましたが、関数の更新がうまく実装できず（というより再帰で組んで間に合う気がせず）結局何もできませんでした。これも後日ときます。

2021-07-25

ABC211 参加記録

4完0ペナ 33分でした

A - Blood Pressure

式が与えられているのでその通りに実装しました。誤差は生じても小さいので気にしなくて良いです。

A, B = map(int, input().split())
print((A-B)/3+B)

B - Cycle Hit

やり方はいくつかあると思いますが、問題文中の「ただし、全ての $S_i$ は H , 2B , 3B , HR のいずれかと一致します。」というところから、種類数を見れば確定できることがわかったので、そちらで実装しました。

l = set([])
for _ in range(4):
    s = input()
    l.add(s)
if len(l) == 4: print('Yes')
else: print('No')

C - chokudai

なんか似たような問題を直近やったような。ちゃんと復習してますか？と問われたような気持ちになりました。 DP が苦手でバグらせつつ、14分くらいでAC。ここ早解きできる人はアドバンテージだと思います。

DP 配列 1行目を初期化しているなら 0 行目いらなくない...？とか色々ありますがこれで出しました。。計算量は $O(|S|)$ です。

MOD = pow(10,9)+7
def MODINV(n:int, MOD=MOD):
    return pow(n, MOD-2, MOD)


def main():
    S = '*' + input()
    T = '#chokudai'
    DP = [[0] * len(S) for _ in range(len(T))]

    for j in range(1, len(S)):
        DP[1][j] = DP[1][j-1] + (S[j] == T[1])
        DP[1][j] %= MOD

    for i in range(2, len(T)):
        for j in range(1, len(S)):
            DP[i][j] = DP[i-1][j-1]*(S[j] == T[i]) + DP[i][j-1]
            DP[i][j] %= MOD
    print(DP[len(T)-1][len(S)-1])


if __name__ == "__main__":
    main()

D - Number of Shortest paths

最短経路かと思いきや、場合の数を求める問題でした。どの道路も同じ長さなので、幅優先探索でできそうです。最短で探索しつつ、その頂点に入ってくる最短経路の場合の数を足し合わせて管理していきます。

例えば下の図では、各都市で、都市1 からの最短距離を青字の数字、その都市に最短で到達するまでの場合の数をそれぞれ記載しています。最短距離は幅優先探索の容量で良いです。場合の数の方は、今見ている都市を fr、隣接している都市を v とおくと、都市1からの最短距離 d について d[v]-1 == d[fr] が成り立つときに、v で記録している場合の数を fr に加算していきます。

f:id:Xenous:20210724230128p:plain — 距離と場合の数の管理の例

計算量は $O(N+M)$ くらいだと思います。

提出コード

from collections import deque
import sys

MOD = pow(10,9)+7
def MODINV(n:int, MOD=MOD):
    return pow(n, MOD-2, MOD)

input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        A, B = map(int, input().split())
        graph[A-1].append(B-1)
        graph[B-1].append(A-1)
    
    fr = 0
    que = deque([fr])
    goneset = set([fr])
    pattern = [0] * N; pattern[0] = 1
    count = [0] * N
    while que:
        fr = que.popleft()
        for v in graph[fr]:
            pattern[fr] += pattern[v] * (count[fr]-1 == count[v])
            pattern[fr] %= MOD
        for to in graph[fr]:
            if to in goneset:
                continue
            count[to] = count[fr] + 1
            que.append(to)
            goneset.add(to)
    print(pattern[N-1])


if __name__ == "__main__":
    main()

E - Red Polyomino

何も思い浮かびませんでした。 $N \leq 8$ と小さいのですが、数え上げる方法が全くわかりませんでした。

F - Rectilinear Polygons

E問題よりもこちらの方が解きやすそうでした。コンテスト中に考えた内容を記載しておきます。

多角形というワードから少し敬遠していましたが、サンプルであったように角張った領域でどのくらい重なっているかをクエリの数答える問題です。

パッと思い浮かぶのがいもす法です。領域が小さければ可能ですが、x軸、y軸それぞれが $10^{5}$ の大きさなので無理です。そこで、片方の軸だけで管理できないか考えます。

f:id:Xenous:20210724234346p:plain — 加算のイメージ

x 軸の小さい方から順に、区間加算 +1 と -1 ができて、あるタイミングのクエリに答えるために、一点取得ができれば良さそうです。よって LazySegmentTree や BIT を使えばできそうです。

実装の時間がなかったのが惜しいですが、これで間に合うかと思います。実装は後日やってみます。

2021-07-18

ABC210 参加記録

ABC AtCoder コンテスト参加記録

3完0ペナ 10分でした

A - Cabbages

$A$ 個までは $X$ 円、それ以降は $Y$ 円です。 $N > A$ のときは $AX + (N-A)Y$ 円とかけます。そうでない時は単純に $AX$ 円です。

N, A, X, Y = map(int, input().split())
if N <= A:
    print(X*N)
else:
    print(X*A + Y*(N-A))

B - Bouzu Mekuri

実際に順に手札を取っていくシミュレーションをして確かめます。後で考えてみると、初めて 1 が出てくる場所がわかればいいので、入力をリストで受け取って S.index('1') でも求められそうです。

N = int(input())
S = input()
k = 0
for s in S:
    if s == '0':
        k += 1
    else:
        break
if k%2 == 0: print('Takahashi')
else: print('Aoki')

C - Colorful Candies

先にベースとなる $K$ 個のカウンターを持っておき、そこからウィンドウを動かすように、先頭を追加、末尾を削除、を繰り返してその都度種類数を確認します。

from collections import Counter

N, K = map(int, input().split())
C = list(map(int, input().split()))
CounterC = Counter(C[:K])
ans = len(CounterC.keys()); tmp = ans
for i in range(N-K):
    if CounterC[C[K+i]] == 0: tmp += 1
    CounterC[C[K+i]] += 1
    CounterC[C[i]] -= 1
    if CounterC[C[i]] == 0: tmp -= 1
    ans = max(ans, tmp)
print(ans)

D - National Railway

探索の仕方が難しいです。後日解きます。

E - Ring MST

こちらはある程度考察しましたが、WA が取れず。後日解きます。