最初に
投稿遅れてすいません
寒いですね 僕が住んでいるとこは、明日(11/7)最低気温が、1度予報です(長野県)
自転車に行ったら手がかじかみました
投稿が遅れた言い訳に寒さを出そうと思ったけどやめた
さて本題
いつもどおりの配点で、普通に大丈夫かなーと思ったらB問題に苦戦しました
でB問題は結局ACして、C問題は簡単ですぐ解けました
それでD問題は、この手の問題はdfsで解けると思って書いたらACしました
それじゃ一問ずつ感想書きますか
使っているライブラリ
# ライブラリと関数と便利変数
# ライブラリ
from collections import deque, defaultdict, Counter
from math import pi
from itertools import permutations
import bisect
import sys
# cortedcontainersは使うときだけ wandbox非対応なので
# from sortedcontainers import SortedDict, SortedSet, SortedList
# 関数
def pow(x: int, n: int, t: int = 1):
# O(log N)
if t == 1:
ans = 1
while n:
if n % 2:
ans = ans * x
x = x * x
n >>= 1
return ans
ans = 1
while n:
if n % 2:
ans = (ans * x) % t
x = (x * x) % t
n >>= 1
return ans
def is_prime(n: int) -> bool:
# O(√N)
if n == 1:
return False
i = 2
s = n**0.5
while i < s:
if n % i == 0:
return False
i += 1
return True
def gcd(a, b):
while a > 0 and b > 0:
if a > b:
a = a % b
else:
b = b % a
return max(a, b)
def lcm(a, b):
return (a * b) // gcd(a, b)
# 標準入力系
def s():
return sys.stdin.readline().rstrip()
def sl():
return s().split()
def ii():
return int(s())
def il(add_num: int = 0):
return list(map(lambda i: int(i) + add_num, sl()))
# 便利変数
INF = 10**18
lowerlist = list("abcdefghijklmnopqrstuvwxyz")
upperlist = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# テンプレ
class SegmentTree:
# 鉄則本のパクリですけどよろしく
def __init__(self, N) -> None:
# サイズは要素の数
self.size = 1
while self.size < N:
self.size *= 2
self.data = [0] * (self.size * 2)
def update(self, ind, x):
ind = ind + self.size - 1
self.data[ind] = x
while ind >= 2:
ind //= 2
self.data[ind] = max(self.data[ind * 2], self.data[ind * 2 + 1])
def query(self, l, r, a, b, u):
if r <= a or l >= b:
return -INF
if l <= a and b <= r:
return self.data[u]
m = (a + b) // 2
return max(self.query(l, r, a, m, u * 2), self.query(l, r, m, b, u * 2 + 1))
A問題
問題文の要約
同じ色のボールがあれば２つ選び両方捨てるという問題(そのまんま)
defaltdictでまとめてやれば簡単にできた
acコード 全文
関数名はご想像にお任せします
クソコードですいません
L = il()
D = defaultdict(int)
for i in L:
D[i] += 1
ans = 0
for v in D.values():
if v == 2:
ans += 1
elif v == 3:
ans += 1
elif v == 4:
ans += 2
print(ans)
B問題
問題文の要約
$i$種類目のゴミは$q_i$で割ったあまりが$t_i$ならゴミが収集されて
$d$日目に$t$種類目のゴミが出たら、次にそれが回収される日を答えてください
すいません 少し要約しただけです
$d // q_t * q_t + t_t < d$なら条件を満たしていないので$(d // q_t + 1)*q_t+t_t$を出力
$d // q_t * q_t + t_t >= d$なら条件を満たしているので$d // q_t * q_t + t_t$を出力します
acコード 全文
関数名はご想像にお任せします
N = ii()
A = [il() for _ in [0] * N]
Q = ii()
for _ in [0] * Q:
t, d = il()
t -= 1
tmp = d // A[t][0]
if tmp * A[t][0] + A[t][1] < d:
tmp += 1
print(tmp * A[t][0] + A[t][1])
C問題
問題文の要約
そのまんまですけど 前回の記録を取っておいて、lenが0なら-1を出力してlenが1以上なら最後の値を出力するという問題です
まあdefaltdictに取っておけば簡単です
acコード 全文
クソコードですいません
N = ii()
D = defaultdict(list)
A = il()
B = []
for i, a in enumerate(A):
if len(D[a]) == 0:
B.append(-1)
else:
B.append(D[a][-1])
D[a].append(i + 1)
print(*B)
D問題
問題文を要約...(結構複雑なのでパス)
あまりを取らないので、多分実装できればいい系の問題だと思ってdfsで実装した
なんやかんや迷ってメモ化再帰とかしようかなと思ったりして時間かかった
で結局残り20分ぐらいでACした
acコード
あまりにもコードが汚いのでお見せできません
一応url載せときます
解説の実装例がpythonなのでそちらを見てください
最後に
初の4完して嬉しかった(完を打つのにスペースキーすごい連打したw)
緑パフォ出してレートは26上がりました