目次
AtCoder Grand Contest 048 A,B,C問題メモ
A - atcoder < S
解法
まず、$S$ を与えられたままで比較して 'atcoder' より大きければ0回。
また、($S$ から作れる辞書順最大の文字列) $\le$ 'atcoder' なら不可能だが、これは少し考えると 'a' のみからなる文字列が必要十分条件であるとわかる。
それ以外を考える。ここまでに当てはまらない $S$ は、以下を共に満たす。
- $S$ は2文字以上
- 1文字目は
'a' - 2文字目は
't' 以下
目指す最終形は、以下のいずれかである。
- 最終形①: 1文字目が
'b' 以上 - 最終形②: 1文字目が
'a' で、2文字目が'u' 以上
他にも「1,2文字目が 'at' で3文字目が 'd' 以上」なども条件を満たすが、最小操作回数を求める上では、上記のみ考えればよい。
何故かというと、仮に 'a' 以外の文字がはじめて出てきたのが $i$ 文字目とすると、（最小かどうかはともかく）以下のいずれかで達成できる。
- $a \lt S_i \le t$ のとき、$S_i$ を1文字目に持ってくることで $i-1$（最終形①）
- $S_i \gt t$ のとき、$S_i$ を2文字目に持ってくることで $i-2$（最終形②）
最終形を 'at + d以上' という形にすることでこれより小さくできるか、という点だが、
必要回数 a[u-z]... 0 [u-z]はu～zのいずれかの1文字を示す a[b-t]... 1 aa[u-z]... 1 aa[b-t]... 2
$S$ の先頭からの文字を分類して必要操作回数を調べていくと最初の方は上記のようになる。
これらの最終形はいずれも先ほどの2つに当てはまっている。
ここまでに当てはまらない $S$ は先頭から3文字が全て 'a' ということになる。
最終形を 'at + d以上' とするには、少なくとも 't' を2文字目まで運んで、さらに 'd' 以上の文字を3文字目まで運ぶ必要がある。
しかし、't' を2文字目まで運んだ段階であと1回、1,2文字目を入れ替えれば最終形①となり目的は達成される。
一方、'd' を3文字目に運ぶためには、少なくとも1回以上の操作を必ず要する。
最終形を 'at + d以上' とすることによって①や②よりも操作回数を少なくできることはない。
これは、'atc + p以上' など 'atcoder' と共通するprefixを増やしても、むしろ悪化する一方である。
よって、最終形は前述の2パターンのみ考えればよく、'a' 以外の文字がはじめて出てくる位置とそれが 't' より大きいかどうかで $O(|S|)$ で求められる。
この判定・最小回数の求め方は 'atcoder' の最初の文字が辞書順最小の 'a' であること、また2文字目が 't' $\gt$ 'a' で、ひっくり返せば大きくできることが条件として便利なので、それによって条件分岐を幾分か減らせている。
もし 'zyxcoder' など、それに当てはまらないのが比較対象であったら、もう少し最小回数を求めるのは複雑になる。
その場合、比較対象がせいぜい8文字なので、目標とする文字列を総当たりして、各目標とするのににかかる最小回数を求めるのが楽か。
B - Bracket Score
解法
丸括弧、角括弧にするindexは、ある条件を満たして選べば、開き括弧と閉じ括弧の具体的な配置は考えなくてもよい。
つまり、「丸括弧は1,2,5,8番目に配置する」と決めてしまえば、具体的な「'('は1,2に、')'は5,8に配置する」というのを矛盾無く当てはめられる方法が必ずある。
その条件とは、「奇数と偶数が同数」ということになる。
- ある括弧ペアの中身は、良い括弧列でなければいけない
- →中身の長さは偶数
- →それを包む開き括弧と閉じ括弧のindexの偶奇は異なる
これで必要条件は示せたが、十分条件は本番では多分いけるやろで通してしまった。
公式解説によると、以下の繰り返して構築できるので証明できる。
'(',')'を配置するindexを昇順に並べると、偶奇同数なので、偶数と奇数が隣接する箇所が必ず存在する- その間は
'[',']' だけからなり、長さ偶数なので、'[][][]…' で埋められる - 良い括弧列の中で、一部分が良い括弧列
'([][][]…)' を形成していれば、それを除いたものも良い括弧列
答えを求めにかかる。まず各 $i$ について以下を計算する。
- 貪欲に $A_i,B_i$ の大きい方を取り、答えに加算する
- $A_i$ を採用した奇数番目と偶数番目の個数の差 $balance$ を計算しておく
- $A_i$ と $B_i$ を入れ替えたときに減らさなければいけないスコアを、$balance$ を減らすとき $dec$、増やすとき $inc$ 別に配列に溜めておく
最後に、$balance$ が0より多いならその分 $dec$ から、少ないなら $inc$ から小さい順に取り出して貪欲な答えから減算すればよい。
import sys
n = int(sys.stdin.buffer.readline())
aaa = list(map(int, sys.stdin.buffer.readline().split()))
bbb = list(map(int, sys.stdin.buffer.readline().split()))
ans = 0
balance = 0
inc = []
dec = []
for i in range(n):
a = aaa[i]
b = bbb[i]
if i % 2 == 0:
if a >= b:
ans += a
balance += 1
dec.append(a - b)
else:
ans += b
inc.append(b - a)
else:
if a >= b:
ans += a
balance -= 1
inc.append(a - b)
else:
ans += b
dec.append(b - a)
if balance > 0:
dec.sort()
ans -= sum(dec[:balance])
elif balance < 0:
inc.sort()
ans -= sum(inc[:-balance])
print(ans)
C - Penguin Skating
解法
腹ばいで滑るペンギンって、あんまりスムーズに滑れるわけでもなく思ったより必死で足じたばたしてる。
閑話休題。
ペンギンの動きを試すと、マスの端っこはともかく、中途半端な位置に止まろうと思ったら初期位置で壁となるペンギンがいてくれないといけないことがわかる。
↓このペンギンを目標位置に持っていく
🐧 🐧 🐧 🐧
初期位置 3 7 10 13
目標位置 10
↓壁
🐧 🐧 🐧 🐧
10 11 12 13
ただし、間に何匹のペンギンが挟まることになるかによって、壁となるペンギンがいてほしい位置は異なる。
上記では、間に2匹のペンギンが挟まることで初期位置13のペンギンが壁となるが、これが3匹なら14だし、10匹なら21となる。
これでは、壁となるペンギンが存在するかどうか、そしてどこに存在するか、検索しにくい。
しかし、indexが1つ進むたびに壁に求められる初期位置も1つ増えるので、あらかじめ初期位置からindexを引いておけば、壁が存在するかを固定値で検索できるようになる。
🐧 🐧 🐧 🐧 index 1 2 3 4 初期位置 3 7 10 13 初期位置' 2 5 7 9 目標位置 10 目標位置' 9 初期位置' の中から、ペンギン1の目標位置' である9を探す →index=4に存在 →ペンギン1は、ペンギン4が壁となることで目標位置10に止まることが可能である
この検索部分は、問題の制約から初期位置'の配列が必ず昇順であるので、二分探索で検索できる。
また便宜上、位置 $0$ と $L+1$ にもペンギンがいることにしておくと、マスの端っこの処理を分離しないで統一的に判定できる。
全てのペンギンについて、初期位置から動かなくてよいか、壁となるペンギンがいてくれれば、可能である。
例では、初期位置から右に動くパターンで説明したが、左に動くパターンでも同様のことが言える。
これで判定はできた。
後は移動回数を求めたい。
「他のペンギンの土台となるために1回以上移動した後、さらに自分の目標位置に移動する」ペンギンも存在することに留意して数える必要がある。
A B C D E
🐧 🐧 🐧 🐧 🐧
初期位置 3 7 10 13 20
目標位置 10 11 18
↓
🐧 🐧 🐧 🐧 🐧 まずペンギンAの土台となるため、Cは1回移動
10 11 12 13 20
↓
🐧 🐧 🐧 🐧 🐧 その後、Cは自分の目標位置にいくため1回移動
10 11 18 19 20
全てのペンギンは各自どちらか一方にのみ動き、「左に動いた後、右に動く」ようなことはしなくてよい。
2回以上動くペンギン $P_i$ の移動は、最後の1回を除き他のペンギン $P_j$ が目標位置に止まるための土台となるための移動である。
その時点で、たとえば右に動いたなら、もう $P_j$ によって左は詰まってしまうので移動できない。
制約からも、$P_i$ の目標位置は $P_j$ のために土台となった位置より右（その位置を含む）であり、左に動く必要は生じない。
よって、初期位置と目標位置が同じペンギンは動かす必要は無いし、
異なるペンギンは「初期位置より目標位置が左なら左にのみ動く」「右なら右にのみ動く」ので、それぞれ独立に移動回数を求めればよい。
以下は、右に動く場合を想定する。
基本的に、計算中のペンギンを $i$、その壁となるペンギンを $j$ としたとき、土台を含めて $j-i$ 匹のペンギンの移動が必要となる。
その後、土台となったペンギン（上例でAにとってのB,C）は改めて自身の移動を行うが、もし土台となった位置が自身の最終位置である（B）なら、それ以上動く必要は無い。
なので、左から各ペンギンの必要回数を求めていく過程で、「現在、壁となった最も右のペンギン」を更新していく。
直前のペンギンと壁を共有しているなら、直前のペンギンの土台となったときに自身の移動も完了しているので何もしなくてよい。
共有しないなら、改めて自身のための移動を（土台が必要なら、土台の移動を含め）行う必要がある。
初期位置から左に動くペンギンも逆から同様に計算すればよい。
または、右に動くペンギンと同じく左から順に見ていっても計算できる。
その場合、直前のペンギンと壁を共有していても、直前のペンギンの移動回数に自身の移動は勘案されていない（土台分だけ、既に勘案されていると考えればよい）。
自身の移動分だけ+1する必要がある。
from bisect import bisect_left, bisect_right
def solve(n, l, aaa, bbb):
ccc = [1] + [a - i for i, a in enumerate(aaa)] + [l - n + 1]
ddd = [1] + [b - i for i, b in enumerate(bbb)] + [l - n + 1]
ans = 0
left_last = 1
right_last = l - n + 1
for i in range(1, n + 1):
c = ccc[i]
d = ddd[i]
if c == d:
continue
if c > d:
j = bisect_right(ccc, d) - 1
if ccc[j] != d:
return -1
if left_last == d:
ans += 1
else:
ans += i - j
left_last = d
else:
j = bisect_left(ccc, d)
if ccc[j] != d:
return -1
if right_last == d:
pass
else:
ans += j - i
right_last = d
return ans
n, l = map(int, input().split())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
print(solve(n, l, aaa, bbb))
D - Pocky Game
問題
例
解法
