0. はじめに
就活が終わった24歳、学生です。
AtCoderのコンテストに参加してきました。:
結果としてはAを早々に解き、B以降は詰みました。
1. 問題
その1 : ABC 300 A - N-choice question (100 点)
【問題概要】
整数 $A$,$B$が与えられるので、$A+B$の値を答えてください。
但し、この問題は$N$択問題であり、i番の選択肢は $C_i$です。
正解となる選択肢の番号を出力してください。
【考えていたこと】
やることは以下の4つ。
- 標準入力から入力うけとり
- A+Bを求める
- 選択肢から一致するものを探す
- 一致選択肢のIndexを出力
【ポイント】
- 愚直に足し算をしてから、for文回して一致するかを判定。
その2 : ABC 300 B - Same Map in the RPG World (200 点)
【問題概要】
2枚のマップを片方を縦横に何回かシフトさせて一致させることができるかを判定する問題。
条件を満たす非負整数の組$(s,t)$が存在するかを判定する。
【考えていたこと】
+文字列からなる行列の処理をどうしたらよいか分からず行き詰まった。
【ポイント】
- 愚直に「左シフト」と「上シフト」を繰り返して毎回一致するか確認？
- 計算量的には問題ない？➡︎
一旦えびまラボさんの解説を参考にしながら解説ACしてみる
H,W = map(int,input().split())
A = [input() for _ in range(H)]
B = [input() for _ in range(H)]
def shift_left(C):
return [r[1:] + r[0] for r in C]
def shift_up(C):
return C[1:] + [C[0]]
ans = False
for i in range(H):
for j in range(W):
ans |= A == B
A = shift_left(A)
A = shift_up(A)
print("Yes", if ans else "No")
ans |= A == B はA==Bの部分が1個でもあったらansが1になるということ？
その3 : ABC 300 C - Cross (300 点)
【問題概要】
#から構成されるサイズnのバツ印の個数をそれぞれカウントする。
【考えていたこと】
- Bと同様に方針が立たず手詰まり。
【ポイント】
evimaさんの解説を参考にしながら解説ACしてみる
H,W = map(int,input().split())
C = [list(input()) for _ in range(H)]
def dfs(y, x):
cnt = 1
C[y][x] = '.'
for dy in range(-1, 2):
for dx in range(-1, 2):
y2, x2 = y + dy, x + dx
if 0 <= y2 < H and 0 <= x2 < W and C[y2][x2] == '#':
cnt += dfs(y2, x2)
return cnt
ans = [0 for _ in range(min(H, W))]
for y in range(H):
for x in range(W):
if C[y][x] == '#':
ans[dfs(y, x) // 4 - 1] += 1
print(' '.join(map(str, ans)))
その4 : ABC 300 D - AABCC (400 点)
【問題概要】
$N$以下の正整数のうち、$a<b<c$なる素数$a,b,c$を用いて$a^2×b×c^2$と表せるものはいくつありますか?
【考えていたこと】
- 愚直にやったら$N=10^12$でTLEになってしまった
- 計算量を減らす必要があるが、解法ストックが足りず実装ができなかった
【ポイント】
- エラトステネスの篩という考え方が重要らしい
- 整数の絞り込みの考え方も重要？
Nyaanさんの解説を参考にしながら解説ACしてみる
from math import isqrt
N = int(input())
# sqrt(N) 以下の素数の列挙
sieve = [1] * (isqrt(N) + 1)
primes = []
for p in range(2, len(sieve)):
if sieve[p] == 0:
continue
primes.append(p)
for j in range(p * p, len(sieve), p):
sieve[j] = 0
# prefix_sum[n] : (n 以下の素数の個数)
prefix_sum = sieve
for i in range(len(prefix_sum) - 1):
prefix_sum[i + 1] += prefix_sum[i]
ans = 0
# a, b を全探索する
for i in range(len(primes)):
a = primes[i]
if a * a * a * a * a >= N:
break
for j in range(i + 1, len(primes)):
b = primes[j]
if a * a * b * b * b >= N:
break
ans += prefix_sum[isqrt(N // (a * a * b))] - prefix_sum[b]
print(ans)
2. おわりに
久しぶりのABCでしたが、A問題しか解けなかった。解放パターンの引き出しの少なさを痛感。しばらくは
- 「バチャコン精進→コンテスト参加→解説見て復習」のサイクル
- C++での解法が豊富なのでC++も試してみる