今日はABC開催日だったので参加結果を振り返る
結果はまたまたA,B,Dの3完、2連続でDが解けてCが解けない事態に😅
今回は363が回文数だからかしらんけど回文の問題が複数あった(C,D,F)
A
100からNを100割ったあまりを引くだけ。
ソースコード
main.py
import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)
def main():
N = rI()
ans = 100-N%100
print(ans)
if __name__ == '__main__':
main()
B
配列の要素を1ずつ増やしながらT以上になったかを数え、
その数がP以上になったらループの回数を表示して終了。
ソースコード
main.py
import sys
from itertools import count
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)
def main():
N, T, P = rLI()
L = rLI()
if sum(l >= T for l in L) >= P:
print(0)
return
for d in count(start=1):
c = 0
for i in range(N):
L[i] += 1
if L[i] >= T:
c += 1
if c >= P:
print(d)
break
if __name__ == '__main__':
main()
C
permutaionsを使って探索するまでは検討が着いたが
重複する要素を削除するのが分からなくてブッチ
D
参考サイト
回文数で検索していたら桁数ごとの回文数の個数を出す計算式を発見
$$a_n=9\cdot10^{\lfloor (n-1)/2 \rfloor}$$
この式は0を含んでいないので+1するとして以下のような式を考える
$$S=\sum_{n=0}^{d+1}a_n + 1\gt N$$
この式が成り立つ最小の$d$が求める回文数の桁数
そこから$d$桁の中で$N-S-1=j$番目の回文数を出す
その$d$桁の回文数でj番目の数を計算する方法は数列表みながら浮かんできたが言語化しづらい…
- $d$桁($d\ge3$)の最小の回文数は$10\ldots01$(0の個数は$d-2$個)
- この数を半分に区切り上位半分はjを足して下位半分はそれの反転
- ただし、$d$が奇数なら反転した数の最上位桁は使わない
ソースコード
main.py
from itertools import count
import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)
def main():
N = rI()
if N<=10:
print(N-1)
return
if N<=20:
print(11*(N-10))
an = 1
k = 0
for i in count(start=1):
t = 9* 10**((i-1)//2)
if an + t > N:
d = i
break
else:
an += t
j = N-an-1
k = j+10**((d-1)//2)
s1 = str(k)
s2 = s1[::-1]
if d%2 == 1:
s2 = s2[1:]
err(d,j,k)
print(s1+s2)
if __name__ == '__main__':
main()
E
幅優先探索で頑張って実装しようとしたがTLE、
その後時間なかったのでワンチャンを狙って生成AIに適当に改良してもらったがWA
後日解き直します。
TLEソースコード
main.py
import sys
from collections import deque
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)
d = ((0,1),(0,-1),(1,0),(-1,0))
def main():
H, W, Y = rLI()
A = [rLI() for _ in range(H)]
area = H*W
search = set(( 0, i) for i in range(W))
search |= set(( i, 0) for i in range(1,H-1))
search |= set(( i,W-1) for i in range(1,H-1))
search |= set((H-1, i) for i in range(W))
min_h = min(A[i][j] for i,j in search)
for y in range(1,Y+1):
if y >= min_h:
q = deque()
rm = set()
for i,j in search:
if A[i][j] > y:
min_h = min(min_h,A[i][j])
continue
else:
rm.add((i,j))
area-=1
A[i][j] = -1
for di,dj in d:
ni = i+di
nj = j+dj
if ni < 0 or nj < 0 or ni == H or nj == W:
continue
if A[ni][nj] == -1:
continue
if (ni,nj) in search:
continue
q.append((ni,nj))
for p in rm:
search.remove(p)
while q:
cur = q.popleft()
ci, cj = cur
min_h = min(min_h,A[ci][cj])
if 1 <= A[ci][cj] <= y:
A[ci][cj] = -1
err(cur)
area -= 1
for di,dj in d:
ni = ci+di
nj = cj+dj
if ni < 0 or nj < 0 or ni == H or nj == W: continue
if A[ni][nj] == -1: continue
if (ni,nj) in search: continue
q.append((ni,nj))
else:
search.add(cur)
print(max(0,area))
if __name__ == '__main__':
main()
F
素因数分解した後どうすんのって感じ
G
クエリ的に考えてセグメント木使う必要がありそうって思ったくらい
まとめ
前回の反省を活かして、わからなくて、次の問題に向かうタイミングを早めた。
結果としてなんとか解けたので良かったが、安定してCまでは解けるようにしたい。