S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。 例えば、ab は abc の部分文字列ですが、ac は abc の部分文字列ではありません。」 折りたたまれた用語の説明を読んでいなかった。今回の「部分文字列」は連続部分文字列と呼ばれることもあるものだった。やつあたりに聞こえるだろうけど、知らない人のための用語解説なら折りたたむのも結構だけど、問題の一部としての定義なら隠してはいけないと思う。必ずクリックして開かなければいけないなら(それなしでは問題文が曖昧になるのなら)隠す目的はなんだ。■F 問題。提出 #38104204 (AC / 1984 Byte / 634 ms)。ソースを見るに余裕のなさが窺える。「脳みそに余裕がなくなるとクラスや日本語変数がソースに現れる傾向があるみたい」。日本語をクラス名にするために Class オブジェクトを明示的に new しているとはずいぶんな余裕のなさ(※日本語は小文字扱いなので(=定数ではないので) class 構文が使えなかった)。間に合うみたいだったのでセグメント木はやめて転倒位置をソート済み配列で管理する当初の方式に BIT 26 本の利用を付け加えた。これを時間内に解くのは無理だよ、量的にも。青 diff でした。青 diff ならもう射程に入ってないといけないんだよなあ。■経緯を忘れてあらためて考えると、転倒位置の管理に BIT を使わない理由がないなあ>提出 #38325205 (AC / 1645 Byte / 593 ms)。BIT 27 本。
見えないことは存在しないことではない」■これはまったくその通りで、周囲を見回して人がいないことを確認する、車が来ていないことを確認するというときに、いる・いないの二値ではなく、いる・いない・陰になっていて確認できていないの三値で景色を塗り分けないといけない。いるの否定(=いることが確認できなかった)がいないではないことを認めなければいけない。しかし、すべての免許保持者が NULL を正しく取り扱えるとあなたは信じられますか。私には無理です。
a*Mb-b*Ma という式を複数の速い提出で見かけた。比例式のような外積のような？ 実行前のオーバーヘッドが Ruby 2.7 より小さい Ruby 2.3 であることを差し引いても 12 ms や 27 ms は速いのでは。■提出 #37756578 (AC / 416 Byte / 60 ms)。テキトーにさっきの式をパクってみたらそれでも AC になった。式の意味がわからない。じゃあ最初の提出では何をやっていたかというと、a と b のペアから MA 対 MB の比率ですでに完成した物質 C を取り除いたときに a と b がそれぞれどれだけ過剰かを１つの値にエンコードして DP のキーにしていた。そのキーを例の謎の式にすると a と b の値をデコードする必要がなくなってエンコードした値そのもので演算ができるらしい。謎。[表記] 新聞などでは「憶病」で代用するが、慣用になじまない。」という事情があるらしい。臆が使えない字だという認識はないし、学校で習ったと思うんだけどなあ。漢字テストできっちり区別させられたと思うんだよなあ。■読んでいた本は『会話を哲学する コミュニケーションとマニピュレーション』。とても良い。マンガや小説が題材になっていて、読んだものや積んでいるものがいくつもあってとっつきがいい。タイトルのセレクトにちょっと思うところがあったのだけど、なんとなく納得できるような意外な事実が明かされたりも。全体に言葉を尽くす、言葉を蔑ろにしないという姿勢がくどいくらい徹底している。言葉が他者とのインターフェイス(のひとつ)であることを考えるとそれは他者や他者との関わりを大事にする姿勢と重なる。たぶん題材である学問分野だけが理由ではないと思う。著者のパーソナリティがだだ漏れでちょっと心配ですよ。それも本の味でとても良いのだけど。■@2023-01-04 最後まで読んだ。フィクションから現在へあざやかに繋がりました。ちょっと前にこういう本も読んだよ。『差別はたいてい悪意のない人がする』(著：キム ジヘ)、『子どもに学ぶ言葉の認知科学』(著：広瀬 友紀)。もちろん関連があると思ったから挙げた。
W と M。W 関数は表現したい区間の幅に対して、組み合わせるべき区間の幅を返す。連想配列 M は W 関数によって正規化された区間幅 w に対して、区間 [1,w] が何番目に提示した区間であるかが記録してある。■D 問題「Make Bipartite 2」と E 問題「Choose Two and Eat One」の精進はまだだよ。解けてないんだからしかたないね。残念なことがあったんだよ。■C 問題「String Delimiter」はいろんな解法が考えられて他の人の提出を見るのが楽しいかもね。でも現実問題として CSV を処理しようとするとどんな実装をした場合でも完璧には処理できない狂った仕様の CSV の実在が確認されそうで怖い。提出 #37330344 (AC / 83 Byte / 155 ms)。引用符で分割して奇数番目と偶数番目で処理を分ける、たぶんオーソドックスな方法。入力と出力で文字列長が変わらないことを考えると富豪的ではあるかも。スクリプトだから気軽に split とかやっちゃったけど。■D 問題。こちらのツイート「D dfsで各連結部分の色を塗りわける。色が塗り分けられないときは0。そうでない場合、ある連結成分については「異なる色の個数の積 - 辺の個数」、異なる連結成分通しは無条件で塗ってOK。辺を重複して数えないように注意。」を読む限り考察は完了していたと思う。提出 #37345235 (WA×20)。デバッグするだけだと思ったから E 問題へ行って、帰って来られなかったんだよね。それはそれでしかたがない。E 問題の、ああいう形の繋がり方から全域木が見えなかったことこそ問題。全域木が見えたら持つべきデータの形に頭を悩ませることもなかった。■D 問題。お風呂デバッグ完了しました！ U(nite)関数において引数の２頂点のあいだに辺を張るべきところ、その根と根のあいだを辺で結んでしまっていた(と思う)。提出 #37379282 (AC / 604 Byte / 438 ms)。前々回の ABC280-F が重み付き UnionFind だったんだけど(20221203)、付随データが数値(距離)から二値(偶奇)になったから扱いが簡単になるわけではなく、むしろ距離の場合はベクトルの取り扱い方が使えるところ、0/1 の XOR では取り扱いが手探りになって頭がバグりがち。だから最初の提出ではいったん根からの距離を求めた上でその偶奇を利用するように途中から方針転換したんだけど、すでにバグっていた頭は根からの距離の計算もバグらせた。どっちでやってもバグらせたので AC 提出では当初の方針通り 0/1 の XOR を UnionFind に載せた。連結成分内の辺の数をわざわざ記録したけど、まとめて辺の総数(M)を引くのでいいらしい。■E 問題はもう種明かしを見てしまったので D 問題の UF 実装から難しい部分を取り除くだけでおしまい。提出 #37379631 (AC / 341 Byte / 296 ms)。■D 問題。頭がバグるなら BFS/DFS でやるなり頂点を倍加して普通の UnionFind をするなり(「偶数世界と奇数世界？」)、やりようがあったらしい。しかしまあ、バグる頭は足りない頭でもあるわけで。■F 問題。「FはSparse Tableを作れと書いてある」らしい。たしか蟻本でセグメント木、BIT に続けて紹介されていたのが Sparse Table だった。よくわからなかったので見なかったことにしたが。■蟻本を読み直した＠風呂。セグメント木と BIT のあいだのコラムで Sparse Table が紹介されていた。こういうときに使うんだ、という強みが見えない紹介のされ方だったのであまり理解する努力をしなかったのだ。F 問題の解答を踏まえると Sparse Table のココロがわかった。BIT と比較するとメモリ消費が大きくて、ということは初期化と更新に時間がかかるということ。更新は区間幅(２べき)の和でフルビット(N)だろうか。取得に関して、BIT が対数個の要素を参照しなければいけないところ、Sparse Table は２個の参照で済む。しかしどの要素を参照するかを知るために前後の２べきを求めるのにビット長の線形時間(競プロ的には対数時間だったり「log は定数」だったりする時間)をかけると有利が消える。ビルトインの clz (count leading zeroes) が使えるとビット長の対数時間で２べきが求まったりするの？ なんか上手い配置があったりするの？ そんな感じで、参照に有利な条件が整っているときに強みがあるのが Sparse Table だと思いました。優先度は低いよなあ。■『ハッカーのたのしみ』を開いた。CLZ 相当の命令がある場合があるらしい。ということは __builtin_clz は「悪くて」ビット長の対数時間ということなん？ １命令のコストとかそのレベルからは「すんごく速そう」以外の感想はない。