. を数えるか @ を数えるかして、D を足すか引くかする。■B 問題 Daily Cookie 2。後ろから書き換える。愚直に N^2 の時間をかけて大丈夫。String の場合は検索開始位置が渡せるのでケチって線形時間にもできる。Array で検索開始位置が指定できないのはスライスを使えってことなのかなと思うけど、添字の調整が面倒くさいからやらない。■C 問題 Kaiten Sushi。配点がちょっと高い。上流にいる人が食べたいものをすべて食べてしまうという容赦ない設定は流し索麺を思い出す(Somen Nagashi)。あちらは離席して食べる時間があるけども、こちらは容赦なき総取り。人の列が減少列になるように間引いてから二分探索をしたけど、寿司の方をソートしてしまえば二分探索はいらなかった。計算量のオーダーは変わらないので実装はお好みで。■D 問題 Keep Distance。すべて出力しろと言っているのだから、愚直に列挙して間に合う制約になっている。DFS が書けますかという問題。あ、嘘嘘。愚直に列挙したら最大ケースが終了しなかったので先を見て予め列挙範囲を限定する必要があった。無駄なく列挙しないといけなかった。■E 問題 Expansion Packs。２乗の DP が許される制約(？)。解答形式が小数だからサンプルも小数で書かれているし、サンプルの２が自己ループを含むものになっているおかげでデバッグが捗って助かった。何をしたか。現在持っているレアカードの枚数 R とそこに至る確率をベースとして、今開ける１パックの期待値(＝１パック×確率)を答えに足し、レアカードが R+X 枚になる確率を配っていきたい。そうすると１パックあたり X 枚のレアカードを得る確率を予め計算しておく必要がある。そうすると１パックにレアカードが０枚で足踏みしてしまう場合があることに気がつく。こういうのは具体的にどうするとうまくいくかを考えた。１パックあたり３分の１の確率でレアカードが０枚に終わるケースで考えると、１回に２分の３パック開ければレアカードが期待できる。レアカードが入っている前提ではレアカードが X 枚入っている確率は、分母(全体の場合の数)が減っているのだから最初に求めた数字より大きくなるはずで、1/(1-1/3) の式で倍率を表すと丁度いい大きさになるなと考えた。要はレアカードが０枚の場合を含む全事象からレアカードが１枚以上の全事象への分母の減少率の逆数。しかし！ TLE が解消できなかった。C++ で書き直したものはループの範囲を限定したりといった小細工なしでも 39 ms で AC だったけど(#60354761)、時間内には間に合わなかった。制約に泣かされた。Ruby で通している人が１人いたので、これは泣き言なんだよなあ。■F 問題 Falling Bars。消えない回らないスライドしない、落ちるだけのテトリス。区間更新区間取得のセグメント木の最も基本的な使い方がわかりますかという問題。残念ながら区間更新ができるセグメント木を持っていないので、即座に撤退して E 問題の TLE 解消に戻った(解消できなかった)。あまりにもストレートな問題なので、区間更新ができるセグメント木を書くいい機会かなと思った。以前読んだ競プロに関する翻訳された PDF (現物をなくしてダウンロード元も不明) のおかげで、トップダウン式のトラバースが自分の実装に欠けていることがわかっている。セグメント木を最初に雰囲気で実装したときに、末端から LCA までを辿るようなアクセス方法になった。だけど遅延された(区間)更新が伝播するのは根から末端に向けてなので、ボトムアップ式のアプローチはまったく役に立たない。トップダウン式の辿り方をでっちあげて区間更新ができるものをがんばって実装したけど、TLE だった(#60355045)。もうちょっと実装を洗練させたり無駄を省いたり手抜きをしたりする余地がないか考えてみたいけど、とりあえずここまで。■F 問題。通った！ 提出 #60379219 (AC / 1143 Byte / 1869 ms)。さっきの TLE で再帰呼び出しをしていた４行を直接インスタンス変数を書き換えるように変更したら間に合った。今は 0 とか max とかをあちこちにrequire 'numo/narray' していた。うん、それはね、Rust も Crystal も numo/narray もローカルに、古い Windows にインストールできなくて試行錯誤できないから捨ててるんだ。あきらめがついてすっきりした。■E 問題。あきらめたと書いたそばから通っちゃったね。提出 #60486554 (AC / 355 Byte / 1966 ms)。しょうもないなあ。コードテストで判断すると、制限時間が３秒なら TLE だった提出も TLE ではなかった。TLE と AC の違いはアルゴリズムの違いではなく、スクリプトの記述の違いでしかない。だからしょうもない。でも飛び道具なしのピュア Ruby でも不可能な制約ではなかったと自分で証明してしまったんだよな。なんだよくやしいなあ、あきらめがつかないじゃないか。■■■@2024-12-18 ABC357-F の精進について 20241218 に書いた。ついでに書くけど、さっき通ったと喜んでいた ABC382-F への自分の提出 #60379219 (AC) にはバグがある。61 行目のセグメント木の初期化サイズが間違っているので、N が W よりたっぷり小さいときエラーが出る。Integer#prime_division で見つけようとしたけど、最大ケースのサンプルが通らない。200 万回繰り返すには素因数分解のコストは高すぎるらしい。もうちょっと考えてみる。約数の数が９個ということは、素因数分解したあとの形が p1*p1*p2*p2 になるものしかないのではないかと考えた。約数の数っていうのは素数ごとの (指数の値+1) をかけあわせたものなので、９になるのは (2+1)*(2+1) だけなのではないかと。ここでも平方数だ。２乗なのか４乗なのかもうわけがわからないよ。素数の２乗を列挙するだけで済むので時間は間に合うようになったけど、最大ケースのサンプル２が合わない。10 いくつかだけ少なく出る。時間オーバーの素因数分解解法の答えは合っているので、9=(2+1)*(2+1) の部分で漏れがある。9=(8+1) のケースが漏れていた。２乗４乗の次は８乗だってさ。もうわけがわからないよ。こうなるとサンプル１の嫌らしさに気がついてしまう。最初の８乗数が 256 だから、サンプル１の N=200 は絶妙に少ない。そんなこんなで 40 分間たいへんな思いをした。コーディング部分は列挙して二分探索して足すだけで何も難しくない。Ruby で 307 ms の提出があるなか自分のは 1004 ms かかっているあたり、考察がまだ甘いのだけど、もう考えたくないのだ。■F 問題 Diversity。配点が E より 25 点だけ上なのでまずは F 問題を読んだ。DP。パラメータが多い。制約は N が 500 以下な点を除いて甘くない。特に色の種類が N 以下と全く限定されていないので、どの色がすでに選択済みかというビットフラグを状態のキーにはできない。色の扱いが問題だと思った。色ごとに DP をして価格と効用がそろって上昇するように商品グループを列挙しておいて、そののち価格と効用についての DP をするのかと思った。だけど後段の DP で扱う商品群がどれだけの大きさになるのかわからない。商品を組み合わせたものをさらに組み合わせようとしている。ここらで E 問題へ。■E 問題 Sum of Max Matching。頂点数も辺の数も少なくないグラフ。パスに含まれる辺の重みの最大値を考えるということは、回り道をしてでも軽い辺を使うべきだということ。UnionFind で軽い辺から使って徐々にグラフを拡張していくのかな。特に短くない２つの数列 A と B が与えられて、その組み合わせの最小値を答えるという。各頂点は A 数列か B 数列のどちらかに含まれるか全く含まれないかで、どちらかに複数回現れることもある。グラフを拡張しながら連結成分内で A-B ペアを作ろう。具体的なペアを考えるには A,B 数列は長すぎるけど、連結成分ごとに余っている A(B) 数列要素の数を記録しておくだけでよい。A 数列の要素と B 数列の要素を貪欲に消費して損をしない。F 問題に寄り道していた時間を含めても提出まで 21 分だから、D 問題より早い。これは不思議のないことで、UnionFind を使うからクラスカル法を使うからという理由で E 問題に配置されている問題は、のーみそこねこねな D 問題より型にはまっていて解きやすいことがある。今日は得をしたけどこれとは逆に、LazySegTree を使うからという理由で F に配置されている問題は、diff が低い割に配点が高く、だけど Ruby で参加している自分は TLE にならない遅延セグメント木の実装を持っていないので撤退するしかないということで大損をする。くやしいね。■F 問題。色で商品をソートしておいて、色が切り替わるところで DP テーブルを切り替えることにして、あとは普通に DP をするだけだったのだろうか。DP は１回だけで良かったんだろうか。どんだけ考察が早くても残り 20 分で実装できる DP ではなかったけども。■■■たぶんだけど、１アールに関連して覚えている 100 という数字は、掛ける前の数字ではなく掛けたあとの数字ではなかったか。つまり、10M×10M = 100M^2 = １アール なのではなかったか。そうすると１ヘクタールに関連付けて覚えている１万という数字が、100M×100M = 10000M^2 = １ヘクタール ということになっておさまりがいい。自分の生活に一切関わってこなかった知識なのでわざわざ調べませんけども。■C 問題に関連して多始点 BFS というワードを見かけたので調子に乗ったことを書くんだけども、始点の数を区別することに意味がありますか？ 移り変わるキューの中身をのぞいてみる。キューの中に始点(距離ゼロの頂点)が詰まっている状態がスタート。そこから距離ゼロと１の頂点が詰まっている状態、距離１の頂点が詰まっている状態、距離１と２の頂点が詰まっている状態、距離２の頂点が詰まっている状態、距離２と３の……状態が次々と現れる。距離ゼロの頂点だけが唯一でなければいけない理由はどこにもないと思うんだよ。同じ距離の頂点が１個だろうが複数だろうがキューの中で整然と列をなすからプライオリティキューなしで BFS が成立している。■精進。F 問題。昨日「どんだけ考察が早くても残り 20 分で実装できる DP ではなかったけども」と書いたわけなんだけど、ARC189 が終わったあとで書き始めたら 11 分で完成したよ。提出 #60595097 (AC / 253 Byte / 1030 ms)。ひとひねりあっただけで初歩的な DP でしたね。ひとひねりでてきめんにやられてしまうところに応用力のなさが現れている。BFS の始点が複数になってやられるのと同じことだよ(調子に乗ってごめんなさい)。a0,a1,b0,b1 がある。10 通りの組み合わせのうち、a0×b0, a0×b1, a1×b0, a1×b1 の４つは答えに計上するけども、a0×a0, a0×a1, a1×a1, b0×b0, b0×b1, b1×b1 の６つは答えに計上してはいけない(これらはすでに F 関数で答えに計上されているので)。このように、0/1 で分類して 0×0, 0×1, 1×1 の組み合わせについて答えを計上する F 関数と、似ているけど異なる FF 関数がなかなか書けなかった。F 関数は FF 関数を呼ぶけど、FF 関数は FF 関数を呼ぶ再帰関数なので、FFFF 関数を定義する羽目には陥らないということも見通せなかった。F 関数の要求からとりあえず FF 関数を定義してみて、FF 関数が要求するものは FF 関数だったのでめでたしめでたしという流れ。■これかな？ PAST18-K「2で割り切れる回数」。解けなかったんだよね。シグマの範囲がちょっと違うだけで同じ問題だ。今なら解けるだろうか。ちなみに、Ruby で 81 バイトで解けるらしいです(#60224722)。通った。提出 #60784486 (AC / 650 Byte / 301 ms)。長さから判断するに明らかに不器用な数え方をしているけども、今日の F 問題と同じ構成で解けた。F 問題も K 問題も制限時間が４秒５秒なんだけど、想定解法ではない？ １秒しかいらないよ。Ruby 1.9 では RVALUE に「embed」という考え方が導入され、文字列や配列などデータのうち、サイズの小さいモノは別途 malloc するのではなく RVALUE の中に埋め込んでしまうことで、 malloc & free のオーバーヘッドを削減でき、またキャッシュの局所性を高めることができます。」「
ちなみに Array なら 3 つまで embed で扱います。」(Ruby は String をメモリ上でどのように扱っているのか？ | IIJ Engineers Blog)■最初期の提出を見てみると、出力用の第３引数を渡すことで配列を使っていてもオブジェクトの使い捨ては抑制できていたみたい。それでひどい TLE なのだから、クラス化による最大のメリットは
[] メソッドを使わないインスタンス変数へのアクセスなのかもね。@ を通過したあと . に書き換えた。■C 問題 Illuminate Buildings。難しかった。実装で２つ間違えてペナルティは４回出した。AC が出たのは終了５分前。２乗が通る制約だからと愚直に書いて、念のために最大ケースでテストしたら TLE になりそうだった。愚直というのは始点を固定して全ての間隔を試すというもの。よく考えると右側にある同じ要素を何度も参照するから２乗では済んでいない。そこで間隔を中心に考えることにした。１つおき、２つおき……の各数列について、同じ要素が最長でどれだけ続くかを数える。間隔が S なら長さが N/S 程度になる S 本の数列を考える。間隔の選び方がおよそ N 通りだからこれで O(N^2) になる。ここでも罠があって Array#values_at と Enumerable#chunk と Integer#step を組み合わせた解答が予想よりも時間を食っていた。Enumerable#each_cons には大きい数を引数にしたとき尺取りの計算量 O(N) では済まないらしい罠があると思ってるんだけど、ここにもあったのだろうか。手続き的に書き直して最初に提出するまでに 15 分かけた。そこからペナルティを重ねるんだけど、最後まで見つけられなかったバグは N=1 のケース。間隔に注目したせいで単一要素のケースが漏れて nil を出力していた。■D 問題 Santa Claus 2。どうやって計算量に対処するか悩む。たとえば BIT を使えば各行、各列のどこに家を置いて、どこから家を取り除くかは自在に(対数時間で)できる。あるいは行ごと列ごとに移動区間と家の並びのソート列があれば並行してスキャンしていくことができる。どちらも行データと列データに重複して登録される家を二重にカウントしないために同期が必要。これは行に基づいて得た訪問家リストと列に基づいて得た訪問家リストを最後に線形時間でマージして出力すれば良い。ということを考えてから必要なデータ(行ごと列ごとの移動区間)を集めて整理していった。そうすると家を中心にして考えたとき、行データと列データを参照して二分探索をするとその家が訪問されるかどうかがすぐに判断できるなと気がついて、後半の実装がちょっとだけ楽になった。BIT はいらないし、ソート列の並行スキャンもいらないし、答えのマージもいらない。ランタイムエラーでペナルティを１回出したのは N×N のグリッドを想定していたせい。D の提出をするときに C が WA になっているのに気がついて、C のデバッグをしているときに D が RE になって、C のデバッグを優先したけど結果的にデバッグしやすかったのは D だった。いっときは C をあきらめて E 問題を読んだほど。■E 問題 Snowflake Tree。木 DP かなと思って実装を始めたら親方向の情報が欲しくなって全方位木 DP だと気がついて、残り 10 分での実装をあきらめて C のデバッグに戻った。C は終了５分前に、E は終了 10 分後に AC。最も簡単なタイプの全方位木 DP だと思ったけど、もっと簡単に中心を全探索して間に合う計算量だったらしい。頂点数が N でそこから辿る辺の数が両方向で 2×(N-1) だから間に合う。しかし気付けない。だって解けるんだから。それで時間が足りてればね。■C のミスと D の重さにやられて E を通す時間がなかったのが悔やまれる。F はどれだけ時間があっても無理なので期待も諦めもない。