AtCoder Grand Contest 026
やっぱり今回も駄目だったよ
A - Colorful Slimes 2
問題
- スライムが1列に $N$ 匹並ぶ。$i$ 番目のスライムの色は $a_i$
- 同じ色のスライムが隣り合っていると合体してしまう
- 何匹かのスライムの色を変更し、1匹も合体しないようにする
- スライムの色の種類は、10000通り
- 最低何匹の色を変更すればよいか
解法
順番に見ていって、$i$ 番目が $i-1$ 番目と同じ色だったら変更すればよい。
この時に、スライムの色の種類が2色しか無かったりすると今度は $i+1$ 番目の色とのかぶりを気にする必要があるが、3色以上（10000色）なので、常に両端のどちらでもない色に変更可能である。よって、$i$ 番目の色を変えたら、$i$ 番目と $i+1$ 番目の色のかぶりについてはチェックしなくてよい。
n = int(input())
aaa = list(map(int, input().split()))
prev = aaa[0]
ans = 0
for a in aaa[1:]:
if prev == a:
ans += 1
prev = 0
else:
prev = a
print(ans)
B - rng_10s
問題
- R店には、今日の朝、$A$ 個のジュースの在庫がある
- Sくんは毎日、昼にR店で $B$ 個のジュースを買う
- R店は毎晩、ジュースの在庫が $C$ 個以下だったら翌朝までに $D$ 個仕入れる
- Sくん以外にR店でジュースを買う人はいない
- Sくんが永遠に毎日ジュースを買うことが可能か、判定せよ
解法
Sくんはジュース会社と直接契約した方がいいと思う
まず自明なパターンとして、
- $A \lt B$ なら初日でアウト
- $B \gt D$ ならいつかはジリ貧になってアウト
- $B-1 \le C$ なら在庫不足になる前に必ず仕入れが発生するので可能
それ以外の場合を考える。小難しく書くと、
$A+Dk \mod{B} \gt C$ となる整数 $k$ が存在すればアウト、しなければ可能となる。
左項は、Sくんがジュースを買った後の在庫としてあり得る数。$B$ で割った余りなので当然 $B$ 未満。このままでは翌日に買えなくなるので仕入れる必要があるが、$C$ より大きいと仕入れが発生しないのでアウト、ということ。
$B,D$ の最大公約数が $G$ なら、$Dk \mod{B}$ は $0, G, 2G, \ldots, B-G$ の値を取る。よって、$B-G \le C$ なら、可能である可能性がある。
その場合、可能かどうかは、初期値 $A$ のオフセットによって決まる。
例えば $A=9, G=5$ の時、$A+Dk \mod{B}$ の取る値は $4, 9, 14, \ldots$ となる。いわば、$0, G, 2G, \ldots$ から、$A \mod{G} = 4$ 個の「下駄を履かされた」状態となり、その分だけ $C$ の条件が厳しくなる。
よって、$B-G+(A\mod{G}) \le C$ なら可能、そうで無ければアウトとなる。
ちなみにAtCoderではPython3.4のため、gcd()関数はmathでなくfractionsモジュールに存在する。
import fractions
def solve(a, b, c, d):
if a < b or d < b:
return False
if b <= c + 1:
return True
gcd_bd = fractions.gcd(b, d)
cc = c - a % gcd_bd
b //= gcd_bd
cc //= gcd_bd
if b <= cc + 1:
return True
return False
t = int(input())
buf = []
for _ in range(t):
a, b, c, d = map(int, input().split())
buf.append('Yes' if solve(a, b, c, d) else 'No')
print('\n'.join(map(str, buf)))
C - String Coloring
問題
- 長さ $2N$ の英小文字からなる文字列 $S$
- $N$ 文字を赤、残りを青に塗る
- 赤文字を左から右に読んだ文字列と、青文字を右から左に読んだ文字列が一致するような塗り分け方は何通りか
- $N \le 18$
解法
競技プログラミング的には、制約から解法を推測する問題。えーん知らねーよそんなん。
文字列 $S$ の左半分を $S_L$、右半分を $S_R$ とする。また、ある塗り分け方で赤文字を左から右に読んだ文字列を $T_A$、青文字を右から左に読んだ文字列を $T_B$ とする。
S: abcdefggfedcba
SL ｜ SR
------------->
TA: a c f g ed b
b de g f c a :TB
<-------------
また、$S_L$ から赤に塗った文字を $T_{AL}$、$S_R$ から赤に塗った文字を $T_{AR}$ とする。
TAL: a c f TAR: g ed b TBL: b de g TBR: f c a
仮に $T_{AL}$ が $K$ 文字だったら、$T_{AR}$ は当然 $N-K$ 文字。青はその逆で、$T_{BL}$ が $N-K$ 文字、$T_{BR}$ が $K$ 文字。
条件を満たすように塗るには「$T_{AL}$ と $T_{BR}$」「$T_{AR}$ と $T_{BL}$」がそれぞれ一致しなければならないことがわかる。
よって、$S_L$ を $T_{AL}$ と $T_{BL}$ に分解する全 $2^N$ 通りを試し、そのペアが $S_R$ を $T_{BR}$ と $T_{AR}$ に分解する全 $2^N$ 通りと一致する個数を求めればよい。
実際には、赤青反転させたパターンは同じ個数なので、$2^(N-1)$ 通りでよい。
from collections import defaultdict
from itertools import combinations
def get_pair(s, cmb):
g, h = 0, 0
for i in range(n):
if i in cmb:
g <<= 5
g += s[i]
else:
h <<= 5
h += s[i]
return g, h
def patterns(k, d, e):
ret = 0
f = defaultdict(int)
for cmb in combinations(range(n), k):
f[get_pair(d, cmb)] += 1
for cmb in combinations(range(n), k):
ret += f[get_pair(e, cmb)]
return ret
def solve(n, b):
d = b[:n]
e = b[2 * n - 1:n - 1:-1]
ans = 0
if n % 2 == 0:
for k in range(n // 2):
ans += 2 * patterns(k, d, e)
ans += patterns(n // 2, d, e)
else:
for k in range(n // 2 + 1):
ans += 2 * patterns(k, d, e)
return ans
n = int(input())
s = input()
a = ord('a') - 1
b = [ord(c) - a for c in s]
print(solve(n, b))
D - Histogram Coloring
問題
解法
E - Synchronized Subsequence
問題
- $N$ 個の'a'と $N$ 個の'b'から成る長さ $2N$ の文字列 $S$
- この内いくつかの文字を（順番は崩さず）取り出し部分文字列を作る
- ('a'の中で数えて) $i$ 番目の'a'を取り出す場合、('b'の中で数えて) $i$ 番目の'b'も同時に取り出さなければならない
- 逆もしかり
- 取り出せる辞書順最大の文字列は何か
例
S aabbbbabaa
a 12 3 45
b 1234 5
a b b ab a → ○（各1,3,5番目を取り出す）
b bba a → ×（1番目のbを取り出してるのに1番目のaを取り出してない）
解法
同時に取り出さなければならない'a'と'b'のペアをabペアと呼ぶことにする。
なるべく、$S$ の中で'b'の方が'a'より先に出てくるペアを取り出したいように思う。が、これが考え始めるとなかなかどういう方針で取り出せばよいか決めづらい。以下、解答の丸写しとなるが、これを自力で組み立てるのはちょっと難しい。
ひとまず、先頭から数えて「今まで出てきた'a'と'b'が同数」となる箇所が存在すれば、そこで区切って個別に考えられる。区切ったグループ毎に辞書順最大となる文字列を求めて、最後にいい具合に選んで結合すればよい。区切り位置は、'a'を-1、'b'を1で置き換えて、先頭から累積和を取れば'0'になる位置である。
aabb|bbabaa|ab|ba
すると一つのグループの中では、「どのabペアも'a'より'b'が先に来る」か「どのabペアも'b'より'a'が先に来る」のいずれかとなっている。（この2つの状態を切り替えるには、間に必ず'a'と'b'が同数となる＝グループが区切られる箇所が存在する）
aが先パターン
aの次には、そのaのペアとなるbが来るのが絶対にいい。他に来られるとしたら別のペアのaしか無いが、「aa…」より「ab…」の方が辞書順は必ず後になる。
また、なるべく長い方がいい。「ab」より「abab」の方が後になる。
よって、「先頭のa」→「ペアとなるb」→「そのb以降に始めて出てくるa」→「ペアとなるb」→…を繰り返すと、グループの解が得られる。
bが先パターン
どのペア $i=1,2,3,\ldots$ を取り出すかは「ある $i$ を採用すると決めたら、それより後のペアは全て採用する」のがいいらしい。
最初に採用する'b'を決めて、それに対応する'a'が出てくるまでは、間にあるのは全て'b'となる。この'b'の連続が長ければ長いほど辞書順が後になるので、間の'b'は残すべきである。
b1 b2 b3 ... bk a1 ... a2 a3 ... ~~~~~~~~~~~~ これらを消すメリットは無い
また、それによって残すことになった最後の $b_k$ に対応する $a_k$ が出てくる前に、他の'b'があるのであれば、それも'a'の前に持ってきた方が辞書順が後になる。
これを繰り返すと、結局最初に採用する'b'以降、全てのペアは残した方がよくなる。
辞書順を最大にするためには「最初の'b'の連続を一番長くできる $i$ は何か」というのが重要で、もちろん、連続数が同じ場合は以降の並びも含めて最も辞書順を後にできる $i$ を探さなければならないので、単純に $i$ について全探索すればよい。
結合
このように求めた各グループの結果から、いい感じに選んで結合する。
「bが先グループ」より前に「aが先グループ」が来るメリットは無い。まず「bが先グループ」のみで結合する。
「bが先グループ」を後ろから試していって、「現在の暫定文字列」より「現在チェック中のグループの結果＋暫定文字列」の方が辞書順が後になれば、暫定文字列を更新する。
「bが先グループ」を全て繋げたら、その後に出てくる「aが先グループ」の結果を繋げられるだけ繋げたのが、答えとなる。
from itertools import accumulate
def search_ab(sss, cursor):
# print('a', cursor)
ai = aaa.index(cursor)
tmp_cur = bbb[ai]
max_cur = sss.index(0, cursor)
repeat = 1
while tmp_cur < max_cur:
cur = s.find('a', tmp_cur, max_cur)
if cur == -1:
break
ai = aaa.index(cur, ai)
tmp_cur = bbb[ai]
repeat += 1
return repeat, max_cur + 1
def search_ba(sss, cursor):
# print('b', cursor)
first_bi = bbb.index(cursor)
max_cursor = sss.index(0, cursor)
last_bi = aaa.index(max_cursor)
tmp_buf = [''] * (last_bi - first_bi + 1) * 2
tmp_max = ''
for i in range(last_bi, first_bi - 1, -1):
tmp_buf[aaa[i] - cursor] = 'a'
tmp_buf[bbb[i] - cursor] = 'b'
tmp = ''.join(tmp_buf)
if tmp > tmp_max:
tmp_max = tmp
return tmp_max, max_cursor + 1
def integrate(parts_b):
tmp_max = ''
for pb in reversed(parts_b):
tmp = pb + tmp_max
if tmp > tmp_max:
tmp_max = tmp
return tmp_max
n = int(input())
s = input()
n2 = n * 2
sss = []
aaa, bbb = [], []
for i, c in enumerate(s):
if c == 'a':
aaa.append(i)
sss.append(-1)
else:
bbb.append(i)
sss.append(1)
sss = list(accumulate(sss))
repeats_a = []
parts_b = []
last_b_cur = 0
cursor = 0
while cursor < n2:
c = sss[cursor]
if c < 0:
repeat, cursor = search_ab(sss, cursor)
repeats_a.append((cursor, repeat))
else:
tmp, cursor = search_ba(sss, cursor)
parts_b.append(tmp)
last_b_cur = cursor
print(integrate(parts_b) + 'ab' * sum(r for c, r in repeats_a if c > last_b_cur))
