脳log[20240817]

2024年08月17日 (土) [AtCoder] 今日は AtCoder Beginner Contest 367 があった。最終的には嬉しい結果だったけど、かけた時間で難易度を判定すると E<F<<<<D なのが複雑な気持ちにさせる。もっと早く D が解けても良かったのでは？ 以下ふりかえり。■A 問題「Shout Everyday」。スマートに解くことができない。ループを回して %24 で現在時刻を表し、それが A 時ならたこ焼きへの愛を叫び、それが B 時ならループを終了した。■B 問題「Cut .0」。String#chomp! という便利なメソッドがあるので、無条件に５回呼び出した。■C 問題「Enumerate Sequences」。５の８乗掛ける８が数百万のレベルだったので、Array#product で全数列を列挙して選んで出力した。■D 問題「Pedometer」。問題文を読んでもいない G を除けば本日のボス問題。やり方は少し考えるとわかった。最初に累積和を用意すれば、頂点１から自身を除く他の N-1 個の頂点までの距離の一覧が得られる。この一覧を更新しながら、全頂点について、条件を満たす他の頂点を数えるのが方針。条件というのが M の倍数となっているけど、デバッグのためには %M が邪魔なので、うまいことできればいいですね！ 自分は AC まで 51 分かけて、そのうち 40 分かそこらは下手なデバッグに費やしていた。■E 問題「Permute K times」。一読ダブリング。■F 問題「Rearrange Query」。Range Set Query とかそのへんの問題に見える。一致判定はソートして一致するかどうかでいいが、クエリごとにソートすることはできない。残り時間が 25 分しかなかったので(D 問題の半分！)、半ばあきらめて仰向けになって目をつぶって考えてみると(今日は朝がいつもより 30 分早かったのだ)、ローリングハッシュでずるいことができそうだと思った。数列の各値を素数で置き換えて、範囲の一致を範囲の積の一致で判定するならソートの必要もない。実装が軽かったので最初の提出を出したのが終了７分前。これは要素を素数に置き換えるためのコードを呼び出し忘れていたので WA になった。２分で修正して出した２つ目の提出は、素数１と素数２をあちらこちらで取り違えていたのが原因で WA だった。さらに２分で修正して出した３つ目の提出が AC だった。終了３分前。これが WA だったときのために３つ目の素数を利用するバージョンを WJ のあいだに用意していたが、結果的に必要なかった。■自分のすべての提出。前回が３完で、今日も D 問題がさっぱり合わなくて泣きたくなるやら腹立たしいやらだったけど、最終的に A-F の６完で大満足。D 問題がもっと早く解けたはずだとか、F 問題の２ペナの原因がしょうもなすぎるとか、欲をかけばきりがないけども、冴えないなりに健闘した。■F 問題。他の提出を見てると、自分はずるのしかたが下手だった疑いがある。素数はたくさんはいらないのかな。要素を素数にするのでなく、要素を素数の指数にして、範囲の和の一致で判定をするのが、まっとうなずるのしかた、っぽい？ チェックサム？ ローリングハッシュ自体がベースと mod の２つしか素数を使わないしね(※２つの素数でも十分だけど、書いてあったのは互いに素な２数だった)。自分みたいに要素をそれぞれ異なる素数に置き換えて、それらの範囲の積で判定をするのは、無駄だし要素数に応じてスケールしない下手なやり方。そもそも、ロリハ言いながらなぜ変なやり方をしているのか。たぶんローリングハッシュは位置と値に意味があるもの(位取りされた数字の列や文字列)に限られた範囲のアイデンティティを割り当てる方法であって、F 問題で必要なのは多重集合のアイデンティティだから、ローリングハッシュとして知っている方法にならなかった。各要素に散らばったユニークな値(x 番目の素数であったり、素数の x 乗であったり、Ruby であれば x.hash でも OK らしい)を割り当てたら、集合のアイデンティティとしてはその和でも積でも求めれば順序を問わない値が合成される。発想はロリハでもそれはロリハとして知っている方法ではなかった。ところで、「x 番目の素数」と「和」の組み合わせでは衝突しやすいかもしれないので(2+5=7 みたいに)、素数の積にしたのはファインプレーだったのかテストケースの穴なのか。あ、素因数分解から連想して ID を定めるか、N 進数から連想して ID を定めるかという感じでまとめられるのかも。素因数分解ならあいだに入る演算は掛け算に決まってるし、N 進数なら当然各桁重み付きの和を求める。多重集合の要素に割り当てる値の定め方に応じて、合成された全体の ID として積が選ばれるか和が選ばれるかは決まっていたのかも。■D 問題。不明なまま放置していた問題名。ペドメーターって響きがいかがわしいけど(それはお前が……)、pedestrian (歩行者) から連想すると歩数計なのかな。読み直すと、問題を解くのには全く影響しない単位が歩数だったから、たぶんそう。あたりをつけただけで確定はさせずにやっぱり放置するのはいつも通り。pedometer が何かに興味がないし気にもならない。広告があふれすぎている現代への適応。■■■ D 問題。「累積和を計算して、Mの剰余が同じ位置を集めます。そしてその位置の集まりで差がN以下の個数をカウントします。そのとき、その集まりが大きくなる可能性がありますが、尺取り法的に計算すれば速くなります。」を参考にして。提出 #56958498 (AC / 318 Byte / 371 ms)。最初の提出 #56820856 (AC / 232 Byte / 202 ms) より長くて遅くてメモリ消費量も多いけど、ややこしいデバッグは必要なかった。コーディング時間は 20 分くらいかな。30 分の節約。