ARMERIA

放置していたけど更新再開、Rubyと競技プログラミングの話が中心になっていく予定です

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種類でもあれば、 aabcbbbccccc のように、他の文字を全部拾っていくことができます。また、文字列が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

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

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

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

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

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

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

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

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

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

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

f:id:betrue12:20180820211505p:plain

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

さいごに

私が全く解けなかったD問題もプレテスト段階では1000人くらい通していたのに、システスで残ったのは500人くらい。本当に波乱の回でした…前日・前々日と連続でシステス落ちした経験が生きたかなと思います。

脚注

*1:素数定理というものがあって、整数A以下の素数の個数を見積もることができます。20億以下の素数の個数はだいたい1億程度です。

*2:素因数をなるべく多く稼ごうと思うと、小さい方から素数を掛けていくことになりますが、素数16個目で積が(2×109)2を超えます。なので16個以上は得られません。