初めに
ねえいいねください 色変記事なのに全然伸びない(自分の責任だろ)
取り乱してすいません
あと少し投稿が遅れてしまってすいません
スノーボード行って、記事を書く気力がなく、このような結果になりました
そして虚無埋めをする気力もなくstreakを切らしました
初スノボの記録
母と二人で行きました。 母はスキーをやってます。 鹿島槍が一番レッスン代が安いのでそちらに行った記録です。 鹿島槍ガーデン(釣り堀です -6度近くあるのにおっさんがたくさんいた)の天気予報だと、雪はふらない予報だったのですが早速オリンピック道路で、雪が降ってきて、それも道路ガッチガチに凍っていました。 波乱の予感がしますスキー場に行く山道は結構雪が降っていて、こりゃコンディション悪いと確信しました
スキー場に到着し、スリップした2躯の軽が帰るのを見届けると、シーズン券(15000円の共通券)を受け取り、スキー学校の受付を済ませてレッスンが始まりました。
プライベートレッスンの四時間コースで、新雪がすごかったけど、ある程度滑れるようになりました。
駐車場へ言ったら、雪が20センチぐらい積もっていて、かき出すのが大変でした
駐車場は-7度ぐらいで寒かったです。
意外と順調に駐車場からは帰れて無事帰宅しました。(車は4~5回ぐらいエンストしてました マニュアル車なので)
すみませんスノボ全然関係ありませんでしたね、ごめんなさい
コンテスト結果は、4完 水perf 落茶回避でした
AJLのランキング上昇が楽しみです。
コンテスト前 手がかじかんで動かなかったので、寿司打やりました
コンテスト中の流れとしては
ABは瞬殺、Cは一見$O(N^3)$に見えましたが、実装してみたら計算量が$O(N^2)$っぽく簡単にACできました。
ここまで1ペナ 10分 たしかこれだけでperf 1000は出るみたいです
Dは二分探索+imos法でACしました。
そんじゃ、1問ずつ感想書きますか
使っているライブラリ
レポジトリを変えました
unittestとか実装しようと思ったけど、とりあえず今度やります。
A問題
普通に、条件分岐して、解きました
やっぱりYesNo関数必要かな
ACコード(ライブラリ抜粋)
A, B, C = il()
if A + B == C or B + C == A or A + C == B or (A == B and B == C):
print("Yes")
else:
print("No")
B問題
動けるのであれば、フラグを立てて、動く
動けなかったら、そのまま
その後、フラグが立っている、かつ、家がある場合の数の、総和を出力すればいい
でxとyも変数に取っておけばいいから、簡単
ACコード(ライブラリ抜粋)
H, W, X, Y = il()
X -= 1
Y -= 1
S = li(H, s)
T = s()
used = create_array2(H, W)
for t in T:
nx, ny = X, Y
match t:
case "U":
nx -= 1
case "D":
nx += 1
case "L":
ny -= 1
case "R":
ny += 1
if S[nx][ny] != "#":
X, Y = nx, ny
used[X][Y] = True
ans = 0
for i in range(H):
for k in range(W):
if S[i][k] == "@" and used[i][k]:
ans += 1
print(X + 1, Y + 1, ans)
C問題
間隔と始点を全探索して、始点からループを回して、ループを回した回数の最大値を求めればいいです
計算量が$O(N^2)$になる理由の考察は、大体ループが回っている量が$O(N^2)$ぐらいだからだと思います
一度競技プログラミング最高の瞬間を、出してしまったものの、すぐバグに気づいてACしました
N = ii()
H = il()
ans = 1
for i in range(1, N):
for start in range(N - i):
count = 0
t = H[start]
for k in range(start, N, i):
if t == H[k]:
count += 1
else:
break
ans = max(count, ans)
print(ans)
D問題
そのx座標とy座標それぞれにdefaltdictを作って、それをソートの中身をすべてソートします。
そしてimos法用の配列を、x座標とy座標それぞれに作成します。
そして各クエリごとに、二分探索すればOK
最後にimos法のために用意しておいた配列に累積和を取って、それが1以上だったら、setに入れます。
あとは、現在地とsetの長さを入れればOKでした。
公式解説は僕のコードより全然エレガントでした(そりゃそーだ)
まあいつものクソコードよりは綺麗にできた気がします
ACコード(ライブラリ抜粋)
N, M, x, y = il()
H = defaultdict(list)
W = defaultdict(list)
l = set()
ts = set()
for _ in [0] * N:
X, Y = il()
ts.add((X, Y))
H[X].append(Y)
W[Y].append(X)
UH = defaultdict(list)
UW = defaultdict(list)
for tx in H.keys():
H[tx].sort()
UH[tx] = [0] * (len(H[tx]) + 1)
for ty in W.keys():
W[ty].sort()
UW[ty] = [0] * (len(W[ty]) + 1)
def bis_y(a, b, tx):
a, b = min(a, b), max(a, b)
if len(H[tx]) == 0:
return
if H[tx][0] > b or H[tx][-1] < a:
return
l = bisect.bisect_left(H[tx], a)
r = bisect.bisect_left(H[tx], b)
UH[tx][l] += 1
UH[tx][r] -= 1
def bis_x(a, b, ty):
a, b = min(a, b), max(a, b)
if len(W[ty]) == 0:
return
if W[ty][0] > b or W[ty][-1] < a:
return
l = bisect.bisect_left(W[ty], a)
r = bisect.bisect_left(W[ty], b)
UW[ty][l] += 1
UW[ty][r] -= 1
for _ in [0] * M:
D, C = sl()
C = int(C)
match D:
case "U":
bis_y(y, y + C, x)
y += C
case "D":
bis_y(y, y - C, x)
y -= C
case "L":
bis_x(x, x - C, y)
x -= C
case "R":
bis_x(x, x + C, y)
x += C
if (x, y) in ts:
l.add((x, y))
for tx in H.keys():
t = list(accumulate(UH[tx]))
for i in range(len(H[tx])):
if t[i] >= 1:
l.add((tx, H[tx][i]))
for ty in W.keys():
t = list(accumulate(UW[ty]))
for i in range(len(W[ty])):
if t[i] >= 1:
l.add((W[ty][i], ty))
print(x, y, len(l))
最後に
やっぱりD問題の二分探索使う系の緑diffはめんどくさいですね
レートは50ぐらい上がりました
半年後ぐらいには入水したいです。
最後まで見ていただきありがとうございました。