k = (b/p+1)/2)がまったく一筋縄ではいかなかった。他にもね、14 行目と 15 行目にある２つの式 k*k*p と (k+k+1)*p が似てるでしょ。自分の目には同じに見える。取り違えてもしかたないよね。それから、後半７行でやっているボーダーライン上のアイテムを買えるだけ買う処理だけど、これ単純に割り算で計算できるらしい。二分探索で求めたボーダーラインの意味を考えればその通りなんだけど、半信半疑になってしまうところがあると思う。■F 問題まで解ける問題が並んでいて、だけど時間内に解けたのは C 問題までってどういうことですか。最近の問題傾向のせいにしてもいいですか。自分は数字とか式を精密に扱うのはまったく苦手なので、たこ焼きに関する問題が解きたいです。文章で発想のヒントとなる過剰なディテールが与えられてるといいなあ。そして発想だけで解けるといいなあ。式変形とかまじ無理なんで、D と E が解けなかったのもそれが原因なので。■D 問題の早い人の提出を見てると、ループで１つの式の合計を求めて、４倍して１を足して答えにしていた (#61802287)。どういう見かたをすればそんなシンプルな理解に至れるのだろう。■F 問題に関連してセグメント木の max_right メソッドへの言及をいくつか見た。どうやらそれは前回の ABC388-F に関して自分が「セグメント木で解こうとすると、何をリクエストして何を得るかという検索インタフェイスがどうあるべきかがよくわからない」「懸案だった検索インタフェイスは左側の境界を与えて判定関数が true を返す区間の右端を探るメソッドということにした」(20250111) と書いていたメソッドそのものではないかという気がする。お名前いただきました。■E 問題。「制約を見たら M の上限が 10 の 18 乗だった。キューから M 回取り出そうとしたら TLE になるのは当たり前」とさっき書いた。AC までいった今だからわかるけど、キューから取り出す回数の上限は M 回ではない。(k+1)^2-k^2 = 2k+1 であることから、+1 個のコストは個数に比例して上がっていき、その和は２乗のオーダーになるから(Σk = n(n+1)/2)、取り出す回数は M の平方根である 10 の９乗に比例する。ていうかコストの定義が kkPi なのだからそれはそう。それでもやっぱり TLE になるように M の上限が 10 の 18 乗程度に定められている。■E 問題。ボーダーラインを求めてさらにボーダー上の境界に注目する問題としては PAST8-I「/2 and *3」を思い出す (#26574800)。知ってる問題だったんだよ。解法の枠組みが自明で、でも式変形が難しすぎた。$<.read か gets かの違いか？ ローカルでも遅いから再現性があるんだけど、何が悪いのかさっぱり。提出 #61608160 (AC / 256 ms)。配列の shift をやめて添字アクセスにしたら数十秒が数百ミリ秒になって AC になった。S という配列に対して shift したり []= で代入したりするのがどういうわけか遅くなるみたい。それが [] と []= の組み合わせだと大丈夫だと。これが S という配列に対してイテレータでループを回している最中の話だと因果が見えやすいけど、そうではない。この時間の差は Ruby 3.1、2.7、1.9、1.8 までさかのぼっても変わらなかったので、Ruby で最初の提出のような書き方をしてはいけないということを自分が知らなかっただけということになるのだけど、何度見てもまずさがわからないのがやばいと思う。一応書いておくと、Ruby の Array#shift は要素を前に詰める線形時間の操作ではないし、shift 操作が(配列の実データ共有を無効化する) copy on write を引き起こすこともない。……と書いて気がついたけど、[]= による代入が配列のコピー書き換えを引き起こしているのだな。自分には S という配列が１つあるだけにしか見えないから、書き換え前にコピーしなければいけない理由がわからないけど。shift には注意しよう。あ、問題について書いていない。各人が配る石がどのタイミングで尽きるかをメモしておいて、あとは決まった流れを再生する。■E 問題 Simultaneous Kagamimochi。上に乗せるおもちは小さい方から順番に選んでいくしかない。最初に間違えたのは、一度下にしたおもちを上に乗せるおもちに再利用してしまったこと。それで乗せ替えをしたりややこしいことをしてなんとか答えを合わせたけど、おもちを前半と後半に分けるともっとすっきり解けたのだろうか。■F 問題 Dangerous Sugoroku。黒マスブロックの前後に集中する BFS なのかなと思ったけど、いい具合に集中する手順が出て来なかった。■G 問題 Simultaneous Kagamimochi 2。セグメント木で連結を工夫して二分探索でできないかな。■E まで解いてまさかの緑パフォ。あまりにも厳しい。■■■精進。G 問題。セグメント木でどのセグメントをどのように連結して答えに近づいていくかを考えていたら、それってダブリングぽいなと思った。提出 #61669596 (AC / 503 Byte / 1728 ms)。セグメント木ではなくダブリング。たぶんメモリ使用量の点で、ざっくり要素数の２倍を使うセグメント木に対して、ダブリングのために要素数×log2(要素数)のサイズのデータを準備したのが不利だと思う。しかし 2 対 18 は定数倍の範囲。できあがったものは実装途中よりもシンプルになったけどすんごくややこしくて、バグはなかったけど寝る時間がなくなった。実はやってることは E 問題への提出 #61589354 とあまり変わらなくて、高速に乗せ替えをするためにセグメントごとに前計算をしたみたいな感じ。セグメントの連結というのが上のおもちと下のおもちがオーバーラップしないように乗せ替える操作にあたる。乗せ替えると何が起こるかというと、前計算で得ていた下に敷くおもちのインデックスが右にずれる。どれだけずれるかは添字との差だけから計算できる。E 問題を解くのにそんな回りくどいやり方をして時間を無駄にしていたのだった。ダブリングでなくセグメント木で解こうとすると、何をリクエストして何を得るかという検索インタフェイスがどうあるべきかがよくわからない(だから都合良くダブリングを採用した)。二分探索をセグメント木の外部に担わせると木の操作の log と合わせて log が２乗になってしまうけど、log は１つで済ませられるはずなので(実際そうだった)、セグメント木に探索を丸投げするために何をリクエストすればいいのか。汎用性(普遍性)のある問いとは何か。■セグメント木に乗せるのは下に敷くおもちのインデックスそのものではなくて、いくつ右かというオフセットにするのがいいらしい？ そうすると l+k+max(l...l+k)≦r で判定できる？ k を二分探索すると log が２乗になるので Ruby が許されるかどうか。提出 #61683769 (TLE×13/AC×33)。許されなかった。残念。もう AC があるので定数倍改善の意欲はありません。しかし、インデックスの代わりにオフセットを扱うだけでびっくりするほど簡単にセグメント木が利用できるようになるのだね。そういううまいやり方があるのは ABC371-F「Takahashi in Narrow Road」(20240914) のおかげで知っていたはずだけど。「FはまずXi←Xi-iとすることで条件を狭義単調増加から広義単調増加に書き換えておく。すると用事を完了するためには邪魔になる人もろとも目的の座標までずらせばよく、」(週記（2024/09/09-2024/09/15） - kotatsugameの日記)。他には ABC353-G「Merchant Takahashi」(20240511) も同じようなセグメント木の使い方をする。セグメント木ではないけど ARC120-C「Swaps 2」(20211022p01) も同じ発想で解く。以前はポテンシャルという勝手用語で説明していたけど、改めて共通点を見つけ出そうとすると、絶対相対変換という見かたができると思った。位置相対的な値をセグメント木に乗せても共通の土俵で比較することができなくて困るときは絶対的な値を乗せる。そしてややこしいことに逆のニーズもあって、今回の F がそうなんだけど、絶対座標が扱いにくくて相対値を乗せたいこともある。そういうテクニック。■ついに許された！ 提出 #61689758 (AC / 1030 Byte / 1837 ms)。セグメント木。定数倍ではなくオーダーを改善して log を１つにした。懸案だった検索インタフェイスは左側の境界を与えて判定関数が true を返す区間の右端を探るメソッドということにした。しかし 118 ms オーバーで惜しくも TLE (#61689533)。しかたがないので判定関数ではなく判定の閾値を引数にして判定処理を埋め込む苦肉の策でやっとの AC。苦しい。
@ を通過したあと . に書き換えた。■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 はどれだけ時間があっても無理なので期待も諦めもない。Ruby 1.9 では RVALUE に「embed」という考え方が導入され、文字列や配列などデータのうち、サイズの小さいモノは別途 malloc するのではなく RVALUE の中に埋め込んでしまうことで、 malloc & free のオーバーヘッドを削減でき、またキャッシュの局所性を高めることができます。」「
ちなみに Array なら 3 つまで embed で扱います。」(Ruby は String をメモリ上でどのように扱っているのか？ | IIJ Engineers Blog)■最初期の提出を見てみると、出力用の第３引数を渡すことで配列を使っていてもオブジェクトの使い捨ては抑制できていたみたい。それでひどい TLE なのだから、クラス化による最大のメリットは
[] メソッドを使わないインスタンス変数へのアクセスなのかもね。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 問題も制限時間が４秒５秒なんだけど、想定解法ではない？ １秒しかいらないよ。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 の始点が複数になってやられるのと同じことだよ(調子に乗ってごめんなさい)。. を数えるか @ を数えるかして、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 よりたっぷり小さいときエラーが出る。1*/2* を拾い出してからスラッシュの位置を探して計算した。なんでか 10 分かかっている。■D 問題 1122 Substring。やることが多いよね。まずペアの列を複数切り出したんだけど、同じ値が３つ以上連続している場合に注意が必要。その部分でペアの列を切って新しい列を始めるのだけど、どちらの列にもペアを登録することになる。たとえば 1 1 2 2 2 3 3 が与えられたとき、得られるペアの列２つは 1 2 と 2 3 になる(同じ数字の繰り返しは省略)。2 と 2 のペアが前後のどちらの列にも属している。その次にペアの列に対して同じ値を含まない最長の範囲を求める。現在の値を右端とするとき左端がどこまで伸ばせるかを考えた。最初は値ごとに直前の位置を記憶しておくだけでいいかと思ったけど、そうではないのだな。たとえばペアの列が 1 2 3 2 1 だったとき、右側の 1 から左側の 1 の直前までを切り出すと 2 3 2 1 になって違法。値ごとに直前の位置を記録するだけでなく、その最大値を１つメモしておく必要があった。RE/WA を１回出しつつ 26 分かけた。難しいし妥当だと思う。■E 問題 11/22 Subsequence。25 点だけ配点が上の F 問題に先に取り組んだけど追い返されてきた。スラッシュの位置にそのスラッシュを中心とする 11/22 文字列の長さを記録しておけば、(区間の両端に近いスラッシュだけちょいちょいと調整すれば)セグメント木の区間クエリで答えが出せると思ってしばらく無駄な時間を費やしていた。何を勘違いしていたか。「(連続とは限らない) 部分列」で 11/22 文字列を構成するということは、スラッシュとスラッシュで 11/22 文字列が区切られるわけではない、ということがわかっていなかった。スラッシュを飛ばしてその向こうまで 1 なり 2 なりの文字を拾い出して構わない。ということを理解すると、スラッシュの位置ごとに左に１がいくつあって、右に２がいくつあるかということだけが重要。クエリで範囲が与えられたとき、どのスラッシュにとっても同じ数だけ１と２の利用が制限される。範囲内のスラッシュに対して二分探索で左右の１と２の均衡点を探る。こういう二分探索は少し前に初めてやった(ABC364-D「K-th Nearest」、20240727)。２つの均衡点(m0, m1)を取り違えるタイポで WA を１回出しつつほぼ１時間かけた。終了５分前に WA が出たときは目の前が真っ暗になる思いがしたけど、上から読み直して運良く見つけられた。F 問題を考えていた時間とセグメント木を使っていた時間が無駄になった。3、40 分で解きたかったね。■F 問題 1122 Subsequence。A の値域が 20 以下という制約からどういう DP がやれるか考えてしまって考えが深まらなかった。D 問題でやった DP と、E 問題で気がついた「都合の悪い要素を飛ばして伸ばせる」という点がヒントになると思うんだけど、未だまとまらず。現在の要素を右端として直前の同値の要素からどれだけ左に伸ばせるかを考えたいんだけど、それをするのに何をキーにして状態を記録するのかが不明。■値が 20 種類しかないということは、最長でも 20 までしか伸ばせないということだ。ということは？ 何ができる？ 長さが問題にならないなら幅が 1<<20 でも問題ないということで、bit DP か？■五線譜ならぬ 20 線譜があって、隣接する同値の２要素を繋いだ区間が線上に乗っていて、20 本の線からオーバーラップのない区間を選んで繋ぐ。同じ線からは１つの区間だけ。■■■精進。F 問題。O(AN) の方針に行き詰まって O((2^A)A) の ビット DP に方針を定めたとして、遷移がわからなかった。ところで、状態のキーがこれまで使用した値ペアだとして、何を記録するのか。これは N 要素のどこまでを使用してその状態に至ったかの最小値。ということを整理しているうちに TSP が降ってきた。巡回セールスマン問題と同じ遷移で解ける。提出 #60111625 (TLE) のち 提出 #60113392 (AC / 612 Byte / 1405 ms)。やっぱり今日の１問レベルの歯ごたえがあった。Crystal での提出を見てると E 問題の AC から７分半でこの F を通している人がいるけども(#60070912)、それは頭がおかしい。自分はこの問題を反射では解けないし、指を動かすだけでもそれ以上の時間がかかるのは間違いない。TSP 問題は３問ほど解いたことがある(だけど未だに苦しむんだよ)。たとえば ABC180-E「Traveling Salesman among Aerial Cities」(20201018p01.02)。これ水 diff 下位の難易度しかないことに驚く。この F 問題は青 diff 下位だったけど、目くらましが目くらましとして機能しないレベルの人にとっては、青も水も変わらず典型パターンを当てはめるだけの問題になってしまうのか。それも難なくやってのける。■■■A 問題。ややこしいし効率が悪いしやる意味はないんだけど、あえての正規表現。提出 #60163766。パターンは ^(1\g<1>2|/)$。Ruby ならできます。同じパターンを C 問題でも使おうとしたけど、N≦200000 では TLE が不可避だった(提出はしていない)。■■■F 問題。それとさっき挙げた ABC180-E Traveling Salesman among Aerial Cities。遷移まで含めて bit DP と呼ばれてるみたい？ 「集合 S をビット表記により 0,1,…,2N−1 までの自然数にエンコードしてしまうと、S=0,1,2,… 順にループするだけでトポロジカル順序が守られることなどから、実装が簡潔になります。この実装方法から bit dp とも呼ばれることの多い手法です。」([AtCoder 参加感想] 2020/10/17:ABC 180 | maspyのHP)。自分が bit DP と認識しているものはメモ化再帰とよく結びつくもので、状態をビットフラグで表すことで順序に関する情報を落として再計算を省くというもの。遷移はそのつど再帰関数を書くときに考えている。だけど bit DP というだけで今回のような遷移が引き出せるべきなんだろうか。
