ARC 088
C - Multiple Gift
問題
- 数列 $A=\{a_1,a_2,...\}$ を作る
- 各項は $X$ 以上 $Y$ 以下
- 各項は1つ前の項の倍数（2倍以上）
- 作れる $A$ の最大の長さは？
例
X=5 Y=1234
↓
A = {5, 10, 40, 120, 1200}
x2 x4 x3 x10
などとすると、条件を満たしつつ長さ 5 の数列が出来る。（この例は最長ではない）
解法
各項は1つ前の項より大きくなるが、上限が $Y$ と決められているので、なるべく値は小さく保った方がよい。よって最小値の $X$ から始めて、2倍、2倍にしていくのがよい。3倍以上にしていいことは特にない。
$2^kX \le Y \lt 2^{k+1}X$ という $k$ を見つければ、$A=\{2^0X,2^1X,2^2X,...,2^kX\}$ となり、$k+1$ が答え。
x, y = map(int, input().split())
ans = 1
while True:
x <<= 1
if x > y:
break
ans += 1
print(ans)
D - Wide Flip
問題
'0'と'1'からなる文字列 $S$ が与えられる- ある整数 $K$ を決める
- 「$K$ 以上の長さの区間を好きに決め、その中の
'0'と'1'を反転させる」という操作を好きなだけ行い、文字列を全て'0'にする - $K$ として取れる最大の値は？
例
S = 00011011110 たとえば K = 3 とすると、3以上の範囲を一度に反転できる。 00011011110 → 11100011110 → 11111111110 → 00000000000 できた！ ~~~~~ ~~~ ~~~~~~~~~~ K = 6 でもできる 00011011110 → 00000100000 → 00000011111 → 11111111111 → 00000000000 ~~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~~~~~~
解法
文字列中に '..0011..' のように '0' と '1' が隣接するところがあったら、必ず1回、その間を範囲境界として操作しなければならない。操作は、このような「違う数字が隣接している箇所を無くす」意味があると考えるとわかりやすい、かも。
逆に、それさえできれば、1文字単位で反転できる。
K = 3 000010000 → 011100000 → 000000000 ~~~~ ~~~ 「1」のみを反転できた
では、範囲の境界に出来ない場合はどのような場合か。$K$ が長すぎる（文字列の半分以上）と、範囲を $S$ のどちらの端に寄せたとしても、同一範囲にしか出来ない区間が出てくる。
K = 7 000010000 000010000 ~~~~~~~ ~~~~~~~
上の例では、真ん中5文字は、右に寄せても左に寄せても、同一範囲になるしか無い。その中に異なる文字が隣接した箇所があると、その $K$ では全てを '0' にはできないということになる。
同一範囲にしかならない区間があっても、それが最初から全て同じ文字だと、問題なく揃えられる。
K = 6 000111000 → 111000000 → 111111111 → 000000000 ~~~~~~ ~~~~~~ ~~~~~~~~~ 真ん中3文字は同一区間になるしか無いが、最初から同じなので、全て0にできる
よって、解法は大まかに以下になる。
- 中心の文字を取得
- 前後に範囲を広げて、どこまで同一の文字が続くか調べる
ただし $|S|$ の偶奇によって探索範囲を微調整する必要がある。
def solve(s):
n = len(s)
if n == 1:
return 1
if n == 2:
return 2 if s[0] == s[1] else 1
ci = n // 2
c = s[ci]
if n & 1:
for di in range(1, ci + 1):
if c == s[ci - di] == s[ci + di]:
pass
else:
return ci + di
return n
if c != s[ci - 1]:
return ci
for di in range(1, ci):
if c == s[ci - di - 1] == s[ci + di]:
pass
else:
return ci + di
return n
print(solve(input()))
もっとスマートに考えると、各「異なる文字が隣接する箇所」で、左端と右端からの距離のうち大きい方が、そこを無くすために必要な $K$ の値である。その最小値が、答えとなる。
0 0 0 1 1 0 1 1 1 1 0 左から必要 3 5 6 10 右から必要 8 6 5 1 大きい方 8 6 6 10 → この中の最小値 6 が答え
E - Papple Sort
問題
- 英小文字のみからなる文字列 $S$ が与えられる
- 「隣り合う2つの文字を入れ替える」という操作を繰り返して $S$ を回文にする
- 回文にすることが不可能なら -1、可能なら最小手数を出力
例
S = aaabbccdd
操作手数
0～4 aaabbccdd → aababccdd → abaabccdd → abaacbcdd → abacabcdd
~~ ~~ ~~ ~~ ~~
5～9 → abcaabcdd → abcaabdcd → abcaadbcd → abcadabcd → abcdaabcd
~~ ~~ ~~ ~~ ~~
10-15 → abcdaabdc → abcdaadbc → abcdadabc → abcdadacb → abcdadcab → abcdadcba
~~ ~~ ~~ ~~ ~~
解法
回文に出来る出来ないは、文字毎にカウントして、奇数回出てくる文字が2つ以上あったら不可。1つ以下なら可能。
問題はどうやって回文にするか。
隣り合う2つの文字を入れ替える、その手数を数えるという行為から、バブルソートが連想される。問題タイトルもどことなくバブルソートっぽい響きだし。
そこで、完成形である回文の各文字に頭から $1,2,3,...,|S|$ と対応させ、それを元の $S$ の順番に並び替えた数列を考えると、その数列をバブルソートした時の手数を求めればよいと考えられる。
| S | aaabbccdd |
| 完成形 | abcdadcba ⇒ 1,2,3,4,5,6,7,8,9 |
| もとの順に反映 | aaabbccdd ⇔ 1,5,9,2,8,3,7,4,6 |
この例では、1,5,9,2,8,3,7,4,6 のバブルソートの交換手数が答え。
ここで考えなければならない点は以下。
- 同じ文字に対しては、どれとどれを対応させるの？
- 完成形は複数パターン考えられるけど、どれにするかで手数変わるよね？ どう決めればいいの？
同じ文字の中での順番
S = aaabbccdd "a" だけに着目すると、 [完成形] [元] a___a___a → aaa______ 1 5 9 元の"aaa" に対応させるべきは、159? 195? 951?
昇順、つまり「完成形で出てくる順 ＝ $S$ で出てくる順」にすればよい。
隣接した文字を入れ替えるという操作上、元の $S$ と完成形で左右の位置が入れ替わっている2つの文字は、必ずどこかで「直接その文字同士の入れ替え操作」が行われることになる。それが同じ文字同士だった場合、実質的には何も変わらず、結果として手数が1増えただけであり、無駄な操作である。
a1 a2 a3 1 9 5 ← どこかで a2 と a3 を直接入れ替える必要があり、無駄な操作である
よって、この例では 1,5,9 の順がよい。
完成形の決め方
左詰めにしたらとりあえず通った。
同じ文字の内では順番が変わらないので、$S$ が与えられた時点で、回文で左右対応する位置に来るペアは一意に決定する。
S = aaababccb 区別するため番号を振る a1 a2 a3 b1 a4 b2 c1 c2 b3 すると、回文で左右対応する位置に来るペアは (a1,a4) (a2,a3) (b1,b3) (c1,c2) となり、b2が真ん中と、一意に決まる
バブルソートの最小交換回数の求め方については、「各項につき、自身よりも大きい、かつ左側にある項数の和」であることが知られている。
5 1 3 4 2
5 左側には何も無い 0
1 左側に自身より大きい5がある 1
3 左側に自身より大きい5がある 1
4 左側に自身より大きい5がある 1
2 左側に自身より大きい3,4,5がある 3
合計して、6回が、バブルソートにかかる交換回数
これを踏まえて、どのペアをより外側にした方がよいかを考える。
(b1,b3) (c1,c2) を考えると、元々の位置関係は「b1 c1 c2 b3」、なので完成形でもこの順番を保っていると（この部分だけ見た時の）交換回数は 0。これを、完成形で「c1 b1 b3 c2」の順にすると、交換回数が 2回増える。
(a1,a4) (b1,b3) を考えると、元々の位置関係は「a1 b1 a4 b3」なのでこのまま完成形にはできない。「a1 b1 b3 a4」か「b1 a1 a4 b3」のどちらかにする必要があるが、これはどちらも（この部分だけ見た場合）1回。
(a2,a3) (b1,b3) を考えると、元々の位置関係は「a2 a3 b1 b3」なのでこのまま完成形には出来ない。「a2 b1 b3 a3」か「b1 a2 a3 b3」のどちらかにする必要があるが、どちらも 2回。
各ペアの関係は、この3通りに分けられる。
よって、ペアの左側 (a1,a4) (a2,a3) (b1,b3) (c1,c2) だけ見て、元々の位置関係が x1 < x2 ならば、x1を含むペアはx2より外側に配置すれば、無駄に交換回数が増えることは無い･･････ように見える。
でも、3つ以上のペアの関係性を考え出すと、この方法が最小である証明はよくわからん。
from string import ascii_lowercase
class Bit:
def __init__(self, n):
self.size = n
self.tree = [0] * (n + 1)
def sum(self, i):
s = 0
while i > 0:
s += self.tree[i]
i -= i & -i
return s
def add(self, i, x):
while i <= self.size:
self.tree[i] += x
i += i & -i
def solve(s):
indices = {c: [] for c in ascii_lowercase}
for i, c in enumerate(s):
indices[c].append(i)
n = len(s)
center = n // 2
bubbles = [-1] * n
odd_flag = False
pairs = []
for c, ids in indices.items():
cnt = len(ids)
if cnt & 1:
if odd_flag:
return -1
odd_flag = True
bubbles[ids[cnt // 2]] = center + 1
for i in range(cnt // 2):
li, ri = ids[i], ids[-i - 1]
pairs.append((li, ri))
pairs.sort()
for i, (li, ri) in enumerate(pairs):
bubbles[li] = i + 1
bubbles[ri] = n - i
ans = 0
bit = Bit(n)
for i, m in enumerate(bubbles):
ans += i - bit.sum(m)
bit.add(m, 1)
return ans
print(solve(input()))
