目次
AtCoder Grand Contest 039 A～C問題メモ
A - Connection and Disconnection
問題
- 文字列 $S$ が与えられる
- $S$ を $K$ 回繰り返してできる文字列を $T$ とする
- $T$ の文字をひとつ選んで他の文字に書き換える操作を繰り返すことで、$T$ のどの隣り合う2文字も相異なるようにする
- 必要な操作の回数の最小値を求めよ
- $1 \le |S| \le 100$
- $1 \le K \le 10^9$
解法
$K$ がでかすぎて $T$ を実際に構築できないので、$S$ だけで考える。ランレングス圧縮して、同じ文字の連続個数に置き換える。
aaabbbbccdaaa → 3 4 2 1 3
それぞれの連続について、連続数/2（切り捨て）文字を変更すればよい。これの $K$ 倍が、基本的には答えとなる。
axabxbxcxdaxa ← 1 2 1 0 1 ~ ~ ~ ~ ~
結合箇所
$S$ の先頭と末尾の文字が同じ場合、結合時に新たな連続ができてしまう。
aaabbbbccdaaa aaabbbbccdaaa
~~~~~~~
$S$ が全て同じ文字の場合
$|S| \times K/2$ が答え。
そうで無い場合
場合分けして考えると、実際に結合によって操作回数が変わるのは、先頭も末尾も連続数が奇数個の場合のみであるとわかる。
___
axabxbxcxdaxa axabxbxcxdaxa
↓
axabxbxcxdaxa xaxbxbxcxdaxa
この場合、操作を1増やす必要がある。他の場合は、適当に変更箇所をずらすことで同じ文字が隣接しないようにできる。
結合箇所は $K-1$ 個あるので、答えに $K-1$ を加える。
Pythonでのランレングス圧縮
知らなかったけど itertools.groupby() はgroupbyという名前でありながらやってることはランレングス圧縮っぽいことらしい。
（そのため本来のgroupbyとして使うためには事前に同じキーでのソートが必要とされている）
「(要素, その要素が連続する限りのiterator) というtuple」のiteratorが返るので（ややこしい）、適宜list化して長さを得る。
s = aaabbbbccdaaa rle = [len(list(g)) for c, g in groupby(s)] # => [3 4 2 1 3]
from itertools import groupby
def solve(s, k):
rle = [len(list(g)) for c, g in groupby(s)]
if len(rle) == 1:
return len(s) * k // 2
ans = sum(l // 2 for l in rle) * k
if s[0] == s[-1] and rle[0] % 2 == 1 and rle[-1] % 2 == 1:
ans += k - 1
return ans
s = input()
k = int(input())
print(solve(s, k))
B - Graph Partition
問題
- $N$ 頂点 $M$ 辺の連結無向グラフが与えられる
- 辺の情報は $S_{1,1} ... S_{N,N}$ を用いて表され、$S_{i,j}$ が 1 なら頂点 $i,j$ を結ぶ辺が存在し、0なら存在しない
- 以下の条件を満たす $k$ が存在するか判定し、存在する場合は最大値を求めよ
- 頂点全体を空でない $k$ 個の集合 $V_1,...,V_k$ に分解する
- その時、全ての辺は、番号が隣り合う集合どうしを結ぶ
- $1 \le N \le 200$
例
,------------------, 0 -- 1 -- 2 -- 3 4 5 `------------' / `----------------' ↓ | | | 4 -|- 0 -|- 1 -|- 2 | \ | `|' | `|- 3 '|` 5 4グループに分けることが可能
解法
二部グラフ＋αと気付くのに時間かかった。
答えとなるグループ分けがあったとして、奇数グループ、偶数グループ同士をまとめると二部グラフになっている必要がある。
4 | 0 1 | 2 3 | 5
二部グラフは、適当な頂点から隣り合う頂点を白、黒と互い違いに塗っていって、矛盾しないかで判定できる。これができなければ不可能。
できるなら、最悪その2グループで成立しているので、とりあえず可能であることは分かる。
あとはどれだけのグループに展開できるかだが、これはグラフの直径 $d$ を求めればよい。
「最短経路が最も長い2頂点」を $p,q$ として、$V_1$ を $\{p\}$ とする。$p$ から出発して、
- 最短経路が1の集合を $V_2$
- 最短経路が2の集合を $V_3$
- …
としていくと、$q$ は $V_{d+1}$ となり、$d+1$ グループは作ることが可能である。逆にそれ以上は作れない。
グラフの直径は、木ならば2回BFSをすれば求まるが、木で無い場合、全点間最短距離を計算する必要がある。
from collections import deque
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
def bfs(links):
color = [-1] * n
q = deque([(0, 0)])
while q:
v, c = q.popleft()
if color[v] != -1:
if color[v] != c:
return False
continue
else:
color[v] = c
new_c = c ^ 1
for u in links[v]:
if color[u] != -1:
if color[u] != new_c:
return False
continue
q.append((u, new_c))
return True
def solve(n, links, matrix):
res = bfs(links)
if res == -1:
return -1
g = csgraph_from_dense(matrix)
f = floyd_warshall(g)
return int(f.max()) + 1
n = int(input())
links = [set() for _ in range(n)]
matrix = []
for i in range(n):
s = input().strip()
for j, c in enumerate(s):
if c == '0':
continue
links[i].add(j)
matrix.append(list(map(int, s)))
print(solve(n, links, matrix))
C - Division by Two with Something
問題
- 整数 $N$ が与えられる
- ある整数 $k$ に対し、$f(k)$ を以下のように定める
- $k$ が奇数なら1を引いて2で割る、偶数なら2で割って $2^{N-1}$ を足す、という操作を1回とする
- $f(k)=$「$k$ から操作を繰り返して、元の $k$ にもどるまでの操作回数、ただし戻らない場合は0」
- 2進数表記で $N$ 桁以下の整数 $X$ が与えられる
- 0以上 $X$ 以下のすべての整数 $k$ に対し、$f(k)$ の総和を $\mod{998244353}$ で求めよ
- $1 \le N \le 2 \times 10^5$
例
N=3 X=100
000 → 100 → 110 → 111 → 011 → 001 → 000 6回
001 → 000 → 100 → 110 → 111 → 011 → 001 6回
010 → 101 → 010 2回
011 → 001 → 000 → 100 → 110 → 111 → 011 6回
100 → 110 → 111 → 011 → 001 → 000 → 100 6回
~~26回~~
解法
操作は、わかりやすく書くと、$k$ を $N$ 桁の2進数で表記して「1の位を反転したものを最上位にくっつけて、右に1つビットシフトする」ことに相当する。
10110 → 末尾が0なので、先頭に1をくっつけてシフト → 11011 → 末尾が1なので、先頭に0をくっつけてシフト → 01101 → 00110 → ...
さらに言い換えると、$k$ の前に $k$ をビット反転させたものをくっつけて、枠を1つずつずらしていった結果に相当する。
10110|01001|10110
~~~~~ 10110
~~~~~~ 11011
~~~~~~ 01101
なので、どんな数であろうと、$2N$ 回シフトすれば元に戻る。戻らない数は無い。そして、大半の数はこの $2N$ 回のシフトが必要である。
例外的に、$2N$ 回より前に上手い具合に元の数と同じものが途中で出現する場合があり、そういったものの周期と個数を数えられればよい。
途中出現ケース
どんなケースで途中出現するかについて、とりあえず $N$ や $X$ は無視して一例作ってみる。ビット反転したものとしてないものを同時に考える。
反転 元
01001 ... 10110... 最初、適当に並べる
^ 反転側の次から、元の整数と同じ並びが出現すると仮定する
0100110110... 1011001001... 反転側を、元に従って延長する
^ またさらにそれに従って元を延長する
010011011001001...101100100110110... 繰り返す
^
ここで互いへの反映を止めると、とりあえずこんなケースを作れる。
010011011001001 101100100110110
~~~~~~~~~~~~~~~~~~
これをよく見ると、“10110” とそのビット反転 “01001” をそれぞれ $A,B$ とすると $ABA$ という形になっている。 反転したものと合わせて $BABABA$ となるため、途中に“ABA”が出現することとなる。
逆に、元と反転で共通の箇所を持つならこうならざるを得ないことは、試しに作ってみた上記の例で先頭5文字を決めると連鎖的に全て決まってしまうことからも分かる。
これがたとえば $ABAB$ ではダメで、反転と合わせると $BABAABAB$ となりAが続いてしまう。
$ABABA$ ならよい。Aで始まりAで終わらないといけない。 つまり $N$ は $A$ の長さの奇数倍という関係になる。
途中出現ケースの数えあげ
“ABA”や“ABABA”というパターンを作るためには、$N$ が分割数（“ABA…BA”の文字列長をこう称することにする）で割り切れないと行けない。 分割数は奇数限定のため、$N$ の奇数の約数をまず列挙する。
各分割数につき、「$X$ 以下」という制約を考慮しながらその周期での繰り返しパターンの個数を数えたい。
分割数 $d$ とすると、$A$ の長さ $l=\frac{N}{d}$、シフト数は $2l$ となる。
$A$ が $X$ の先頭 $l$ 文字より小さければ、そこから生成される元の数字 ABAB…BA は $X$ より小さいので数え挙げてよい。 逆に大きければ、元の数字は $X$ より大きいため不適。
問題はちょうど同じ場合で、この場合は実際に（文字列のまま） ABAB…BA を作って、$X$ と比べてやる。比較に最悪 $O(N)$ かかるが、調べるべき分割数は多くないので大丈夫。
X = 10110 00111 01010
l = 5
Amax = 10110
↓
10110 01001 10110
これはXより大きいので、Aとして10110は取れない
Aは0～10101の各値を取ることになる
→10101は10進数で21のため、22パターンが存在する
重複して数え挙げないように注意する。たとえば以下の3つは同じ数である。
N = 30 d = 3 l = 10 0011001100 1100110011 0011001100 d = 5 l = 6 001100 110011 001100 110011 001100 d = 15 l = 2 00 11 00 11 00 11 00 11 00 11 00 11 00 11 00
分割数が大きいほどAの長さは短くなり、シフト数は少なくなる。
反転 元
011 100 011 100 011 100 011 100 011 100 分割数5 → Aの長さ3 → シフト数6
~~~~~~~~~~~~~~~~~~~~~~
01001 10110 01001 10110 01001 10110 分割数3 → Aの長さ5 → シフト数10
~~~~~~~~~~~~~~~~~~~~
よって、$d$ の大きい方から計算し、もし今計算中の $d$ が、過去に計算した $d_{checked}$ の約数であれば、既に数えられているのでそのパターン数を引く。
（サンプル3）
X = 001110011011011101010111011100
d = 15 ... 1パターン x シフト数 4 = 4
d = 5 ... (14 - 1)パターン x シフト数 12 = 156
d = 3 ... (231 - 1)パターン x シフト数 20 = 4600
計 244 パターン 4760 回
その他 ... (242079197(0～Xの個数) - 244) パターン x シフト数 60 = いっぱい
いっぱい + 4760 = 答え
def count_head(x, y, d, t, MOD):
p = x[:t]
q = y[:t]
k = int(p, base=2) % MOD
r = (p + q) * (d // 2) + p
if x >= r:
k += 1
return k
def solve(n, x):
MOD = 998244353
y = ''.join('1' if c == '0' else '0' for c in x)
divisors = []
for i in range(3, n + 1, 2):
if n % i == 0:
divisors.append(i)
divisors.reverse()
checked_divisors = {}
ans = 0
short = 0
for d in divisors:
t = n // d
k = count_head(x, y, d, t, MOD)
for pd, pk in checked_divisors.items():
if pd % d != 0:
continue
k -= pk
ans = (ans + 2 * t * k) % MOD
short += k
checked_divisors[d] = k
t = (int(x, base=2) + 1 - short) % MOD
ans = (ans + t * 2 * n) % MOD
return ans
n = int(input())
x = input()
print(solve(n, x))
