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()