コンテスト中に全部できたわけじゃないが復習して解いたのでせっかくなので
atcoder.jp
下から順番に見て条件満たしたらprintしてbreak
A,B = map(int,input().split())
c = A+B
for i in range(10):
if i != c:
print(i)
break
atcoder.jp
defaultdictって便利だなってだけの問題。空のリストの扱いが楽なのが特にえらし。
N = int(input())
A =[list(map(int,input().split())) for _ in range(N)]
from collections import defaultdict
d = defaultdict(list)
for i in range(N):
for j in range(N):
if A[i][j] == 1:
d[i].append(j+1)
d[j].append(i+1)
for i in range(N):
L = list(set(d[i]))
L.sort()
print(*L)
atcoder.jp
オーダーを見ると1/3乗して全探索で解けると分かるので、後は端点で変なミスをしないように念のためif文を入れる。回文かどうかは素直に文字列に直して判定。
N = int(input())
from math import pow
M = int(pow(N,1/3)+1)
for i in range(M,-1,-1):
L = i ** 3
if L <= N:
a = str(L)
b = str(L)[::-1]
if a == b:
print(L)
break
atcoder.jp
ここら辺からGPT4に投げ始める。愚直に数えるとTLEになるので、高速化するために道中の情報を辞書に保持する。辞書はメモリ食う代わりに早いという単純な暗記してるだけだけど、困ったことはなし。
N, T = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(T)]
# 各選手の得点を0で初期化
scores = [0] * N
# 得点の多様性を追跡するための辞書
score_counts = {0: N} # 初期状態では全選手の得点が0点
diversities = []
for i in range(T):
Ai, Bi = AB[i][0] - 1, AB[i][1] # 選手の番号は1から始まるため、インデックス用に1を引く
# 既存の得点を減らす
if scores[Ai] in score_counts:
score_counts[scores[Ai]] -= 1
if score_counts[scores[Ai]] == 0:
del score_counts[scores[Ai]]
# 得点を更新
scores[Ai] += Bi
# 新しい得点を追加
if scores[Ai] in score_counts:
score_counts[scores[Ai]] += 1
else:
score_counts[scores[Ai]] = 1
# 異なる得点の数を追加
diversities.append(len(score_counts))
# 各時刻における得点の多様性を出力
for diversity in diversities:
print(diversity)
atcoder.jp
まず、90度回転と平行移動を使って、1つの点は原点にしていいとわかる。そのあと回転をすることで、もう一点はx>=0 , y>=0 , z>=0 にあると仮定していいとわかる。
残りがどう仮定して一般性を失わないと考えて矛盾がないとしてよいのかが難しい。
今回は、原点を頂点にする立方体の周りを他の立方体がぐるぐる回転すると考えて、もう一個の立方体は原点を頂点にする立方体と共有店を持つ範囲で自由に動けると考えて解いた
こう考えてよい理由やきっかけで、立方体どうしが共有点を持たない場合、辺が共通部分を持つように平行移動しても答えが変わらないという事がある。
つまり間があいていたら詰めて考えてよいので、実は探索する幅が非常に小さいのだ。なので、一般性のある仮定を置くことが大事となる。
次に包除の原理を使うと、
m(C1orC2orC3) = V1 + V2 + V3
= m(C1) + m(C2) + m(C3) - m(C1andC2) - m(C2andC3) - m(C3andC1) + m(C1andC2andC3)
= m(C1) + m(C2) + m(C3) - (m( (C1andC2)notC3)+m(C1andC2andC3) -m( (C2andC3)notC1)+m(C2andC3andC1) - m( (C3andC1)notC2)+m(C3andC1andC2) )+ m(C1andC2andC3)
= 343 * 3 - V2 -2V3
よって
1029 = V1 + 2V2 + 3V3
で、後は全探索するだけなのだが、ここでちょっとした言い換えをする必要がある事に注意
直方体は
a<=x<=b , c<=y<=d , e<=z<=f をすべて満たす(x,y,z)の存在範囲と言い換えられるので、x,y,z成分だけみて共通部分を考えて、各成分の共通部分の長さの積で直方体の体積が求まることは気づかないと駄目。
やってることは感覚的に難しくないんだけど、書いてみると結構面倒くさいねこれ
書くのも面倒くさくてたたきをAIに書いてもらわなかったら発狂してたと思う
def main():
V1, V2, V3 = map(int, input().split())
# V1+V2+V3 > 1029 なら No
if V1 + 2*V2 + 3*V3 != 1029:
print("No")
return
# V1 = 1029,V2 = 0,V3 = 0 なら Yes
if V1 == 1029 and V2 == 0 and V3 == 0:
print("Yes")
print("0 0 0 10 10 10 20 20 20")
return
for a2 in range(8):
for b2 in range(8):
for c2 in range(8):
for a3 in range(-8,8):
for b3 in range(-8,8):
for c3 in range(-8,8):
X = max(0, min(7, a3 + 7) - max(a2, a3))
Y = max(0, min(7, b3 + 7) - max(b2, b3))
Z = max(0, min(7, c3 + 7) - max(c2, c3))
V3_calc = X * Y * Z
X1 = 7-a2
Y1 = 7-b2
Z1 = 7-c2
V4 = X1 * Y1 * Z1 - V3_calc
X2 = max(0, min(a3 + 7, 7) - max(a3, 0))
Y2 = max(0, min(b3 + 7, 7) - max(b3, 0))
Z2 = max(0, min(c3 + 7, 7) - max(c3, 0))
V5 = X2 * Y2 * Z2 - V3_calc
X3 = max(0, min(a2 + 7, a3 + 7) - max(a2, a3))
Y3 = max(0, min(b2 + 7, b3 + 7) - max(b2, b3))
Z3 = max(0, min(c2 + 7, c3 + 7) - max(c2, c3))
V6 = X3 * Y3 * Z3 - V3_calc
V7 = V4 + V5 + V6
Vr = 1029 - 3*V3_calc - 2*V7
if Vr == V1 and V7 == V2 and V3_calc == V3:
print("Yes")
print(f"0 0 0 {a2} {b2} {c2} {a3} {b3} {c3}")
return
print("No")
if __name__ == "__main__":
main()
atcoder.jp
見るからにセグメントツリー
セグメントツリーでどうやって解こう？ってところから考える
と、最大値、二番目に大きい値の数値と個数を保持する感じにseg_funcを設定しようという感じで、seg_func をなんとか設定することから解こうという感じの思考になるはず。
seg_func をちょっと冗長に書くとTLEになる（計算量が2倍になるとNG）ので、かなり苦心した。苦心したの主語はGPTです。
import sys
N, Q = map(int, sys.stdin.readline()[:-1].split())
A = list(map(int, sys.stdin.readline()[:-1].split()))
Query = [list(map(int, sys.stdin.readline()[:-1].split())) for _ in range(Q)]
def segfunc(node1, node2):
# node1とnode2の最大値と2番目に大きい値を比較して、新しい最大値と2番目に大きい値を決定
max_val = max(node1[0], node2[0])
second_max_val = -1 # 初期値は存在しないことを示す-1
# 最大値が同じ場合、最大値の個数を合算し、2番目に大きい値はそれぞれの2番目に大きい値の最大値
if node1[0] == node2[0]:
max_count = node1[1] + node2[1]
second_max_val = max(node1[2], node2[2])
second_max_count = (node1[3] if node1[2] == second_max_val else 0) + (node2[3] if node2[2] == second_max_val else 0)
else:
# 最大値が異なる場合、最大値の個数は大きい方の個数
# 2番目に大きい値は、最大値ではない方の最大値と、それぞれの2番目に大きい値の最大値
if max_val == node1[0]:
max_count = node1[1]
second_max_val = max(node2[0], node1[2])
else:
max_count = node2[1]
second_max_val = max(node1[0], node2[2])
# 2番目に大きい値の個数を計算
second_max_count = 0
if node1[0] == second_max_val:
second_max_count += node1[1]
if node2[0] == second_max_val:
second_max_count += node2[1]
if node1[2] == second_max_val:
second_max_count += node1[3]
if node2[2] == second_max_val:
second_max_count += node2[3]
return (max_val, max_count, second_max_val, second_max_count)
#################
m = -1
#################
class SegTree:
"""
init(init_val, ide_ele): 配列init_valで初期化 O(N)
update(k, x): k番目の値をxに更新 O(logN)
query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
"""
def __init__(self, init_val, segfunc, ide_ele):
"""
init_val: 配列の初期値
num: n以上の最小の2のべき乗
tree: セグメント木(1-index)
"""
n = len(init_val)
self.segfunc = segfunc
self.num = 1 << (n - 1).bit_length()
self.tree = [ide_ele] * 2 * self.num
# 配列の値を葉にセット
for i in range(n):
self.tree[self.num + i] = init_val[i]
# 構築していく
for i in range(self.num - 1, 0, -1):
self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])
def update(self, k, x):
"""
k番目の値をxに更新
k: index(0-indexed)
"""
k += self.num # 実際の配列位置に変換
self.tree[k] = (x, 1, -1, 0) # 新しい値とその個数をセット、2番目に大きい値は存在しないと仮定
# 根に向かって遡りながら情報を更新
while k > 1:
k //= 2
self.tree[k] = segfunc(self.tree[k * 2], self.tree[k * 2 + 1])
def query(self, l, r):
"""
[l, r)のsegfuncしたものを得る
l: index(0-index)
r: index(0-index)
"""
l += self.num
r += self.num
while l < r:
if l & 1:
res = self.segfunc(res, self.tree[l])
l += 1
if r & 1:
res = self.segfunc(res, self.tree[r - 1])
l >>= 1
r >>= 1
return res
# セグメントツリーの初期化
init_val = [(a, 1,-1,0) for a in A] # 各要素を(最大値, 2番目に大きい値)の形式で初期化
seg = SegTree(init_val, segfunc, ide_ele)
for query in Query:
if query[0] == 1:
# タイプ1のクエリ: 指定された位置の値を更新
_, p, x = query
seg.update(p - 1, x) # セグメントツリーの更新
elif query[0] == 2:
# タイプ2のクエリ: 指定された区間内で2番目に大きい値の個数を計算
_, l, r = query
max_val, max_count, second_max_val , second_max_count = seg.query(l - 1, r)
if second_max_val == -1:
print(0) # 2番目に大きい値が存在しない場合
else:
# 2番目に大きい値が存在する場合、その個数を数える
print(second_max_count)
セグメントツリーのコードはもうどこからコピペしてきたのか分からないコードです。出典を忘れたものを書くなと言われたらそうなんだけど、一般的な内容なのでここは許してほしいです。
