目次
AtCoder Grand Contest 040 A～C 問題メモ
深夜開催で参加者数が少なくなるかと思いきや、そこまででもなかった。みんなげんき。
A - ><
問題
- '<' と '>' からなる長さ $N-1$ の文字列 $S$ がある
- ここから、以下の条件を満たすように非負整数の数列 $a = \{ a_1,a_2,...,a_N \}$ を作る
- $S_i$ が '>' の時、$a_i \gt a_{i+1}$
- $S_i$ が '<' の時、$a_i \lt a_{i+1}$
- 数列 $a$ の総和として考えられる最小値を求めよ
解法
問題タイトルがふぇぇんって顔文字に見える。
答えを代入する長さ $N$ の配列を用意しておく。
< > > > < < > < < < < < > > > < 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
先頭から見ていって、'>' から '<' に切り替わったところ（または先頭）を0とし、'<' が続く限り1ずつ増やしていく。
< > > > < < > < < < < < > > > < 0 1 0 0 0 1 2 0 1 2 3 4 5 0 0 0 1
末尾から見ていって、'<' から '>' に切り替わったところを0とし、'>' が続く限り1ずつ増やしていく。ただし先ほど埋めた数字とのMAXを取る。
< > > > < < > < < < < < > > > < 0 3 2 1 0 1 2 0 1 2 3 4 5 2 1 0 1
これで最小となるので、合計したら答え。
s = input()
n = len(s) + 1
ans = [0] * n
tmp = 1
ens = list(enumerate(s))
for i, c in ens:
if c == '<':
ans[i + 1] = tmp
tmp += 1
else:
tmp = 1
tmp = 1
for i, c in reversed(ens):
if c == '>':
ans[i] = max(ans[i], tmp)
tmp += 1
else:
tmp = 1
print(sum(ans))
B - Two Contests
問題
- 「$L_i$ 以上 $R_i$ 以下」という範囲区間が $N$ 個ある
- 区間を2グループに分ける。いずれのグループにも最低1つは区間が含まれる
- 各グループで、グループに含まれる全ての区間の共通部分の長さを「グループの良さ」とする
- 上手くグループ分けして、2グループの良さの和を最大化せよ
- $2 \le N \le 10^5$
- $1 \le L_i \le R_i \le 10^9$
例
1 2 3 4 5 6 7 8 A |---------| B |----------| C |----------| D |----------|
AB,CDで分けると、ABの共通部分は2～4の長さ3、CDの共通部分は5～7の長さ3で、合わせて6。
A,BCDで分けると、Aの共通部分は1～4の長さ4、BCDの共通部分は5の長さ1で、合わせて5。
解法
貪欲に考えられる条件を見つけて境界を全探索。
1つのグループの共通部分の長さは「グループ内の最小 $R_i$ - 最大 $L_i$ + 1」で求められる。 （ただし0未満にはならない）
分け方は愚直には $2^N$ あるので何とかしてまとめたい。さらに、ある分け方のスコアを評価するのに最大・最小が必要なので、工夫しないとそれにも $O(N)$ かかる。
もし、区間を何らかの基準に従ってソートし、ある区切りを境に左と右でグループを分ける、という方法が最適であるならば、区切りを全探索しても $N-1$ 箇所。 さらにそれなら累積で最小・最大を管理してやれば前計算 $O(N \log{N})$、1回の評価を $O(1)$ で済ませられるので、間に合いそう。
この方法が妥当か検証する（してない）
左から順
上記のサンプルなどを見ていると、2グループに分ける場合、 あんまりバラバラな区間を同じグループに入れても、共通部分がむやみに短くなって損な気がする。
なので、$(L_i,R_i)$ を小さい順にソートし、どこかで左右に分ける方法が考えつく。
それぞれのグループの最大 $L_i$、最小 $R_i$ は、左右から累積Max,Minを取っておくことで取得できる。
1 2 3 4 5 6 7 8 0 |---------------| 1 |----------| 2 |-------------| 3 |-------| i 0 1 2 3 左からの累積 右からの累積 Li 1 2 4 5 Max 1 2 4 5 Max 5 5 5 5 Ri 6 5 8 7 Min 6 5 5 5 Min 5 5 7 7
$i$ 番目の区間を右グループの開始点とする場合、
- 左グループ共通部分: 左累積Min $R[i-1]$ - 左累積Max $L[i-1]$
- 右グループ共通部分: 右累積Min $R[i]$ - 右累積Max $L[i]$
として、配列アクセスだけで計算できる。
最も長い区間のみ単独グループ
区間がまったくバラバラで、ろくに共通部分を持たない場合であっても、 最低保証として「どれか1つを1グループとし、残りは別グループとする」という方法を採れば、 最初のグループは必ずその区間の長さ分の得点が得られる。
その場合、明らかに最も長い区間を1グループとした方がよい。
上記の「左から順」では補足できないので、これを別に計算する。
（最も長い区間が複数ある場合が不安だったり、似たような処理を書くのを省略するため、 下記コードでは区間の長さ順にソートした上で区切りを全探索するコードを再利用しているが、 実際はチェックするのは最も長い任意の1区間を1グループとする場合のみでよい）
ちゃんとした証明
- アルメリアさんの記事
「ソートして左右に分けるのが最適」であることを検証するにあたり、 「ソートした結果、全体の中で最も右の区間が含まれる方をグループ2とした時、グループ1に含まれる最も右の区間」を固定することで、 それぞれのグループ内最大 $L_i$ が固定されるため、見えやすくなる。
さらに、ソートして分ける方法と、最も長い区間を単独グループにする方法の2つで、本当に網羅できているのかも理解できる。
import sys
from itertools import accumulate
def calc(tasks):
tasks_l, tasks_r = zip(*tasks)
tasks_l_acc_fwd = list(accumulate(tasks_l, func=max))
tasks_l_acc_bwd = list(reversed(list(accumulate(reversed(tasks_l), func=max))))
tasks_r_acc_fwd = list(accumulate(tasks_r, func=min))
tasks_r_acc_bwd = list(reversed(list(accumulate(reversed(tasks_r), func=min))))
score = 0
for i in range(1, n):
left_max_l = tasks_l_acc_fwd[i - 1]
left_min_r = tasks_r_acc_fwd[i - 1]
right_max_l = tasks_l_acc_bwd[i]
right_min_r = tasks_r_acc_bwd[i]
tmp_score = max(0, left_min_r - left_max_l + 1) + max(0, right_min_r - right_max_l + 1)
score = max(score, tmp_score)
return score
n = int(input())
tasks = []
for line in sys.stdin:
l, r = list(map(int, line.split()))
tasks.append((l, r))
tasks.sort()
ans1 = calc(tasks)
tasks.sort(key=lambda lr: (lr[1] - lr[0], lr[0], lr[1]))
ans2 = calc(tasks)
print(max(ans1, ans2))
C - Neither AB nor BA
問題
- 偶数 $N$ が与えられる
- 以下の条件を満たす、'A','B','C' からなる長さ $N$ の文字列 $S$ を考える
- 隣り合った2文字を削除することを繰り返して、$S$ を空文字列にすることが可能
- ただし、'AB' と 'BA' は削除禁止
- 条件を満たすものがいくつあるか、$\mod{998244353}$ で求めよ
- $2 \le N \le 10^7$
- 制限時間 4秒
例
AABBCC → AABB → AA → '' OK! AACBAB → CBAB → AB 失敗! (どうやってもできない)
解法
タネが分かれば実装は頻出のMOD計算をするだけ。タネに気付くか勝負。
実験
まず、試してみると普通のランダム文字列ならだいたい成功してしまうので、無理な例を考えてみる。 あからさまに無理な例として、ABABABAB… や BABABABA… が挙げられる。
この1つをCに変えてみても、ABABCBAB → ABABAB となり、すぐに手詰まりになる。 2つ、3つと増やしても無理だが、4つ変えると成功できる（ABCCACCB → ACACCB → ACCB → CB など）。 $N=8$ なので、半分、というところが怪しそう。
一方、途中でABの連続をずらした ABAABABA みたいなのは、→ ABBABA → AABA → BA となり、失敗は失敗なのだが、結構いいところまでいく。
法則探し
文字列中のABAB…が連続する箇所を考えると、この部分はどの2文字も一気には削除できず、両端から1文字ずつ削っていくしかない。 この“岩盤”を削る作業に必要となる“爆薬”が、'A'なら'A,C'、'B'なら'B,C'であり、削除時に隣接してもらわないといけない。
そういうわけで、岩盤1文字の削りに爆薬1文字必要なので、1箇所の岩盤を削除するには、その長さと同数の爆薬が最低限必要である。
ただし、ABA|ABABAのように、AとBを組み替えた岩盤はもう一方にとっての爆薬になり得る。
しかし、ABABCBAB → ABABAB のように、初期状態では離れていても「$S$ の先頭から数えて奇数番目がA, 偶数番目がB」が一致している2つの岩盤は、中間を削るとくっついてしまう。 このようにA,Bのindexの偶奇が一致している複数の岩盤は、まとめて大きな1つの岩盤として扱える。
それ以外の文字で爆薬が、岩盤の長さと同数必要。 爆薬は、indexが奇数番目（Bと組になるもの）ならA以外、偶数番目（Aと組になるもの）ならB以外なら何でもよいので、1箇所につき2通りずつの選択肢がある。 （奇数番目がAの岩盤の場合）
常にindexの偶奇は不変なので、奇数番目がAの岩盤を考えている間、ある瞬間に岩盤の'A'と隣接して使えるはずだった爆薬の'A'が、操作手順によって岩盤に変化したり、岩盤の'B'と隣接して使えなくなる、ということは無い。
数え挙げ
まず $N$ 文字の ABABAB…（またはBABABA…）をベースとして、そこからいくつかの文字を爆薬に置き換える時、 「$\frac{N}{2}$ 個未満の文字しか置き換えていない文字列」は、不可能とわかる。
逆に、$\frac{N}{2}$ 個以上爆薬があれば、どこにあろうと最終的には岩盤に隣接できるので、達成可能である。
半数未満しか置き換えないので、ABAB…をベースとしたものと、BABA…をベースとしたものが、重複して数えられることは無い。 また、同じ理由から、爆薬の並びの方が実質的な岩盤となって最後まで残ってしまう、ということも無い。
何個爆薬を仕込むか $i(0 \le i \lt \frac{N}{2})$ のそれぞれに対し、以下を掛け合わせたパターンが不可能である。
- 岩盤の種類(ABAB…, BABA…) 2通り
- 設置箇所の選び方 ${}_N C_i$ 通り
- 爆薬として設置（変更）する文字 $2^i$ 通り
この総和を、全体のパターン数 $3^N$ から引けばよい。$O(N)$ にもかかわらず $N \le 10^7$ でちょっとビビるが、計算は単純なのでPyPyを使えば問題なく通る。
def prepare(n, MOD):
f = 1
for m in range(1, n + 1):
f *= m
f %= MOD
fn = f
inv = pow(f, MOD - 2, MOD)
invs = [1] * (n + 1)
invs[n] = inv
for m in range(n, 1, -1):
inv *= m
inv %= MOD
invs[m - 1] = inv
return fn, invs
n = int(input())
MOD = 998244353
fn, invs = prepare(n, MOD)
ans = pow(3, n, MOD)
impossible = 0
mul = 2
for i in range(n // 2):
tmp = fn * invs[i] * invs[n - i] % MOD * mul
impossible = (impossible + tmp) % MOD
mul = mul * 2 % MOD
print((ans - impossible) % MOD)
