LoginSignup
0

More than 1 year has passed since last update.

Atcoder参加記録 ABC254 PythonでA~E

Last updated at Posted at 2022-06-04

A - Last Two Digits

入力の最後2文字を出力。

def main():
    N = input()
    print(N[-2:])


if __name__ == "__main__":
    main()

B - Practical Computing

問題文の通りに実装。

def main():
    N = int(input())
    A = [[0] * i for i in range(1, N + 1)]
    for i in range(N):
        for j in range(i + 1):
            if j == 0 or j == i:
                A[i][j] = 1
                continue
            A[i][j] = A[i - 1][j - 1] + A[i - 1][j]
    for a in A:
        print(*a)


if __name__ == "__main__":
    main()

C - K Swap

解法

K=1の時は必ずソートできるのでYes
例えばK=3の時、
先頭から1, 4, 7,..., 3x-2の要素は好きなように並べ替えることができるが、これら以外の場所には移動できない。同様に2, 5, 8,..., 3x-1と3, 6, 9,...,3xの要素もそれぞれ独立している。
Aをそれぞれのグループに分け、降順にソートする。
例:

A[2,5,1,3,2,4,7,6]
#↓
grouped_A[
[2, 3, 7],
[2, 5, 6],
[1, 4]
]

あとは先頭からA[i][0]<=A[i][1]<=A[i][2]<=...<=A[i][K-1]となっているかを確認し、
なっていない場所があればNo、最後まで行けばYes
途中で長さが短くなっている場所(上の例で[1,4])があるのでそこまで来たら終了。

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    if K == 1:
        print("Yes")
        exit()
    grouped_A = [sorted(A[i::K]) for i in range(K)]
    for i in range(len(grouped_A[0]) - 1):
        for j in range(K - 1):
            if i == len(grouped_A[j + 1]):
                break
            if grouped_A[j][i] > grouped_A[j + 1][i]:
                print("No")
                exit()
    print("Yes")


if __name__ == "__main__":
    main()

D - Together Square

解法

数iの約数の中で最大の平方数f(i)を算出。
i*j=平方数の時、i/f(i) = j/f(j)となることを利用するとのことでしたが、解説を読んでもあまりピンと来ませんでした。
試しにi=1~10で検証。

# i:[iの約数], f(i)=iの約数で最大の平方数(1, 4, 9,...)
1:[1]            -> f(1)=1   -> 1/f(1)=1
2:[1, 2]         -> f(2)=1   -> 2/f(2)=2
3:[1, 3]         -> f(3)=1   -> 3/f(3)=3
4:[1, 2, 4]      -> f(4)=4   -> 4/f(4)=1
5:[1, 5]         -> f(4)=1   -> 5/f(5)=5
6:[1, 2, 3, 6]   -> f(6)=1   -> 6/f(6)=6
7:[1, 7]         -> f(7)=1   -> 7/f(7)=7
8:[1, 2, 4, 8]   -> f(8)=4   -> 8/f(8)=2
9:[1, 3, 9]      -> f(9)=9   -> 9/f(9)=1
10:[1, 2, 5, 10] -> f(10)=1  -> 10/f(10)=10

確かにi/f(i)=1(1,4,9)i/f(i)=2(2,8)の組合せで平方数となります。
実装としては、i/f(i)をキーにdefaultdictやCounterを用いて、そこに属する要素数を出し、
あとはi,jがそれぞれ要素数分あるので要素数の2乗を答えに加算していきます。

from collections import Counter
from math import sqrt


def main():
    N = int(input())
    # 平方数であるか否か
    is_sqrt = [False] * (N + 1)
    for i in range(1, int(sqrt(N)) + 1):
        is_sqrt[i * i] = True
    # i=1~Nの各数について約数を数えてリストに
    factor = [[] for _ in [0] * (N + 1)]
    for i in range(1, N + 1):
        for j in range(i, N + 1, i):
            factor[j].append(i)
    # i/f(i)となる組み合わせを数える
    cnt = Counter()
    for i in range(1, N + 1):
        # 各約数のうち最大の平方数fを求める
        f = 0
        for x in reversed(factor[i]):
            if is_sqrt[x]:
                f = x
                break
        # i/f(i)が同じ要素に加算
        cnt[i // f] += 1
    ans = 0
    # 組み合わせの数はi/f(i)につき、その個数の2乗
    for v in cnt.values():
        ans += v ** 2
    print(ans)


if __name__ == "__main__":
    main()

E - Small d and k

解法

制約として次数が3以下=ある頂点につながっている辺が3個以下、探索する深さKも3以下と小さいので、クエリごとに幅優先探索(BFS)や深さ優先探索(DFS)を行い、深さが3を超えたら打ち切るようにすれば間に合う、のですが、
当初、来訪済みを管理するためにbooleanのリストvisited = [False] * (N+1)を使っており、クエリのたびに配列を生成するため非常に時間がかかりTLEしました。
今回の場合、クエリごとの探索範囲は小さいので、来訪済みの判定はset()で管理するべきでした。

from collections import deque
import sys


input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    connect = [[] for _ in [0] * (N + 1)]
    for _ in [0] * M:
        u, v = map(int, input().split())
        connect[u].append(v)
        connect[v].append(u)

    def bfs(x, k):
        # 来訪済みをsetで管理
        visited = set()
        que = deque()
        # queに(現在の頂点, 現在の深さ)を入れる
        que.append((x, 0))
        visited.add(x)
        ans = 0
        while que:
            # queから現在地crrと探索の深さdist取り出す
            crr, dist = que.popleft()
            # 深さがkを超えていたら終了
            if dist > k:
                break
            # 答えに現在地を加算
            ans += crr
            # 現在地から隣接する頂点を探索
            for nxt in connect[crr]:
                # まだ探索していない頂点なら
                if nxt not in visited:
                    visited.add(nxt)
                    # queに(次の地点, 深さ+1)を入れる
                    que.append((nxt, dist + 1))
        # 答えを返す
        return ans

    # クエリを処理
    Q = int(input())
    result = []
    for _ in [0] * Q:
        x, k = map(int, input().split())
        result.append(bfs(x, k))
    print(*result, sep="\n")


if __name__ == "__main__":
    main()

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0