.keys 抜けが１つと L[] 抜けが３つだけと実装も素直。根からの距離を BIT で、LCA をダブリングで求めた。根からの距離をセグメント木で管理するなら LCA もセグメント木で求めたらいいと思う。BIT+セグメント木は無駄だし面倒すぎるのでナシ。だってセグメント木は BIT の上位互換でしょ？■提出 #39951562 (TLE×24)。試しにセグメント木で根からの距離の累積和と LCA の両方を管理してみたら派手に TLE だった。累積和は BIT でやる方が軽いのかな。■提出 #39954631 (AC / 3966 ms)。頑張りました。セグメント木にダミーの０番目の要素を入れて添字計算の微調整を省いたり、&:method 形式は Symbol#to_proc が呼ばれるせいなのか知らないけどやや遅いみたいなのでブロックを渡すようにしたり、せっかくセグメント木で累積和を管理しているのだから根からの距離を求めてから LCA を引き算するのでなく LCA からの距離を直接求めたり、オイラーツアーで作成する配列のサイズが 3N くらいになっていたのを節約して 2N に抑えたり。最初の AC だったなんちゃって HLD よりよっぽど厳しい。■モノイドが乗せられるようにまじめに ST クラスを改良したので、クラスを書く時のマイルールを。まずクラス利用者が知りたいであろう public インターフェイスを書いてから部外秘である private メソッドを並べる。public メソッドの中では、最初に呼ばれるであろうコンストラクタ(イニシャライザ)をまず書いて、つぎにアクセサ(読み取りメソッド)を書く。最後に、なくてもいい存在であり有害にもなり得るので書きたくないミューテータ(内部への働きかけ)を書く。クラスはオブジェクトのテンプレートであり、型通りの処理(不変部分)を書く場所だけど、ではオブジェクトのアイデンティティがどこにあるかというとコンストラクタへの引数でありインスタンス変数(メンバ変数)にふるまいを変える固有の値(可変部分)がある。すべてのメソッドがインスタンス変数に依存するべきだというのはそのため。その依存がないならメソッドの置き場所が間違っているサイン。とかとかいうことを考えながらクラスを書いている。あとはまあ名前だよね。よく言われるように名前重要。ソフトウェアという形のないものにはっきりした輪郭を与えるのは名前。適切な名前さえあればその実体をどう実装するかはどうとでもなるしどうでもいい。好きに、うまくやればいい。コーディング対象として適切な抽象に紛れのない輪郭を与える唯一無二の名前を見出すところが決定的に重要(形容詞増し増しで強調しました)。自分が常々疑問なのは、変数名に型名を使うというひとつの典型パターン(var arr = new Array; みたいな)。そりゃね、飼ってる猫が１匹だけならその呼び名はネコでも十分わかりますけどね、それは消去法や文脈でそう判断できるというだけであって、直接的な命名ではない。解釈や判断という余計なステップ、疑問や誤解の入り込む余地がある。クラスではなくインスタンスの、それそのものの本質を掴んだ命名をするのだ。■いやでも適切な命名は文脈に依存するということも言えるんだよな。識別子が機能するためには他と区別するのに十分な長さを必要に応じて使うのでいい。１文字変数を使い切ってから２文字３文字変数を使う、みたいな。ハフマン符号的な。その対極がたぶん Java の説明的で長ったらしい命名で、自分は HTML の p タグとか好きでいっぱい使いたくなる人間だからどちらかといえばアンチ Java なんだな。そのくせ、よそ者として文脈を共有しないで他人が書いたコードを眺めてるときに限って「変数名に型名を使ってる」とかを批判的に見てしまうわけだ。勝手な。p X を答えにしているが、正しくは p X%M。■終了後の提出 #39648781 (AC)。mod M の世界で A-1 で割りたいけど A-1 の逆元を掛けることができない。どうするか。以前にやってるんだよな。「L 問題だけが解けずに残っていた。余りをとる M が合成数でなければ 9 の逆元が使えて解けるんだけど」。Ruby なので (A-1)*M が 70 ビットになっても気にしないよ。D 問題で時間を使いすぎて 30 分ちょっとしか使えなかったのも悪かったな。■■■D 問題「Tying Rope」。ロープを分岐なしで繋いでいった結果、輪っかがいくつあるかと直線がいくつあるかを答える問題。それだけの問題。■最初の提出 #39629872 (TLE)。40 分かけてこねこねした謎処理が TLE になりました。■２番目の提出 #39631843 (AC)。その後７分ででっちあげた UnionFind が AC でした。どうして当たり前の問題を当たり前に解けないのか。■心当たりはある。道に迷ったとき、とりあえず引き返せばいいものを、前に進んで知っている道に出ようとする子供だった。来た道通った道を２度通るのは退屈なことだ。ABC292-D「Unicyclic Components」、ABC291-E「Find Permutation」、ABC285-D「Change Usernames」というように似たような見た目の問題が続いていたので、似たような解答を書くのには抵抗がある。それで間違えてりゃ世話がないってもんだけど。■提出 #39651186 (AC)。謎処理でも通しておきました。謎っていうか単に左右のノードをたぐるだけなんだけど、だけど、定型から外れた途端に間違えるんだなあ。■■■@2023-03-14 E 問題の問題名って等比数列の意味だったの？ 英語名難しすぎる(等比数列・等比級数が幾何～と呼ばれるためには何かエピソードが求められると思う。三角数……と考えてもみたけど、それはむしろ等差数列に近い)。そうすると A-1 で割るっていうのは等比数列の和の公式の分母にある r-1 (あるいは 1-r) のことだよね、たぶん。自分は A 進数で 111...1 で表される数字を 1000...0 から求めるつもりで式を立てたけど、意外な繋がりがあったもんだ(決してぼんやりしているから意外に感じられるのではない)。■■■@2023-03-14 D 問題に関連して Dancing Links という名前を初めて見たと思ったら、全然別のところでも Knuth 先生の名前とセットで見かけたりして。どうして今日一日だけそんなに有名になったのか。夜間に出荷したご注文は翌日発送扱いとなります」との定型文があるけど、これをどう考えればいいのか。■可能性１。発送メールの通りに発送されたあと２時間で届いた。■可能性２。夜間に出荷され注文ステータスの更新を見逃した。発送メール送信は翌朝に繰り延べられた。翌日発送扱いになるはずだけどヤマトがすっごく頑張って翌午前に届いた。■可能性３。発送メール前日(発売日当日)の日中には出荷・配送されていて、発送メール時点では配達拠点に届いていた。注文ステータスと発送メールが嘘。■さあどれだ。あるいは４番目があるか。■あとね、些細に見えて毎回導線の途切れにひっかかってしまうんだけど、出荷メールから注文履歴に飛べない。そこがすべての起点であるのに。１クリックでヤマトのページで荷物の追跡情報が見られないのも地味に残念。どちらに至らない点があるのかはわからないけど。
スマートフォンとケースを１つずつ買うと１１０ドルになります。スマートフォンの値段はケースの値段より１００ドル高いです。ケースの値段はいくらですか？」 １１０という数字を反射的にキリよく１００と１０に分けると間違える。こういう問題を 20230203 のときの簡易版職業適性テスト(Gテスト)の検査 C (数理)で見たぞ。残念ながらその手のひっかけは中１のときに散々間違えたあとだ(「100gの水に 5gの NaClを溶かしてできる食塩水の質量パーセント濃度は？」という問いに 5%と答えてしまうおバカな中学一年生でした」)。20230203 のときも実は一度ひっかかったけど逆方向に検算するのが習い性なので(答えを出す前に)訂正できた。以前に「ぶつかってそれではダメだと気がついたら定義に立ち返ってひとつひとつの手順を確かめながらたどるのが方法。ここでは注意が必要だと学習したから立ち止まって確かめることができるというだけで、失敗しないうちや失敗を回避できるようになれば、やっぱり中間を飛躍して答えに飛びつく高速のパターンマッチングの出番だと思う。それが人間の基本で、トライ＆エラーで最適化を重ねた結果が思慮や洗練として見えているという気がする」と書いた。2011 年のベストセラーらしい『ファスト＆スロー』(ダニエル カーネマン)がすごくおもしろそう。それでね、定型発達であることの不幸は、エラーに遭遇する機会の少なさにあると思うんだ。短絡思考を修正する機会に恵まれていない。■■■@2023-03-11 日本語の話。116 ページから「
20世紀前半の哲学者たちはヒュームの論述を深刻に受け止め、道徳的言説が論理に関するものでも経験的事実に関するものではないとしたら、いったいどういう意味があるのだろうかと悩んだ」。さて、この文は道徳的言説が論理に関するものであると仮定しているだろうか、そしてまた、経験的事実に関するものだと仮定しているだろうか。■「～でも～でもない」の形であれば迷いなく論理に関わるものではないし、経験的事実に関わるものでもないと読み取れる。では実際に見られたように「～でも～ではない」の形はどうだろう。自分は意味を変えずに次のように語を補うことができると考えている。「(たとえ)～で(あって)も～ではない」。そう書いてあるのだろうか。同ページの直前の文がこう「
確かに道徳的言説は、論理的言説とも経験的言説とも区別しなければならない」。論理的言説と経験的言説はそろって道徳的言説と区別されるべきものだと書いてあるのであり、道徳的言説が仮に論理的言説であっても、というのは話の流れに合わない。「～でも～ではない」をどう読み取れば良かったのだろうか。もとはの違いが大違いなのではないか。
Personal Identification Number (クレジットカードなどの) 暗証番号」だって。識別されるものは人ではないし(口座？)、識別に用いているのもカードであって数字ではない。PIN のどこに personal で identifying な要素があるのか。Card Number もしくは Device Number が相当では？
AB+CD=N」が４、５回読んでも理解できなかった。サンプルにヒントを求めても解答例が理解できなかった。つまり、A=12、B=34 だとして、AB=1234 だと読んでしまってそこから抜け出せなかった。A×B+C×D=N の意味ではないかとようやく推測できて、その解釈でサンプルが理解できることを確かめても、まだ半信半疑で問題に本腰を入れられなかった。問題文が難解。■D 問題「Unicyclic Components」。UnionFind をするついでに辺の本数を数えた。グラフの性質を踏まえたかっこいい解法で解きたいなと思ったけど、最近あほなので愚直にやった。■E 問題「Transitivity」。最初はダメ解法に捕まってしまった。こういうの。ある頂点を見て、入ってくる頂点と出て行く頂点の組み合わせを考える。すでに両者に辺が通っているなら操作はいらない。そうでなければ直通辺を足す。このやり方でやるとサンプルの３の答えが 17 と過大になってしまった。自分としては珍しいことだけど、そこで一旦リセットしてイチから別の解法を考えてみた(出口のない泥沼の数合わせに終始するのが見えてしまって瞬時にうんざりしてしまったのだ)。ある頂点から到達できる頂点というのは、必ず直通辺が通っていなければいけない頂点なのであって、距離２以上の頂点が操作の対象。有向辺なので問題は始点に選んだ頂点ごとに独立。足がかりに使う距離１の隣接頂点も無関係。N の２乗が通る制約なので全頂点を始点にして BFS をした。■F 問題「Regular Triangle Inside a Rectangle」。辺の長さが１の正三角形をちょっとずつ回転させて外接する矩形の大きさを調べた。そこから矩形の拡大倍率を求めたんだけど WA×10 が解消できなかった。二分探索をするのだと見かけてテキトーにでっちあげてみれば WA×43 と悪化していて AC が遠い。水 diff ですってよ。
i&-i で。部分集合の列挙は b = bits と初期化してから b = bits&b-1 で。メインはメモ化再帰。やりやすいからこういう方法でやったけど、必要以上にテクニカルなことをしているつもりだった。しかし TLE。■２番目の提出 #39380194 (TLE×1)。これのアイディアは１つで、左の子集合(L)と右の子集合(R)に L<R という大小関係を仮定して L>R の場合の再帰呼び出しを省いた。省いた分は ×2 で辻褄が合う。■提出 #39381113 (AC / 4266 ms)。これのアイディアは２つ。１つ目は前の提出のアイディアの改善。L<R を仮定しているのだから最初から列挙回数を半分にすればいい。２つ目はコードテストで数百 ms の効果があった(けれど単体では TLE 解消に少し足りなかった)チューニング。ビット列に対応した重さを予めメモする部分のコードで、いちいち各ビットが立っているかどうか調べるのをやめた。■(オーバーヘッドが大きい) Hash を使うメモ化再帰をやめて Array を使うボトムアップの DP に書き換えるとさらに改善するだろうけど、それは遷移がわからなくて書けない。