目次
ARC 094
C - Same Integers
問題
- 3つの数字 $A,B,C$ が与えられる
- 「2つ選んで1ずつ足す」か「1つ選んで2を足す」操作を繰り返して、3つを同じにする
- 何回操作すれば良いか
解法
操作は加算しか無いので、基本的に一番大きい数字に残りを合わせればよい。
すると足すべき数の合計は、$A,B,C$で最大の数がたとえば$A$だったとすると、$(A-B)+(A-C)$ となる。
そしていずれの操作でも、1回で全体として2ずつ差が縮まっていくので、回数は $\frac{(A-B)+(A-C)}{2}$ となる。
ただし、$(A-B)+(A-C)$ が奇数の場合は詰めの時に工夫する必要がある。この時はたとえば(25 25 24)みたいに1つだけ1足りない状態になる。この場合は(25 25 26)→(26 26 26)のように、2回余分に操作しないことには3数を同じに出来ない。
a, b, c = map(int, input().split())
m = max(a, b, c)
s = sum((m - a, m - b, m - c))
if s % 2 == 1:
print(s // 2 + 2)
else:
print(s // 2)
D - Worst Case
問題
- コンテストが2回開催され、いずれのコンテストでも同率はいなかった
- 最終順位は各回の順位を $A,B$ とすると、$A \times B$ が小さい方から上位になる
- 高橋くんの各回の順位が $A_i,B_i$ だった時、高橋くんより最終順位の高い人が、最大で何人存在しうるか（同率は除く）
- クエリは最大100個。各$A_i,B_i$について出力せよ
解法
ぼんやりと方針は立つものの、細かな調整が難しい。後から考えれば、editorialにあるように「$A_i=B_i$」「$A_i+1=B_i$」「それ以外」で場合分けするのが網羅性がわかりやすいと気付くが、本番ではちょこまかやってたら通ってしまった（運ゲー）。
一応、解いた時の考えをメモ。
$M=A_i \times B_i$ とすると、$Int(\sqrt{M}) \times 2$ から、状況に応じて1～3を引いた値が答えとなる。以下、$S=Int(\sqrt{M})$ とする。
たとえば $A_i=6,B_i=10$ とする。$M=60$ で、$S=Int(\sqrt{60})=7$ となる。
すると、以下のケースを考えると、いずれも積が60以下の組が14個できる。
最悪ケースの順位表(仮) コンテストA 1 2 3 4 5 6 7 8 9 10 11 12 13 14 コンテストB 14 13 12 11 10 9 8 7 6 5 4 3 2 1
和が等しい2数の積は、2数が近い時が最大となり、差が離れるにつれて小さくなる。なので、中央（この場合は(7,8)）を $M$ をギリギリ超えないように決めてやってその左右に連番を広げると、どの組も $M$ を超えないように $A$ と $B$ の組が $2S$ 個作れる。
なお、$M=60$ の例では中央が$7 \times 8$ と異なる数字になったが、たとえば $M=50$ では中央が $7 \times 7$ と同じ数字になる。その場合、順位表の長さは1つ短くなる。
A 1 2 3 4 5 6 7 8 9 10 11 12 13 B 13 12 11 10 9 8 7 6 5 4 3 2 1
$S \times (S+1) \ge M$ なら、$2S$ から1を引けばよい。
基本的にこの組数が、高橋くんより総合順位が上になる人の最大数であり、ここから除外すべきケースを除外していく。
高橋くん本人を除く
さて、各コンテストで同率はいないので、高橋くん自身が取った順位がかぶる場合は除外して考えないといけない。
$A_i \le B_i$ と固定しても一般性は失わない。すると、$A_i$は順位表(仮)の、中央より左側（奇数個の場合は中央含む）に存在する。
Ai=6, Bi=10 ↓中央 A 1 2 3 4 5 ⑥ 7 8 9 10 11 12 13 14 B 14 13 12 11 10 9 8 7 6 5 4 3 2 1
ここで、14個を保ったまま $A_i$ を使わないで組を作れるか。これはできない。$A_i$ を使わないで積の最大値を最小化するのは、
← A 1 2 3 4 5 7 8 9 10 11 12 13 14 15 B 14 13 12 11 10 9 8 7 6 5 4 3 2 1
のように $A_i$ を取り除きそのまま右側をスライドさせた形だが、そもそも中央は $M$ をギリギリ超えないように決めた。しかも $A_i$ は中央より左にあるので、必ず中央が $M$ を超えてしまう。
よって、$2S$ から高橋くん本人の分(1)は必ず引かなくてはならない。
$B_i$ に関しては、$B$ に存在していることもしていないこともある。しかし、仮に存在していたとしても、さらに追加で答えを減らす必要は無い。
順位表(仮)で $A_i$ と組になっている数値を $B_p$ とすると、$B_i$ は $B_p$ と同じか、より大きい。 よって、$B_i$ が $B$ に存在するとしたら、$A_i$ と同じ位置か、より左側ということになる。
ならば空いた部分をスライドさせて繋げてしまって問題ない。ズレた部分の積は元の値より小さくなるため、$M$ を超える心配は無い。
A 1 2 3 4 5 ○ 7 8 9 10 11 12 13 14 B 14 13 12 11 ○ 9 8 7 6 5 4 3 2 1 （○: 高橋くんの順位とのかぶり） ↓ A 1 2 3 4 5 7 8 9 10 11 12 13 14 B 14 13 12 11 9 8 7 6 5 4 3 2 1
同率になるケースを除く
「$M$ が平方数だが、$A_i \ne B_i$」という場合、さらに1を引く必要がある。
たとえば $A_i=4, B_i=9, M=36$ の時、順位表(仮)は以下になる。
A 1 2 3 4 5 6 7 8 9 10 11 B 11 10 9 8 7 6 5 4 3 2 1
$M$ が平方数の場合、中央が $M$ と等しくなるため、答えからは除く必要がある。$A_i=B_i$ ならば「高橋くん本人を除く」の際に除かれるため考慮しなくて良いが、異なる数の場合、中央より左に高橋くん本人の順位があり、それとは別に中央を除かなければならない。
これらのケースを考慮して除いた数が答えとなる。
from math import sqrt
q = int(input())
for _ in range(q):
a, b = map(int, input().split())
m = a * b
s = int(sqrt(m))
ans = 2 * s - 1
if s * (s + 1) >= m:
ans -= 1
if s * s == m and a != b:
ans -= 1
print(ans)
E - Tozan and Gezan
問題
- 非負整数からなる要素数 $N$ の2つの数列 $A,B$ があり、$A$ と $B$ の数値の合計は等しい
- $A$ と $B$ の数の並びが等しくなるまで、トザンくんとゲザンくんが以下の操作を繰り返す
- まずトザンくんが $A$ の正の任意の要素を1減らす
- 次にゲザンくんが $B$ の正の任意の要素を1減らす
- トザンくんはなるべく操作回数を多くしたい。ゲザンくんはなるべく少なくしたい。
- 操作回数はいくらになるか
解法
操作は減らすことしか出来ないため、仮に $A_i \gt B_i$ となる $i$ が存在した場合（最初からAとBが全く同じで無い限り、必ず存在する）、トザンくんが $A_i$ に触らない限り、数列は同じになり得ない。操作回数を多くしたいトザンくんは、まずは $A_i$ には触らず、その間に他の $A$ の要素を全て0にするのが最適となる。
$A_i \gt B_i$ となる $i$ が複数存在するならば、トザンくんはどれを残せば良いか。
最終的に、数列は以下の形で等しくなって終了する。
A 0 0 ... 0 Bi 0 ... 0 B 0 0 ... 0 Bi 0 ... 0
1操作につき数列の合計は1減少するので、初期状態の数列の合計($S$ とする)から、最終的に残る $B_i$ を引いた値が操作回数となる。
操作回数を多くするならば、$B_i$ はなるべく小さいものを選んだ方がよい。よって、$A_i \gt B_i$ を満たす $B_i$ のうち最小のものを $B_{min}$ として、$S-B_{min}$ が答えとなる。
n = int(input())
min_b = float('inf')
sa = 0
for _ in range(n):
a, b = map(int, input().split())
if a - b > 0:
min_b = min(min_b, b)
sa += a
if min_b == float('inf'):
print(0)
else:
print(sa - min_b)
F - Normalization
問題
a,b,cの3種の文字からなる文字列 $S$ が与えられる- 以下の操作を0回以上行って作ることの出来る文字列の総数を答えよ（mod 998244353）
- 操作
- 隣り合う異なる2文字を、
a,b,cのうちそのいずれでも無い文字に置き換える - 例:
abcabc→abcccc
解法
$S$ を $a=0, b=1, c=2$ に置き換えて、その合計をとり、$\mod{3}$ を取った値を考えると、操作を行っても値は維持されることが分かる。
abcabc → 0+1+2+0+1+2 = 6 == 0 mod 3 abbbbc → 0+1+1+1+1+2 = 6 == 0 mod 3 abcccc → 0+1+2+2+2+2 = 9 == 0 mod 3
変化 ab → cc | bc → aa | ca → bb 置換 01 → 22 | 12 → 00 | 20 → 11 mod 3 1 → 1 | 0 → 0 | 2 → 2
なので、$\mod{3}$ の値が異なる文字列間は互いに変換できない。
また、1回でも変換を行った文字列は、同じ文字が連続する箇所が必ず1つ以上存在する。
で、どうやら$|S| \ge 4$ において、この2条件（$\mod{3}$ が等しい、同じ文字が連続する箇所が1つ以上）を満たすならば、少なくともどちらかからどちらかに変換が可能であると証明できるらしい。
証明は後で考える
として、その条件に合致する文字列の個数を数え上げればいいことになる。
以下の動的計画法を考える。
dp[文字列長][同じ文字が連続する箇所が存在フラグ][mod 3][最後の文字] = パターン数
ただし、同じ文字が連続する箇所が既にある場合、最後の文字は特に気にしなくて良いので、計算量を減らすため以下で良い。
dp[文字列長][0][mod 3][最後の文字] = パターン数 dp[文字列長][1][mod 3] = パターン数
最終的に、$dp[|S|][1][S \mod{3}]$ が答えとなる。ただし、もし $S$ に、同じ文字が連続する箇所が1つも無かった場合、カウントされていないので、1を足す必要がある。
ちなみに、このパターン数は対称性が無い。もし $\mod{3}=0,1,2$ でパターン数が同じなら、（全ての文字列数 - 全ての同じ文字が隣接しない文字列数）÷3 $=\frac{3^{|S|}-3 \times 2^{|S|-1}}{3}$ で計算できそうなのだが、残念ながらそうではないので、数え上げるしかない。
まとめると、
- 全て同じ文字の場合は変換が1回も出来ないので1
- $|S|=2,3$ の場合は手計算して埋め込んでおく
- $|S| \ge 4$ の場合は動的計画法でカウントする
def solve(s):
if all(a == b for a, b in zip(s, s[1:])):
return 1
if len(s) == 2:
return 2
elif len(s) == 3:
if s[0] == s[1] or s[1] == s[2]:
return 6
elif s[0] == s[2]:
return 7
else:
return 3
# dp[has succession=0][mod 3][last char], dp[has succession=1][mod 3]
dp = [[[0] * 3 for _ in range(3)], [0] * 3]
dp[0][0][0] = 1
dp[0][1][1] = 1
dp[0][2][2] = 1
MOD = 998244353
for _ in range(len(s) - 1):
ndp = [[[0] * 3 for _ in range(3)], [0] * 3]
dp0, dp1 = dp
ndp0, ndp1 = ndp
sdp1 = sum(dp1)
ndp0[0][0] = (dp0[0][1] + dp0[0][2]) % MOD
ndp0[1][0] = (dp0[1][1] + dp0[1][2]) % MOD
ndp0[2][0] = (dp0[2][1] + dp0[2][2]) % MOD
ndp0[0][1] = (dp0[2][0] + dp0[2][2]) % MOD
ndp0[1][1] = (dp0[0][0] + dp0[0][2]) % MOD
ndp0[2][1] = (dp0[1][0] + dp0[1][2]) % MOD
ndp0[0][2] = (dp0[1][0] + dp0[1][1]) % MOD
ndp0[1][2] = (dp0[2][0] + dp0[2][1]) % MOD
ndp0[2][2] = (dp0[0][0] + dp0[0][1]) % MOD
ndp1[0] = (dp0[0][0] + dp0[1][2] + dp0[2][1] + sdp1) % MOD
ndp1[1] = (dp0[1][0] + dp0[2][2] + dp0[0][1] + sdp1) % MOD
ndp1[2] = (dp0[2][0] + dp0[0][2] + dp0[1][1] + sdp1) % MOD
dp = ndp
return (dp[1][sum(map(ord, s)) % 3] + all(a != b for a, b in zip(s, s[1:]))) % MOD
s = input()
print(solve(s))
