AtCoder Problems Hard No.11~20解説

#Hard No.11 : D - Disjoint Set of Common Divisors
D - Disjoint Set of Common Divisors
##発想
AとBの正の公約数なので、それぞれの約数のうち両方に共通するものを列挙しようと考えます。ただしこの中には互いに素でない約数たちが現れます。互いに素であるような約数のみを取り出すためには、公約数かつ素数であるもののみを取り出せばよいです。

##実装
まずはA, Bそれぞれの約数かつ素数を列挙します。

A, B = map(int, input().split())
a = []
b = []

def prime_factorize(n, x):
    
    while n % 2 == 0:
        x.append(2)
        n //= 2
    
    f = 3
    while f*f <= n:
        if n % f == 0:
            x.append(f)
            n //= f
        else:
            f += 2
    
    if n != 1:
        x.append(n)

prime_factorize(A, a)
prime_factorize(B, b)
a = list(set(a))
b = list(set(b))
ab = a + b

関数に切り出したところが約数かつ素数を列挙する部分です。最初に2で割れるだけ割って、あとは3から順番に割り切れる数字を探していきます。ある数$N$までの素数を列挙するときは$\sqrt{N}$まで調べればよいです（エラトステネスの篩）。

次に共通する約数を取り出します。collections.Counter()で出現回数が2回のものを取り出します。必ず1が正の公約数になるので、Counterで取り出した要素数に1を加えたものが答えになります。

C = collections.Counter(ab)
div = [c[0] for c in C.items() if c[1] == 2]
ans = len(div) + 1
print(ans)

#Hard No.12 : B - Counting of Trees
B - Counting of Trees
##発想
全て頂点１からの距離を考えます。つまり距離０の頂点がただ一つあるので、そのようになっていない状況は例外処理をします。また、頂点１から移動するにつれて距離は１づつ増えていくので、Dをソートした時に隣と値が２以上離れている場合も例外処理します。

実際の数え上げをどうしようかなと思った時は実験してみます。
例えば距離１の頂点が３つ、距離２の頂点が２つあるとすると、頂点１には生えた３つの頂点それぞれに対して、距離２の頂点を生やすことができます。つまり$3^2$通りあることがわかります。このような計算を続ければ良さそうだと考えます。

##実装

import collections

N = int(input())
D = list(map(int, input().split()))
#頂点１の距離は０
if D[0] != 0:
    print(0)
    exit()

D = sorted(D)
#離れて良い距離はたかだか１
for i in range(N-1):
    if D[i+1] - D[i] > 1:
        print(0)
        exit()
        
C = collections.Counter(D)
#距離０の頂点は２つ以上あってはいけない
if C[0] >= 2:
    print(0)
    exit()

ls = list(C.values())
ans = 1
for i in range(1, len(ls)-1):
    ans *= ls[i] ** ls[i+1]
    ans %= 998244353

print(ans)

$O(N)$で計算できます。

#Hard No.13 : D - Lucky PIN
D - Lucky PIN
##発想
ラッキーナンバーSは最大で30000桁の非常に大きな値となり、Sから暗証番号を探すのは大変そうです。暗証番号は3桁ですので、答えの候補は000~999までの1000通りしかありません。答えを決め打って、Sから作れるかどうか判定すると楽そうです。
##実装
答えの候補を作成するときに、答えが1桁または2桁の場合は先頭に0をつけます。
あとはSから作成できるか判定します。

import collections

N = int(input())
S = list(input())

ans = 0
for i in range(1000):
    #答えの候補を先に決め打つ
    s = str(i)
    if len(s) == 1:
        s = '00' + s
    elif len(s) == 2:
        s = '0' + s
    #ラッキーナンバーから作れるか判定
    cur = 0
    for j in range(N):       
        if S[j] == s[cur]:
            cur += 1
        if cur == 3:
            ans += 1
            break

print(ans)

計算量は$O(1000N)$です。

#Hard No.14 : C - Digits in Multiplication
C - Digits in Multiplication
##発想
$N=A×B$を満たす整数の組$(A, B)$と言っているので、$N$の約数を求めようかなと思います。単に約数を列挙するのでなく、約数$i$と$N/i$をセットにするのが良いと思います。例えば12の約数として$(1, 12)$、$(2, 6)$、$(3, 4)$のように。

##実装
関数部分が約数を列挙します。$\sqrt{N}$まで調べれば良いです。あとはそれぞれのセットの大きい方の値に対して文字列として最小の長さを求めれば良いです。

N = int(input())

