脳log[20230725]

2023年07月25日 (火) [AtCoder] 精進１。ABC104-D「We Love ABC」(青 diff)。３つの要素があるときに真ん中に注目するという典型をこの前仕入れたのでその方向で考えてみた。各文字を見ていくとき、その文字が B である場合と、? を B にする場合に ABC 数を数えて足し合わせたい。前準備として左にある A の数、? の数、右にある C の数、? の数を知るために累積和を用意する。既存の A のうちのひとつを利用する場合には左にある ? に ABC のどれを割り当てても良い。? のうちのひとつを利用する場合には割り当て可能な ? の数が１つ減る。わかりにくかったのは、文字列の種類数と ABC 数としてカウントするための A の文字の選び方の区別。つまり、? への文字の割り当て方は 3.pow(? の数) 通りあって、それぞれの文字列に対して A の数だけ ABC 数を数えるための重みがあるということ。同一文字列を重複して数えてはいけない気がして ? への文字の割り当て方に制限を加えて順序よく数え上げようとしていたのだけど、全然いらない心配だった。ある A(もしくは A を割り当てた ?)に注目して ABC 数をカウントするときと別の A(もしくは ?)に注目して ABC 数をカウントするときに、それぞれに S 全体が同一の文字列になるものがあってもよい。■提出 #43942246 (AC / 451 Byte / 220 ms)。■■■精進２。ARC092-D「Two Sequences」(黄 diff)。XOR を考えるときに問題を桁ごとに分けるのは基本だけど、足し算がかかわると繰り上がりがやっかいだよね。ひとつの対処法を知っている。ARC158-C「All Pair Digit Sums」を解いていたときのこと。「kotatsugame さんの動画を見ていたら k 桁目を見ているときにその桁の数字と同時に 10**(k-1) で割った余りを持てばいいと教えてもらった。たとえば A={1234,9876} だとして 10^2 の位に注目しているとき、(2,34),(8,76) を処理対象にする。余りの部分は小数点以下の数字みたいなもの。言われたら、たしかにそれでできそうではあるけど、でも、そういう発想はたぶん待っていても出てこなかっただろうな」。そうすると数列をマスクしてソートして、注目しているビットが１になる境界、繰り上がって０に戻る境界、さらに繰り上がってきて１になる境界がこの順で見つかる。時間が厳しいので二分探索を使わずに尺取りでやる。これは２か月に渡って苦しめられた Pairs の教訓。■提出 #43950013 (TLE×４) のち 提出 #43950581 (AC / 515 Byte / 2106 ms)。正直初手で通ってほしかった。TLE を回避した手段はイテレータメソッドを while ループに書き換え、Array#map と Array#sort を破壊的メソッドに置き換えたこと。読みにくくなるだけでアルゴリズム的な改善はない。■Corvvs さんの提出 #3092072 を見ると添字を３つも管理していない。キャリーにだけ注目している。AB 変数の意味もわからない。むむむ。■１のビットの数の増分だけ見てるのかな。キャリーが起こると１が２個減って上の桁で１が１個増える。２個減るのは XOR を考える上で意味を持たないけど、１個増えるのは答えに影響する、みたいな？ AB 変数がベースラインで、rmask 変数がキャリーによる変動、とか？ rmask 変数の末尾に無条件で 0 の桁を追加してるのもそれっぽい。自分でコードにできるほどはっきりはわかんないけども。■ところで、自分が他人のコードを読むときって、完全に雰囲気で読んでいる。個別の式の意味を解釈するよりも、全体の形(ループとか)に注目している。雰囲気だから「みたいな？」みたいな感想になる。たとえばこのときも「面白いことを書いている人がいる。「ABC303-D　この問題の正解者は実は間違っていた」。形式だけ見て気が付いたことを」。どういう値を触っているかだけ見てその値の意味を理解しないまま感想を書いている。細かい話は苦手なんだよ。確率・期待値・数え上げ問題の数合わせとかもー最悪。■提出 #43953782 (AC / 484 Byte / 1605 ms)。キャリーによる増分に注目するので間違いなかった。でも伏兵があった。ベースラインとなる繰り上がりを考慮しない和(それは XOR と等しい)の XOR を求めるところに罠があった。項数 N が偶数の時はきれいに打ち消し合って０になるのだね。これはきっちり式を整理して計算しないと気付けない。■提出 #43989881 (AC / 842 Byte / 1496 ms)。Array#sort(一般に NlogN)の隣で二分探索を尺取りにしてもそれは定数倍の改善だし、３つの尺取りが１つの尺取りになってもやっぱり定数倍の改善だけど、ソートを工夫するところまでやると log が落ちて Nlog(N)log(max A) が Nlog(max A) になるっぽい。「数列のソートに桁ごとのバケットソートを使用します。下位の桁から順に計算していけば基数ソートの動きそのままになるので、各桁で O(N) でソートが可能です」 ちょっとだけ早くなった。ちなみに、配列の確保＆使い捨て(15-16 行目)を抑制しようとして添字をちまちま操作しても Ruby の場合は逆に遅くなったりする。実際にローカルでは遅くなった。