Codeforces Round #554 (Div. 2)

なんとか青維持しました（1632→1677）
またしてもDが解けなかった（くやしい）

A - Neko Finds Grapes (500点)

問題: Problem - A - Codeforces
鍵と錠の偶奇だけが問題になるので、それぞれ偶数と奇数がいくつあるか数えてmin{偶鍵, 奇錠} + min{奇鍵, 偶錠}を出力してAC。 $O(n+m)$ 。

拙解 (C++14): Submission #53228308 - Codeforces

B - Neko Performs Cat Furrier Transform (1000点)

問題: Problem - B - Codeforces
最上位ビットから見ていって０があれば反転して1を足し…というのを愚直に繰り返す。０が最下位ビットまで連続するケースに気を付けて、立っているビットの数が最上位ビットのindex(1-indexed)に一致すればそこで１を足さないで奇数回の操作でおしまい。この操作回数と反転するときのビットのindexを出力する。こうすれば操作回数 $t$ は高々 $2(1+\lfloor \log_2 x\rfloor)$ 回になり、 $x \le {10}^6 < 2^{20}$ から $t \le 40$ を満たしてAC。 $O(\log x)$ 。

拙解 (C++14): Submission #53237080 - Codeforces

C - Neko does Maths (1500点)

問題: Problem - C - Codeforces
${\rm lcm} \{a+k, b+k\}$ を最小化する問題。まずは ${\rm lcm}\{a+k, b+k\}=\frac{(a+k)(b+k)}{{\rm gcd}\{a+k,b+k\}}$ から、kをなるべく小さくしつつgcdを大きくしていくと良さそうなことが分かる。 $a\le b$ として一般性を失わず、またこのgcdを $g$ とおくと、 $a+k$ と $b+k$ はいずれもgで割り切れて $a+k \equiv b+k \pmod{g}$ なので、kを相殺してaを移項し、 $b-a\equiv 0 \pmod{g}$ とわかる。したがって、 $b-a$ の約数が $g$ の候補となる。こうして列挙したそれぞれの $g$ に対して、 $k=g-a\%g=g-b\%g$ が定まって、問題文にあるように $\DeclareMathOperator*{\argmin}{arg\,min} \min \argmin_{k} \{{\rm lcm} \{a+k, b+k\}\}$ を求めて出力してAC。 $a,b\le 10^9$ だが $O(\sqrt{|a-b|})$ なので間に合う。

拙解 (C++14): Submission #53247753 - Codeforces

D - Neko and Aki's Prank (2000点)

問題: Problem - D - Codeforces
コンテスト中には解けなかった。
長さ $2n$ の括弧列全体からなるTrie木の辺をすべての辺が $\deg \le 1$ になるように塗っていく問題。すべての葉の深さが $2n$ で一定なことと、対称性をもつことによって、
$\displaystyle dp[i][j][k]:=i個の'(', j個の')'があるときに親とのエッジを青く塗ったか(k=1)、塗っていないか(k=0)$
で、交互に塗るよう遷移して、根ノードの親は実際には存在しないことを考慮しつつ $k=1$ の項をすべて足し合わせて、根ノードの子を塗るか塗らないか2通り試してAC。 $O(n^2)$ だが $n\le 1000$ なので間に合う。