放射線内？ と 直線上？ と 外部？。１つ前の提出 #40337287 (WA×3) を見るとそれらは 線上？ と 内部？ だった。ちなみに２つ前の提出 #40336676 は WA×2 だからいじって逆に WA を１つ増やしている。その差分から直線と線分の区別があいまいだったことに気が付いたし、その他の原因は便宜上の三角形を用いた内/外/境界線上判定が解答の IN/OUT/ON と１対１対応してはいないこと(三角形の辺が多角形の輪郭線と一致している場合と一致していない場合で分かれる)と、道具に選んだ Complex(複素数) の取り扱い方が不確かだったことだった。１点を原点に選んであれやこれやする、１辺を基準に選んであれやこれやする、というので迷走したし、原点に選んだ１点と (0,0) の区別を間違えたりもした。外積って (a.conj*b).imag で求まるんだなーというのも今回の発見。ただただ幾何判定への正確な理解と正確に実装する力がなかった。■あ、線上？ を 直線上？ に改名したときに絶対値の比較をやめるべきだった。まーだ、実装に間違いがある。あと細かい話だけど、内部？ を not 外部？ で置き換えたのは、内部と線上を区別しないように書き換えた 内部もしくは線上？ 関数より 外部？ 関数の方が(問題から離れて)単体で見たときに有用だと思ったからなんだけど、だったら 放射線内？(線上を含んでいる) も not 放射線外？ として用意すべきだった。不徹底。■ローカルでランダムテストケースを作ろうとすると狭義凸多角形の部分で困るよね。±10 の XY 平面に三角形か四角形をテキトーに拡大して配置して全格子点 441 個をクエリにしてテストした。■CP(外積)、上方？、下方？、線上？ の語彙を使って整理した。提出 #40350677 (AC / 606 Byte / 2254 ms)。a.conj*b って内積も外積も求まるのんな。たぶん複素数って一般性が足りないと思うんだけど(自分は不足を感じられるほど先を知らないけど)、おかげで目的に合致しているとすごく扱いやすいと思う。と、その扱いにすら難儀していた者が申しております。■『デモクリトスと量子計算』(スコット アーロンソン)という本を&:to_i を _1.to_i にしたり、２要素の配列を要素に持つ Hash を２つの Hash に分けたり。蓋を開けてみれば 500 ms の余裕をもっての AC だった。■つぎは day1-H「Attack Survival」への提出 #40291192 が 21 ms over で TLE×1 なのをなんとかしたい。たった 21 ms ではあるけど、ジャッジサーバーで慎重に繰り返し実行してそれでも TLE だったということなので、いじって出し直すと逆に悪化したりする。解答の方針を転換する妙案もなく。<<x と <<y)が雑だったのと、11 行目の判定が早すぎて 15 行目の前にあるのが良くなかった。たった２要素を得るために 20 万要素の配列を作るのが憚られたので Enumerable#lazy メソッドを初めて使ったよ。■「利用できそうに見えて実は始点と一致しているために有効に利用できない場合に注意して」 嘘だよね。長方形 R に２つきりしかない１差の２点の X 座標(Y 座標)の一方が始点の X 座標(Y 座標)と一致していても±２ずつ移動していけるよね。早とちりで No と答えてる気がするけど、テストケースの甘さに助けられたのか？■まだちょびっとだけ理解が及んでいない部分があるらしい。提出 #40200554 (WA×1)。長方形 R の縦と横の長さを最大限に利用して終点を目指してみたのだけど、１つだけ WA になってしまった。どこに考え漏らしがあるというのか。AC はやはり偶然だったのか。■いいや、大丈夫。完璧だ。提出 #40201186 (AC / 506 Byte / 377 ms)。３行目の SY を SX と間違えていたうっかりミスが 1WA の原因だった。考え漏らしはナシ！ 十分に整理して満足のいくスクリプトになった。
勘違いして最初は P-2 を mod にしたのだけど、P-1 にすると具合がいいようだった。」 勘違いしていたというのが勘違いだったみたいで、モジュラ逆数を計算するなら P-2 乗で間違いない。P-2、P-1、P 乗がそれぞれ 1/A、1、A に対応する雰囲気。
.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 先生の名前とセットで見かけたりして。どうして今日一日だけそんなに有名になったのか。