なかけんの競プロノート
🕒 2020/12/14 🔄 2021/06/14

ABC185感想戦

🌏

AtCoder Beginner Contest 185 に参加しました。画像はコンテスト中に書いたメモです。

Aは、4つのうちの最小値を答えればOK。1分。

Bは問題文がややこしいな。スタートから、減少と増加を繰り返して0になることがあるかどうかを調べるだけ。maxよりは増えないことに注意する。8分。

Cは、L-1か所の切れ目候補から11か所を選べばいいので、 ${}_{L-1}\\mathrm{C}_{11}$ を計算すればいい。答えは $2^{63}$ 未満になるらしいけど、分子を全部かけてから計算してしまうとオーバーフローしてしまうので、工夫して計算する。

で、このときにやったのが、分子にある $L-1$ から $L-11$ までのうち、約分できるものは約分しておいて、それから掛け合わせるというもの。分母は固定なので、素因数分解しておく。

例えば、分子を2で合計8回割っておく、などとする。これでAC。提出 #18734045。

しかし、今これを書きながら思ったんだけど、こんなことをせずに $\\dfrac{L-i}{i}$ をそのまま掛けていけばいいだけだった（提出 #18773320）。ここで10分近くかかったけど、これだともっと早くできたのに。めんどくさいことをしてしまった。ここまでで18分。

Dは、とりあえず、ハンコはできる限り大きい方がいいので、大きさの最大値を求めないといけない。それが求められたら、回数を求める、という手順でOK。ハンコを押したい区間を、ハンコの幅で割る（切り上げ）と、その区間で必要な回数が求められる。

で、ハンコの大きさの最大値を求めるために、なぜか二分探索をしないといけないと思って、やる（提出 #18745392）。

しかし、こんなめんどくさいことをする必要はなくて、ハンコの大きさの最大値は、区間の一番短いところ（0は無視する）の長さにすればいいので、二分探索なんてする必要はなかった。順位表を見て「なんでみんなこんなに早いんだ」と思ってたんだけど、自分がへんな回り道をしているだけだった。ここまでで42分。

順位表を見ると、EよりFが解かれていたので、問題を見てみる。xorか。うーん、大変そう。いや、待てよ。セグ木にのせるだけでは？AtCoderライブラリの練習問題か？という気持ちに。

そして、ここでも謎にセグ木ではなく、遅延セグ木を用いてめんどくさい道に入ってしまう。ARMERIAさんのサイトを見ながら以前遅延セグ木を少し学んだので、それを思い出しながらやる。

https://betrue12.hateblo.jp/entry/2020/09/22/194541

無事通せた（提出 #18750318）。しかしこれが緑パフォ。恐ろしい。この時点で57分。

FよりEを通している人が少ないとはいえ、通している人は多かったので、Eも通せないとまずいよなぁ、という気がしてくる。あと40分でなんとかできるか。

とりあえず、 $A_i$ や $B_i$ の値の大きさにはあまり意味がない。同じか違うかだけがわかればいい。あと、 $N,M$ が1000以下なので、 $NM$ のサイズの配列・計算時間を作って解くことはできる。

はじめは、同じ値の要素同士をつなぐグラフとかをやるのかなとか思っていたけど、「片方の数列を片方に合わせに行く」と考えていると、編集距離のことを思い出す。 $NM$ のサイズの配列が使えるし、これでいけそう。

Aのi番目までとBのj番目の編集距離 $d_{i,j}$ を考えるとき、i-1番目とj番目の距離に1を足す（i番目の削除に対応）、i番目とj-1番目の距離に1を足す（j番目の削除に対応）の小さい方を持っておく（ $a$ とおく）。さらに、Aのi番目とBのj番目が等しいときは、i-1番目までとj-1番目までの距離 $d_{i-1,j-1}$ と同じにできる。等しくないときは、 $d_{i-1,j-1} +1$ とする。これらを $a$ と比較して一番小さいものを $d_{i,j}$ とする。あとはこれを順番にやるだけ（提出 #18760756）。94分。

なんとか全完できたけど、かなり回り道をしてしまっていた。もっと早くできていたはず。まだまだ修行が足りない。