A - N-choice question
問題ページ : A - N-choice question
考察
$A+B=C_i$なる$i$が丁度1つ存在する、とのことなので$C_i$をリストで受け、頭から$A+B=C_i$となるiを探索すればOK.
コード
N, A, B = map(int, input().split())
C = list(map(int, input().split()))
for i in range(N):
if A + B == C[i]:
print(i+1)
B - Same Map in the RPG World
問題ページ : B - Same Map in the RPG World
考察
基本的な考察として、
・縦のシフトと横のシフトはどのような順番でも各回数が同じであれば結果も同じ
・縦のシフトと横のシフトはそれぞれH回、W回で元に戻るので0~H-1回、0~W-1回、試行すれば良い
後は愚直実装。
多次元リストのコピーにはcopy.deepcopyの使用が無難。
コード
from copy import deepcopy
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
B = [list(input()) for _ in range(H)]
for s in range(H):
AA = deepcopy(A)
for i in range(H):
for j in range(W):
A[i][j] = AA[(i + 1) % H][j]
for t in range(W):
AA = deepcopy(A)
for j in range(W):
for i in range(H):
A[i][j] = AA[i][(j+1) % W]
if A == B:
print("Yes")
exit()
print("No")
このコードは縦のシフトを１回づつ、横のシフトを１回づつとループを回していますが、縦のシフト$s$回、横のシフト$t$回をまとめて表現した方が簡潔になります。
from copy import deepcopy
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
B = [list(input()) for _ in range(H)]
for s in range(H):
for t in range(W):
AA = deepcopy(A)
for i in range(H):
for j in range(W):
AA[i][j] = A[(i + s) % H][(j + t) % W]
if AA == B:
print("Yes")
exit()
print("No")
C - Cross
問題ページ : C - Cross
考察
全マスマス(i,j)に対してこれを左上とするサイズ$0 ～ \frac{min(H,W)}{2}$のバツ印があるかを全判定しても計算量的には間に合います。
コード
H, W = map(int, input().split())
C = [list(input()) for _ in range(H)]
N = min(H,W)
ans = [0] * (N+1)
for i in range(H):
for j in range(W):
for kk in range(1,N // 2 + 1):
k = kk * 2
if i + k >= H or j + k >= W:
break
flag = True
for s in range(k+1):
if C[i+s][j+s] != "#" or C[i+ k- s][j+s] != "#":
flag = False
if i-1 >= 0 and j - 1 >= 0 and C[i-1][j-1] == "#":flag = False
if i-1 >= 0 and j + k < W and C[i-1][j+k] == "#":flag = False
if i+k < H and j-1 >= 0 and C[i+k][j-1] == "#":falge = False
if i+k < H and j+k < W and C[i+k][j+k] == "#":flage = False
if flag:
ans[kk] += 1
print(*ans[1:])
問題文にある
・バツ印を構成するマス以外に # は書かれていません。
・異なるバツ印を構成するマス同士は頂点を共有しません
を正しく理解するとここまでしなくてもよく、もう少し簡潔になります。
H, W = map(int, input().split())
C = [list(input()) for _ in range(H)]
N = min(H,W)
ans = [0] * (N+1)
for i in range(H):
for j in range(W):
if C[i][j] != "#":continue
if i > 0 and j > 0 and C[i-1][j-1] == "#":continue
k = 0
while k + i < H and k + j < W and C[i+k][j+k] == "#":
k += 1
ans[k//2] += 1
print(*ans[1:])
D - AABCC
問題ページ : D - AABCC
考察
結論からいうとあらかじめエラトステネスの篩で素数を列挙し、a,b,cの3重ループ全探索で解を求めることができます。
エラトステネスの篩で求める素数の上限ですが、$a^2bc^2 \leq\ N \leq10^{12}$なので高々$10^6$までの素数を列強すればOKです。
またループを回す際には
\begin{align}
a^5\ >\ N \\
a^2b^3\ >\ N \\
a^2bc^2\ >\ N \\
\end{align}
でbreakをかけ不要な計算を省きます。
コード
# エラトステネスの篩
def eratos(n):
primes = [True] * (n+1)
primes[0], primes[1] = False, False
for i in range(2, int(n**0.5)+1):
if primes[i]:
for j in range(i**2, n+1, i):
primes[j] = False
ret = [num for num, is_prime in enumerate(primes) if is_prime]
return ret
N = int(input())
P = eratos(10**6)
num = len(P)
ans = 0
for i in range(num):
a = P[i]
if a ** 5 > N:break
for j in range(i+1,N):
b = P[j]
if (a ** 2) * (b ** 3) > N:break
for k in range(j+1,N):
c = P[k]
if a * a * b * c * c <= N:
ans += 1
else:
break
print(ans)
E - Dice Product 3
問題ページ : E - Dice Product 3
考察
求める確率を$f(N)$と表すこととします。$N=15$の例を考えてみますと次の式が成り立ちます。
$$f(15)\ =\ f(3)\ \times\ (5を引く確率)\ +\ f(5)\ \times\ (3を引く確率) $$
ここで$2,4,6$を引いて15となることは無いことに注意してください。
また$(5を引く確率)$や$(3を引く確率)$は単純には$\frac{1}{6}$なのですが、その前に$1$を$０～ \infty$回だしても良いことを考慮すると初項$\frac{1}{6}$、項比$\frac{1}{6}$の無限級数の和で$\frac{1}{5}$となります（解説放送によると$1$がでたら振り直しと考え$2$~$5$のでる確率が等確率で$\frac{1}{5}$と考えて良いそうです）。
ここまでの考え方を元にメモ化つき再帰で実装します。
なお$mod\ 998244353$における$\frac{1}{5}$は$pow(5,\ -1,\ 998244353)$で処理します。
コード
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)
md = 998244353
N = int(input())
d = defaultdict(int)
def dfs(n):
if n in d:return d[n]
if n == 1:
d[n] = 1
return d[n]
ret = 0
for i in range(2,7):
if n % i == 0:
ret += pow(5, -1, md) * dfs(n // i)
ret %= md
d[n] = ret
return d[n]
print(dfs(N))
F - More Holidays
問題ページ : F - More Holidays
考察
コード
G - P-smooth number
問題ページ : G - P-smooth number
考察
コード
Ex - Fibonacci: Revisited
問題ページ : Ex - Fibonacci: Revisited
考察
コード
青色diff以上は後日挑戦