AtCoder Regular Contest 099
Updated:
Source codes
Solutions
C - Minimization
最終結果は、すべてが 1 になる。最適戦略を考察する際に、 順番を後回しにして操作をする区間を先に決める のがわかりやすい。すると、操作する区間が全区間を被覆しており、端を除いて、両端で共通部分がないといけない。操作する順番は $1$ を含む区間から初めて順番に伝播させて行く。
よって、区間の数を $g$ とすると、 $N \leq K + (K-1)(g-1)$ を充たす最小の $g$ が答えである。
D - Snuke Numbers
サンプルにある通り、 $n \geq S(n)$ は確実だから $n / S(n)$ の最小値は $1$ である。だからこの最小値を達成する $1, \dots, 9$ はすぬけ数である。
$f(n) = \mathrm{argmin}_{m \geq n} n/ S(n)$
と定める。 $1$ からスタートして、 $n$ がすぬけ数だとわかったら次に $f(n+1)$ を求めることを繰り返す。
まず、 どのような数がすぬけ数としてありえないか を考察する。 $X$ をワイルドカードとして、$2102903847$ より大きい数であり、かつ $2106XXXXXX$ が次のすぬけ数であるとするならば(そんなことは絶対ないのだが)、その候補は $2106999999$ しかありえない。なぜなら、ほかの数字にすると、例えば $2106123456$ にすると、ここを $2105999999$ は分母が大きくなり分子が小さくなるので、劣る。この時点で桁数の $10$ 倍しか候補がないので、この時点で解答が出る。例えば $f(2102903847)$ であれば任意の桁に注目し、それを大きくして、その下の桁をすべて $9$ に置き換える。桁数も大きくすると必ず劣ることにも注意されたい。
ポイント
Ruby で余裕で間に合う。 Ruby の場合文字列のイコールはポインタのコピー渡しになるので、ハードコピーする必要がある。 str2 = str.dup のようにする。
E - Independence
$G = (V, E)$ を元のグラフとする。ここで $G’ = (V, E’)$ を次の規則で作る：相異なる $v, w \in V$ に対して、 $e = (v, w) \in E$ であることと $e \not\in E’$ であることは同値であるとする。このとき $G$ が問題の条件を充たすための必要十分条件は、 $
G’$ において disjoint な $X \cup Y = V$ が存在し、 $X, Y$ のそれぞれの中で全く辺が張られていないことである。ということは、辺は必ず $X, Y$ にまたがっていることになる。ということは、 $G’$ は二部グラフでなければならない。二部グラフでなければ答えは -1 である。これは彩色することで判定できる。
$R = \lvert X \rvert$, $B = \lvert Y \rvert$ とする。 $G’$ は連結とは限らないので、どちらの色で塗るかは DP で決めることができる。すべて試して最小値を取る。
ポイント
問題はかなり早い段階で解けていた。提出だけができなかった。
DP のところで最後間違えた。配列を使いまわしてはいけない。
F - Eating Symbols Hard
解答
ハッシュを取ることにする。 $M = 10^9 + 7$ とし、 $1 \leq X < M$ を乱数とし、 とする。文字列 $T$ に対して飲食を実行した後の $a_i$ を用いて \[ t(T) = \sum_{- N \leq i \leq N} a_i X^i ~~~~ \mathrm{mod} ~ M \] と定める。以下 $\mathrm{mod}$ は省略する。するとこの問題は $0 \leq i < j \leq N$ であって $t(S) = t(S[i, j))$ であるものの数を求めればよろしい。
ローリングハッシュ法を用いるため、 $1$ 文字ずらすときにどのようにハッシュ値が変わるか考察する。以下の関係式が導かれる。
- $t(\emptyset) = 0$,
- $t(+T) = t(S) + 1$,
- $t(-T) = t(S) - 1$,
- $t(>T) = t(S) X$,
- $t(<T) = t(S) X^{-1}$.
これを踏まえて、 $0 \leq i < N$ に対し、
$f_i(a) =$ ハッシュ値 $a$ に対し、「そのハッシュ値を作る前」に $S_i$ の文字をかませた場合に作られたハッシュ値
と定める。要するに $f_i(p) = a \pm 1, X^{\pm 1} a$ のいずれかである。すると問題文の条件 $t(S) = t(S[i, j))$ は、 $c = t(S)$ とすると、 \[ c = f_i \circ f_{i+1} \circ \dots \circ f_{j-1} (0) \tag{1} \] と書ける。さて $f_i(a)$ は $a$ の $1$ 次式であり、いずれの場合も逆関数 $g_i = f_i^{-1}$ が存在し、しかも $1$ 次式で書ける。すると条件式 (1) は次式と同値である。 \[ g_{N-1} \circ \dots \circ g_i (c) = g_{N-1} \circ \dots \circ g_j (0) \tag{2} \] これならば、両辺それぞれを列挙することは $O(N)$ でできる。 $1$ 次式の合成はすべて $1$ 次式であるからである。前者を $a_i$ とし、後者を $b_i$ とすると、求めるものは $a_i = b_j$ かつ $0 \leq i < j \leq N$ を充たすものである。
注意点としては、 $X$ は複数個試し、合議制のもとで解答を決定する。
ポイント
これは自力では無理ですね。ハッシュ使うというのは理解していなかった。
サンプルケースは全部通ったんだけど、テストケースが結構 WA している…
Others
正式版が正常に提出できないことにより、解けていたはずの E が時間内に提出できなかった。 AtCoder でやってきた中で最悪のゴミみたいなコンテストだった。
具体的には、問題は良いものだったと思うけれども、正式版で提出できないことにより、「Net::ReadTimeout (Net::ReadTimeout) が返ってくるまで提出が遅れる」「提出できないで手動で提出するしかない」「場合によっては提出されているので無駄に WA 」ということで、 無駄な 1WA と提出ごとのタイムアウト待ちで時間を無意味に浪費した。
「みんなが同じ障害を被っているから rated なのだ」という理屈は、「公平ですからみんなで平等に不幸になりましょう」というよくある屁理屈だと思う。そのせいで解ける問題が 1 問変わって順位が 500 位程度変動し、 rate のプラスマイナスも入れ替わるなら最低じゃないのって思う。
前回はたくさん WA が提出されたことによるアクシデントだったということだから今回は起らないだろうと思っていたが、全く無意味だった。次回から beta 版でスクレイピングすることにする。正規版が「接続が不安定です。 beta 版をご使用ください」というなら正規版を廃止し beta 版を正式版としてリリースすることが普通の理屈だと思う。それを望む。