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