[AtCoder 参加感想] 2019/08/18:ABC 138

  A B C D E F
問題文
自分の提出
結果 AC AC AC AC AC AC

スポンサーリンク

全体感想

52分6完(ペナルティなし)で21位でした。
ここ2ヶ月くらいでは一番の高順位でした。

最近のABCでは簡単セット?
Fが細部でミスしやすいくらいでしょうか。ほかの問題は実装に悩む要素も少なかったように思います。

問題B – Resistors in Parallel

numpyに慣れたい人は適当な練習問題でしょうか。
\[ \frac{1}{\frac{1}{A_1}+\cdots+\frac{1}{A_N}} \] は

1/((1/A).sum())

と書くだけでよくて簡潔です。

※ numpy は、難しいことやって高速化を得る方法というよりも、簡単なことが簡単に書けるので便利です。

問題D – Ki

各操作と、最終状態の関係を考えると、

・頂点 $x$ には、最終状態で、$x$ の親のどこかに足された値の合計が加わる

というルールだと分かります。すると、根から順に、その頂点の最終値を計算していくことができます。

より詳細には、$x$ の親が $y$ であるとき、最終的な頂点 $x$ の値と最終的な頂点 $y$ の値は、直接 $x$ に足しこまれた値だけの違いしかありません。よって $x$ の値は $y$ の値からすぐに計算できます。

再帰関数による dfs →
list での dfs →
どちらでも書ける場合は、深い関数呼び出しを避けた方がやや高速のようです。

問題E – Strings of Impurity

$t$ の一文字ずつ見て行って、sのどこに現れるかを見ていくことゲームです。

contestcontestcontest
contestcontestcontest
contestcontestcontest

sで1度も使われていない文字が出てきたらアウト(答は’-1’)。
そうでないなら、文字列を追加で1周するまでに必ず1度見つかります。あとは次の課題をクリアすればよいです。

【課題】sにおいて、$x$ 文字目以降で指定のアルファベットが最初に出てくる位置を計算せよ。

各アルファベットの出現位置のリストを事前計算しておくと、
【課題】リストから、$x$ 以上であるような最小の元を取り出せ。
というような課題に置き換えることが可能です。これは、リストがソートしてあれば二分探索により高速に計算できます(今回は自然に作ればソート済リストになる)。

pythonの場合は、二分探索は bisect を使うのが簡単です。

問題F – Coincidence

$x,y$ に関する必要条件を考えていきます。桁数や最上位、最下位の桁などについて言えることを考えると、
・$x$ の桁数が $y$ の桁数より小さければ詰み
ということが分かります(桁数は2進法に関するもの)。するとさらに
・商は必ず1になる
・結局、商が1($x > 2y$)かつ $y = x \ \mathrm{xor} \ (y-x)$ という条件

ということも分かります。また、$y = x \ \mathrm{xor} \ (y-x)$ については、2進法で繰り上がりのない足し算なっていることと同値です。
これは、$r = y-x$ として、$x \ \mathrm{xor} \ r = x+r$ と考えると分かりやすいでしょう(桁ごとに考えて、一般に $x \ \mathrm{xor} \ r \leqq x + r$ であり、等号になるのは桁ごとに等号になる場合)。
結局

$x > 2y$ かつ $x$ である桁が1ならば $y$ もその桁が1

というような条件が得られます。あるいは bit列を集合と見立てて
$x > 2y$ かつ $x \subset y$

と書いてもよいでしょう。これを数える問題です。解法は、俗に桁DPと呼ばれているっぽいものだと思います。
「上の方とか下の方が適当な条件になっているものを数えようとすると、それは小さい桁数のときの問題に帰着できるよ」というタイプ。
私は桁DPは、下の桁から決めて行ってメモ化再帰関数で実装するのが好みなので、そのようにしました。

・$F(L,R)$:$L\leqq x\leqq y\leqq R$ かつ $2x > y$ かつ $x\subset y$ となる $x,y$ の個数(答になるやつ)。
・$G(L,R)$:$L\leqq x\leqq y\leqq R$ かつ $2x \geqq y$ かつ $x\subset y$ となる $x,y$ の個数(補助的に)。

などと置きます。これをそれぞれ、1の位(偶奇)で分割して漸化式(DP)を作ります。
例えば $F(L,R)$ は、次のようにして1桁少ない場合に帰着できます。

(1) ともに偶数、つまり $x = 2x’$, $y = 2y’$ と書ける場合
$2x > y \iff 2x’ > y’$ であり、$\lceil\frac{L}{2}\rceil \leqq x’,y’\leqq \lfloor\frac{R}{2}\rfloor$ なのでこれは $F(\lceil\frac{L}{2}\rceil, \lfloor\frac{R}{2}\rfloor)$ 通り

(2) 奇数・偶数、つまり $x = 2x’+1$, $y = 2y’$ と書ける場合
これは条件 $x\subset y$ に反する。$0$ 通り

(3) 偶数・奇数、つまり $x = 2x’$, $y = 2y’+1$ と書ける場合
$2x > y\iff 4x’ > 2y’+1 \iff 4x’ \geqq 2y’+2 \iff 2x’\geqq y’+1\iff 2x’>y’$ となるので、同様にして$F(\lceil\frac{L}{2}\rceil, \lfloor\frac{R-1}{2}\rfloor)$ 通り
(4) 偶数・奇数、つまり $x = 2x’$, $y = 2y’+1$ と書ける場合
$2x > y\iff 4x’+2 > 2y’+1 \iff 4x’+1 \geqq 2y’ \iff 4x’\geqq 2y’\iff 2x’\geqq y’$ となる。$G(\lceil\frac{L-1}{2}\rceil, \lfloor\frac{R-1}{2}\rfloor)$ 通り
ここで$G$が必要になります。
という要領です。遷移で出てくる $L$ や $R$ は、結局最初の $L$ や $R$ を$2$で割っていったもの $\pm 1$ くらいしかありえない(1を引いた場合、引かなかった場合などの差がすぐに溶けてなくなる)ので、メモ化すれば計算量は $O(\log R)$ 程度です。
実装時には、functools の lru_cache を使用しました。また、細かい式を書き分けなければいけないので、ナイーブな解法も実装しておき、それと比較しながら実装をすすめました。

タイトルとURLをコピーしました