Codeforces Round #505 参加記録

Dashboard - Codeforces Round #505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final) - Codeforces

3完で541位。Div1+Div2混合回でこの順位なので、レートもそこそこ上がりました。

f:id:betrue12:20180820193230p:plain

BもCも解くのが遅めだったんですが、この回はとにかくプレテストが弱い問題が多くて…大量のシステス落ちが発生した結果、生き残った私の順位が上がった感じです。

3問振り返っていきます。

A. Doggo Recoloring

Problem - A - Codeforces

文字列 $s$ に以下の操作を任意回数行うことで、全部同じ文字にすることができますか、という問題。

文字列中に2つ以上存在する文字を選び、その文字を好きな文字に置き換える。

もし2つ以上存在する文字が1種類でもあれば、 aabc → bbbc → cccc のように、他の文字を全部拾っていくことができます。また、文字列が2文字以上で かつ全部の文字が異なる場合は、1度も操作を行えません。

文字列が1文字の時は何もしなくても条件を満たしているので、そこだけ注意です。

ACコード（Ruby）：Submission #41830470 - Codeforces

B. Weakened Common Divisor

Problem - B - Codeforces

$n$ 個の整数ペアのリスト $(a_{1}, b_{1}), ..., (a_{n}, b_{n})$ が与えられます。このペア全てに対して「 $a_{i}$ または $b_{i}$ は $p$ で割り切れる」を満たす2以上の整数 $p$ を、このペアリストのWCDと呼ぶことにします。与えられたペアリストのWCDを1つ示すか、WCDが存在しないことを判定しなさいという問題。

$n \le 10^{6}$ 、 $A = \max(a_{i}, b_{i})$ として $A \le 2 \times 10^{9}$ と制約がやや大きめです。WCDを1つだけ示せばいいので素数だけに絞っていいことは分かりますが、「全部の入力を素因数分解する（ $O(n\sqrt{A})$ ）」や「解になり得る全素数を試す（ $O(n\frac{A}{\log A})$ ）*1」などは間に合いません。

どれか1つのペア、例えば $(a_{1}, b_{1})$ に注目します。探す範囲を素数に絞ると、解の候補は $(a_{1}, b_{1})$ どちらかの素因数であるはずです。全部の入力を素因数分解するのは大変ですが、2つくらいなら $O(\sqrt{A})$ で余裕です。また、ここで得られる素因数は多くても15個くらいになります*2。

ここで得られた解の候補（高々15個）を、残りの入力ペアでひたすら試して、ふるい落としていけばよいです。 $15 \times 2 \times 10^{6}$ 回ほどの剰余算になりますが、これくらいなら間に合います。

ACコード（C++）：Submission #41899593 - Codeforces

本番コードもそんなに差はないんですが、素因数列挙のライブラリが謎な感じだったので出し直し…

C. Plasticine zebra

Problem - C - Codeforces

w と b で構成される文字列 $s$ に以下の操作を任意回数行って、 wbwbw のように1文字ずつ交互に現れるような連続部分列を最大何文字作れますか、という問題。

文字列を好きなところで2つに分割し、その両方を左右反転する。

「好きなところで分割して両方を左右反転する」という操作がどういうものなのかイメージが付きづらいですが…ちょっと実験してみます。

w と b だと分かりにくいので、番号を付けて s = 123456 とします。まずこれを適当に半分で分割して左右反転し 321654 とします。その後…

3 | 21654 と分割・反転すると、 345612 になる。
32 | 1654 と分割・反転すると、 234561 になる。
3216 | 54 と分割・反転すると、 612345 になる。

このように、元の文字列がローテーションするような文字列になります。

そもそも1回目に分割した後の 321654 も 654321 がローテーションしたものです。問題に答えるにあたっては左右が反転しても関係ないため、結局この問題は、

$s$ の全てのローテーションについて、wbwbw のように1文字ずつ交互に現れるような連続部分列を考えた時、その最大長はいくつか

という問題に帰着できます。

操作結果がローテーションになるというのは、以下のように考えるとイメージしやすいかもしれません。文字列を円周上に並べてみると、問題文の操作は円周内での位置を動かしますが、文字と文字が交差して入れ替わることはありません。

f:id:betrue12:20180820211505p:plain

さて、答えを求めましょう。文字列の長さが $|s| \le 10^{5}$ と大きいので全ローテーションを愚直に調べると間に合いません。私は「同じ文字が連続しているところで切断する」というまどろっこしい実装をしてしまいましたが、「 $s + s$ の連続部分列を調べて、結果が $|s|$ を超えたら $|s|$ にする」という実装が一番シンプルだと思います。