#nの約数を全て求める
def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append([i, n//i])
        i += 1
    return table

AB = divisor(N)

ans = 10**10
for a, b in AB:
    ans = min(ans, len(str(max(a, b))))

print(ans)

#Hard No.15 : D - Flipping Signs
D - Flipping Signs
##発想
隣あう2つの要素の符号を好きな回数だけ変えられます。この数列を最大化したいので、できるだけ正の値にしたいです。

（１）負の要素数が偶数の時
全て正の値にすれば良いです。
（２）負の要素数が奇数の時
どれか1つだけを負の値にして、他は正の値にします。この1つは好きな要素を選べます（好きな回数だけ操作できるので）。よって絶対値の小さな要素を負の値にします。

##実装

N = int(input())
A = list(map(int, input().split()))
#負の要素数numと絶対値の最小値mini
mini = 10**9+1
num = 0
for i in range(N):
    if A[i] < 0:
        num += 1
    mini = min(mini, abs(A[i]))
#とりあえず全ての絶対値を足す
ans = 0
for i in range(N):
    ans += abs(A[i])
#負の要素数が奇数の時
if num % 2 == 1:
    ans -= 2*mini

print(ans)

計算量は$O(N)$です。

#Hard No.16 : D - Line++
D - Line++
##発想
最短経路問題ですが、辺に重みはついていません。全ての頂点を始点として幅優先探索をしても計算量は$O(N^2)$程度なので十分間に合います。

##実装
頂点$i$から頂点$j$までの距離と頂点$j$から頂点$i$までの距離は同じなので、最後に答えを半分にします。

from collections import deque

N, X, Y = map(int, input().split())
G = []
for i in range(N):
    G.append([])
for i in range(N-1):
    G[i].append(i+1)
    G[i+1].append(i)
G[X-1].append(Y-1)
G[Y-1].append(X-1)

Ans = [0]*(N-1)
#全ての頂点を始点とした幅優先探索をする
for i in range(N):
    dist = [-1]*N
    Q = deque()
    Q.append(i)
    dist[i] = 0
    #キューから取り出しながら探索する
    while len(Q) > 0:
        j = Q.popleft()
        for k in G[j]:
            if dist[k] == -1:
                dist[k] = dist[j] + 1
                Q.append(k)
    #距離をAnsに入れていく
    for j in range(N):
        k = dist[j]
        if k == 0:
            continue
        Ans[k-1] += 1

#ダブルカウントしているので答えは半分
for i in range(N-1):
    Ans[i] //= 2
    print(Ans[i])

#Hard No.17 : C - AB Substrings
C - AB Substrings
##発想
文字列$s_i$の考えられる場合は
（１）'AB'を含む
（２）先頭が'B'
（３）末尾が'A'
（４）先頭が'B'かつ末尾が'A'
です。
（２）、（３）、（４）の個数によって場合分けが発生します。
##実装
もし（２）、（３）が両方とも0個で（４）が1個以上あると（４）の個数-1を答えに足します。そうでない場合は（２）,（３）のうち少ない方の個数と（４）の個数を足せば良いです。場合分けを間違えそうな問題です。

N = int(input())
#'AB'を含む
numAB = 0
#末尾が'A'
numA = 0
#先頭が'B'
numB = 0
#先頭が'B'かつ末尾が'A'
numBA = 0

for i in range(N):
    S = input()
    
    if S[0] == 'B' and S[-1] == 'A':
        numBA += 1
    elif S[0] == 'B':
        numB += 1
    elif S[-1] == 'A':
        numA += 1

    for j in range(len(S)-1):
        if S[j] == 'A' and S[j+1] == 'B':
            numAB += 1

ans = numAB
if numA + numB == 0 and numBA >= 1:
    ans += numBA - 1
else:
    ans += min(numA, numB) + numBA
 
print(ans)

#Hard No.18 : C - Back and Forth
C - Back and Forth
##発想
最短経路問題かと思いますが、特に壁などは無いですし、経路はシンプルなものになります。始点と終点を長方形の対角線上の頂点とした長方形の辺が1周目の経路になります。2周目の経路はその1つ外側の辺にすれば良いです。
##実装

sx, sy, tx, ty = map(int, input().split())
ans = ''
#内側の経路
ans += 'U'*(ty-sy)
ans += 'R'*(tx-sx)
ans += 'D'*(ty-sy)
ans += 'L'*(tx-sx)
#外側の経路
ans += 'L'
ans += 'U'*(ty-sy+1)
ans += 'R'*(tx-sx+1)
ans += 'D'
ans += 'R'
ans += 'D'*(ty-sy+1)
ans += 'L'*(tx-sx+1)
ans += 'U'

print(ans)

#Hard No.19 : D - Grid Coloring
D - Grid Coloring
##発想
同じ色は全て連結なので、色1から色Nまでを順番に上から並べていきます。高さが偶数番目の行はreverseをすれば全て連結して並べることができます。
##実装

H, W = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))

B = []
#色iをA[i]個だけ連続で並べる
for i in range(N):
    for _ in range(A[i]):
        B.append(i+1)

Ans = []
#Bから1行分を繰り返し取り出す
for i in range(H):
    X = B[i*W:i*W+W]
    #偶数番目の行はreverse
    if i % 2 == 1:
        X = list(reversed(X))
    Ans.append(X)

for i in range(H):
    for j in range(W):
        print(Ans[i][j], end=' ')
    print()

#Hard No.20 : C – ID
C – ID
##発想
いきなり答えを出そうとするのは難しいなという印象があります。どの市もどこかの県には所属し、その中で何番目に誕生したかという情報が必要なので、とりあえず全ての市を県に所属させます。各県から誕生年の小さい順に取り出す必要があるのでheapを使い、市番号と認識番号をセットで新しいリストに入れれば良さそうです。
##実装
認識番号を作成するときにpやxが6桁に満たない場合に先頭に’0’を追加すれば良いです。

import heapq

N, M = map(int, input().split())
#県pre
pre = []
for i in range(N):
    pre.append([])
#市iとその誕生年yを県pre[p]に所属させる
for i in range(M):
    p, y = map(int, input().split())
    pre[p-1].append([y, i])

for i in range(N):
    heapq.heapify(pre[i])

Ans = []
#認識番号の作成
for p in range(N):
    for x in range(len(pre[p])):
        y, i = heapq.heappop(pre[p])

        pp = str(p+1)
        xx = str(x+1)
        #pやxが6桁に満たない場合は先頭に'0'追加
        if len(pp) < 6:
            pp = '0'*(6-len(pp)) + pp
        if len(xx) < 6:
            xx = '0'*(6-len(xx)) + xx
        #答えのリストには市番号iと認識番号を入れる
        Ans.append([i, pp+xx])
#市番号の若い順にソート
Ans = sorted(Ans)
for i in Ans:
    print(i[1])