得られるスコアの期待値を mod 998244353 で求めてください。」という問題文の直後に折りたたまれて補足説明的な感じで「
(前略) R×Q≡P(mod 998244353) かつ 0≤R<998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。」と書かれていて、答えの範囲が疑問の余地なく書かれてはいるんだけど、mod 998244353 で求めてください、という本文に立ち返ると 3 (mod 2) って 1 (mod 2) のことではなくて 2 を法とするとき 3 と 1 が区別されないってことなので、998244353 以上の答えがなんで間違いになるのかなという気持ちになる。一方で、OLE という最レアジャッジがあるので無制限にリソースを奪われる心配もないはずだけど、ジャッジのコストやプログラミング言語の整数型サイズなど現実的な判断として 0≤R<998244353 の範囲で一意に決まる数(R)を答えてくださいという要請も理解できる。ただし真の値を 32 ビットの範囲に丸める便宜的な(本来の意味で姑息な)やり方ではあると承知していていい。最近読んだ「新しくプログラミング言語を作る際に数値型をどうするべきか」みたいな話で、今の当たり前がいつまでも当たり前ではないと思うし、ましてや今の当たり前から外れることが「キモい」なんてことはないはず。
放射線内？ と 直線上？ と 外部？。１つ前の提出 #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 なんだな。そのくせ、よそ者として文脈を共有しないで他人が書いたコードを眺めてるときに限って「変数名に型名を使ってる」とかを批判的に見てしまうわけだ。勝手な。