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 というだけで今回のような遷移が引き出せるべきなんだろうか。
N 個のマスすべてに石がちょうど 1 個ずつ入っている」)。石が余る場合に間違えていた。修正に５分。N マスすべてに石が配れるかは確認済みなので、石の総数が N であることをチェックするだけ。ペナルティ込みで 23 分かけた計算。難しいよー。■D 問題「Home Garden」。一転して簡単な問題。配列(生配列とポインタペアで十分)に植えた日を記録していく。収穫は先頭から順番に。４分半。■E 問題「Sum of All Substrings」。かつての ABC-D 緑 diff って感じの問題。まず、余りを取る問題でないことに驚いた。えっ。64 ビットに収まるんですか？ (サンプルを見て)収まらないね。１の位から考える。S の各桁の数字は１の位として何回活用されるか。10 の位、100 の位としては……。繰り上がりも考慮して決めていく。提出までおよそ 30 分。書く量は 252 バイトでもすらすらとは書けない。■F 問題「Buildings 2」。よみがえる ABC372-D「Buildings」の悪夢 (「脳みそがスポンジ化している」「番狂わせの D 問題」「提出するまでほぼ１時間ぐだぐだやっていた」「問題が全然頭に入ってこない」「いったい何を数えるんだよー」「"ビル i とビル j の間にビル j より高いビルが存在しない" という i と j のペアを数えるんだけど、えっとね、i のビルの高さはなんにも関係ないんだよ」「理解したら実装は５分」)。慎重に問題とサンプルを読んで理解に努めた。基本的には自分自身を起点とする増加列を数えておけば良さそう。自分より低いビルも見ることができるんだけど、r より低いビルを l から見ることはできないので、それは数えても意味がない。l と r の高低にかかわらず r から見える r より高いビルの数が答えの候補になる。あと考えることは、l から r が見えない場合。答えはゼロではなく、あいだにある最も高いビルから見えるそれより高いビルの数が答えになる(この条件は r が最も高いビルである場合もカバーするので場合分けが消える)。ランダム入力と愚直解法からこのケースを見つけた。ABC372-D の記憶によって数えるべきものがはっきりわかっていたから、見つけたケースの解釈で迷うことがなかった。あとは増加列を数えるのに LIS をやるポカをした。スタックを１本持って長さを数えるだけでいいのはさっき挙げた Buildings と同じはずなんだけど、なんで同じにできなかったんだろうなあ。最初の提出 #59612302 (WA) を書くのに 20 分かけて、デバッグに 20 分かけた。提出 #59621904 (AC)。■G 問題「Count Grid 3-coloring」。10 分も残っていないので問題を読むだけ。左の数字と上の数字を参照して１,２,３の場合の数を数える DP かなと思ったけど、制約が３乗を許容しているし制限時間も長めの３秒なので、何かが抜けているか全てが間違っているかのどちらか。■コンテスト成績証。青パフォ 1763。■あっ、F 問題の問題名が Buildings 2 だ！ そうか、問題名で自己言及していたのか。■■■C 問題。左にある石の山から処理をしようとするといろいろ保留することになって面倒そうと書いたけど、実際には左からやった方がシンプルになった。提出 #59709275 (左から / 204 Byte)。提出 #59582960 (右から / 280 Byte)。
Ai と等しい要素が i の直前に出現した位置を Bi とする」とあったが、等しい要素を A 数列から探すのか B 数列から探すのかわからなくてフリーズしてしまった。サンプルで理解したけども、読み飛ばして「
より正確には」以下を読むのでも理解できた。だけどそこまでたどりつかずにぐるぐるとスタックしてしまった。わかれば値の範囲を見て Hash でメモ。■D 問題 Count Simple Paths。計算量で難しさを出してくるのが D 問題というイメージなので、愚直 DFS が通るのは甘々です。だけど BFS は書けるけど DFS はなんか苦手という時期が自分にもありました。■E 問題 Mod Sigma Problem。解けてないよ。６問解く実力がなくて F 問題が 25 点だけ上なら F 問題を先に解かない理由がないよ。■F 問題 Add One Edge 2。単純グラフというのは自己辺なし多重辺なし。単純グラフというのは自己辺なし多重辺なし(２回目)。問題文を読んでるときにこの通りに補完しているが、ABC なんだからそこまで書いてもいいと思うんだよね。知らなきゃ解けないという問題は門前払いされたようで面白くないよ。それが概念でなく単なる言い替えレベルの用語がどう定義されているかというだけのことであればなおさらしょうもなくて面白くない。次数２の頂点同士を結んでその LCA までのパスがすべて次数３であるか、LCA が次数２の頂点の一方であるかという場合を数える。とにかく実装が下手だった。WA (隣接している次数２の頂点を結んでしまっていた。それは多重辺)、WA (葉を刈り取る DP をしているのに処理順が LIFO だった。20241019と同じミス。手癖で書いてるんじゃないのよ。pop かな shift かな pop でいいよねと考えた結果なのが救われない)、WAWAWA (葉を刈り取る DP をしているのだから、１を仮の根としたときの親に処理を流すのは間違いなのよね。この場合の根とは最後まで残った１ノードのことなのだから。一番深いところから積み上げる DP なら間違いではなかったし、脳内イメージではそうしていたんだけど、実際にやってることがちぐはぐだった)、AC (再帰関数で再実装したら AC だった。だって何度問題を読み直してももう考えることが残っていなかったので、原因がわからなくても実装が悪いことが明らかだった)。■レートは横ばい。デバッグとペナルティで失った 50 分が痛い。■■■精進。E 問題。累積和とか転倒数とか BIT とかのワードを見かけてもいまいちピンときていなかったが、ある動画でエスアールヒクエスエルが負と聞いてやっとやるべきことがわかった。それを正しくやるのにも散々迷走して凡ミスをして苦しむんだけど。提出 #59430244 (AC)。■■■精進。水 diff ながら抜けていた ABC221-E LEQ。さっきの E 問題を解いたあとだと普通に解ける気がして、普通に解けた。提出 #59440817 (AC)。ABC378-E とは類題ってことでいいのでは？ 自分は感覚とかイメージとかのふわっとしたもので問題を解いているので(○○の△△は二分探索(を疑う)みたいなトリガーを記憶しておくことも適切に引き出すこともできなくて、二分探索の雰囲気がするから二分探索をしている。例「二分探索っぽさがあるよね」)、式を操作したり式を見て糸口を見つけるということが苦手というか、まったくアプローチができていない。そういう苦手を突くという点で類題だと思った。この問題では２の冪乗というものについて、足し合わせてみたり、足し合わせたものをまとめて割ったりするとどうなるかな、何の問題もなく個別に計算したのと同じ結果が手に入るなということを確認するだけで解答が書けた。昨日まではそれができなかった。ある範囲の連続部分列の和が Sr-Sl であると、それが mod を取ったあとだとどうなるか、それをどうするかと考えてみることができなかった。そういうアプローチが存在していなかった。
