リチウムイオン電池は表記上の残量が0になっても体温で暖めたらほんの少し回復する。冬の寒い時期は特に有効。
それはともかく、時刻ちょうどにカフェに出入りしたときや、ちょうど0でカフェに着いたときの成功失敗の混乱を無くすためか、電池の増減時刻が0.5となっている。
プログラムの実装上は、これを0.5切り落とした時刻と解釈して、「ちょうど $t$ にカフェに着いたら電池は減らない」「$t$ にカフェから出たら減る」と解釈した方がやりやすい気がする。
出発
A1 減る
B1 - A1 増える
A2 - B1 減る
...
BN - AN 増える
T - BN 減る
「減る」ときに0以下にならなければOK。ちょうど0になるのはアウト。
最初と最後を忘れないように。
Python3
n, m, t = map(int, input().split())
s = 0
bat = n
for _ in range(m):
a, b = map(int, input().split())
if a - s >= bat:
print('No')
exit()
bat -= a - s
bat = min(n, bat + b - a)
s = b
if t - s >= bat:
print('No')
else:
print('Yes')
問題名はラテン語で「12の鉄」？
ARCの中～後半などの数えあげでは問題をこのような問題に帰着させることが解法の一端となることもある、教育的な問題。
なかなか一からこれを導き出すのはヒラメキが必要と思うが、
というのが成り立つ。
今回は各棒の長さは1以上ないといけないので、あらかじめ12本に1ずつ配って、残り $L-12$ を振り分けるとよい。
Python3
l = int(input()) - 12
ans = 1
for i in range(l + 11, l, -1):
ans *= i
for i in range(2, 12):
ans //= i
print(ans)
レーベンシュタイン距離というのがあり、今回の問題と概念が近い（というか説明は異なるが結果的にはそのもの）。
以下のDPを使う。整数列 $S$ の先頭 $i$ 要素を $S_{1～i}$ と表現する。
$i,j=0$ の時は空とする。
すると、片方が空の時は全部消すしか無いので、以下は自明に決まる。
A\B| - 1 3 1
---+------------
- | 0 1 2 3
1 | 1
2 | 2
1 | 3
3 | 4
ここで、「$S$ と $T$ の最良な結果」とは、$x+y$ が最小になるようにした場合に残った整数列 $S',T'$ を指すとする。
説明のための概念であり、何かしら存在していることがわかれば、その具体的な形はわからなくて問題ない。
$A_i$ と $B_j$ が同じ場合は、$A_{1～i-1}$ と $B_{1～j-1}$ の最良な結果の後ろにそのまま残せばよい。
$A_i$ と $B_j$ が異なる場合は、以下の4通りの選択肢があり、一番少なくなるものを採用すればいい。
$A_i$ を消す
$B_j$ を消す
両方残す
両方消す
まぁ、両方消すのは常に両方残すより悪いので無視して、3つを比較すればよい。
Python3
n, m = map(int, input().split())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
INF = 10 ** 18
dp = [[INF] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = i
for j in range(m + 1):
dp[0][j] = j
for i, a in enumerate(aaa, start=1):
for j, b in enumerate(bbb, start=1):
if a == b:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
# print(*dp, sep='\n')
print(dp[n][m])
Fenwick木やセグメント木といえば、数列の累積和を更新しながら管理する方法が代表的だが、「累積XOR」でもできますよ、という問題。
いやまぁ、それだけの典型色強めな問題だけど、緑diffってマジですか。
Python3
class FenwickTreeXor:
def __init__(self, n):
self.size = n
self.tree = [0] * (n + 1)
def get(self, i):
s = 0
while i > 0:
s ^= self.tree[i]
i -= i & -i
return s
def xor(self, i, x):
while i <= self.size:
self.tree[i] ^= x
i += i & -i
n, q = map(int, input().split())
aaa = list(map(int, input().split()))
fwt = FenwickTreeXor(n)
for i, a in enumerate(aaa, start=1):
fwt.xor(i, a)
buf = []
for _ in range(q):
t, x, y = map(int, input().split())
if t == 1:
fwt.xor(x, y)
elif t == 2:
buf.append(fwt.get(y) ^ fwt.get(x - 1))
else:
raise NotImplementedError
print('\n'.join(map(str, buf)))