」という添字の変換をそのまま実装して２回３回と繰り返し適用することにした。AC まで 18 分。照合という語を使ったことについて補足。判定条件が論理パズルみたいでちょっと面白かったよね。A の要素が 1 のとき B の要素が 1 でなければいけない。ということは、A=0 のとき B は何でもいいし、逆に B=1 のとき A は何でもいい。A=1⇒B=1 (もしくは B=0⇒A=0) を確かめる式はA_{i,j} をA_{N+1-j,i}で置き換える
A==0||B==1 になる。これって有名なパズルで、人間は未成年の飲酒を見つけるためならば確かめるべきを間違えないけど、ただの記号の組み合わせだとルール違反を見つけるのが途端に難しくなる。■C 問題「Cards Query Problem」 D 問題に出てもおかしくないような、下手を打つと TLE になりそうな制約と操作。あなたは std::set と std::multiset が使えますか、と問う問題かなと思うけど、Ruby にはない。カードごと箱ごとにソート済みの列と未ソートの列を１本ずつ持つことにした。答えを出力するタイミングで未ソートの列をソートしてマージする。出力する数の合計が 20 万以下に制約されているから、ソートする要素数も、マージ操作のコストも同じレベルに抑えられているはず。AC まで 28 分。方針を決めるまでにすこし考えたし、実装量もそこそこ多かった。実は実装に手間をかけなくても、１つの配列につっこんで出力の直前にソートするだけで十分だったっぽい。出力の総数が制約されているとはそういうことだよな。■D 問題「Writing a Numeral」 これは簡単。各桁の数字と全体の mod を記録していく。クエリ２で引き算をするために 10 の冪乗の余りも並行して記録していたけど、たぶん都度 pow メソッドを呼んでも大丈夫だった。■E 問題「Unfair Sugoroku」 確率の問題。確率とか期待値の問題って方針を決めるところに難しさがある。正解方針が引ければ答えが合うけど、答えにたどりつけない方針を引いてしまいがち。当てもんをやっている。「Boy or Girl paradox」とかモンティ・ホール問題とか、知らなければ避けられない、ヒトが傾向的に陥りやすい誤りがある。方針に迷って F 問題に手を付けるも一時退却してきたときにひらめいた正解方針がこう。高橋くんがサイコロを振って進んだ先のマスに場合の数を書き込みます。各回において高橋くんが初めてマス N に到達した場合の数と青木くんがマス N 以外のマスにいる場合の数から勝ちの確率を求めます。そうして各回で勝つ確率の総和が答え。制約が小さかったので愚直に配列をスキャンして数字を出したけど許された。助かる。■F 問題「Rook Score」 なんかやるだけに見えるけど、やや長めの制限時間３秒が気になる。たぶん想定される落とし穴は、0 以外の数字が書いてある N 個のマス (r,c) のどれかを答えの候補にして他を考えないことだと思う。しかし答えの候補は N 個の r と N 個の c の組み合わせから選ばなければいけない……ような気がする。しかし O(N^2) が許されない制約。どうする。貪欲にやって見込みがなくなったところで打ち切るようにしたら間に合った。それでいいのか？■「アライグマ「F問題は、行和＋列和が大きい順にN+1個チェックすればいいのだ！」」 言われてみればそれはそう。そこまで見極められていなかったから、自分の提出(一応 AC)では貪欲さが足りなかったし、だから tinsep19 さんの提出 #40680322 のようにより厳しい打ち切り条件も採用できなかった。あと、セグメント木で解けるというツイートを２つ見たけどよくわからなかったので考えた。たとえば１行ずつ考えるとして、セグメント木には列ごとの合計値を記録する。行を移るときに同じ数字を二重に計上しないようにセグメント木上の数字を足し引き補正して、それから最大値を尋ねるのだと思う。ST でやったら WA×9 と微妙に間違えた。なぜ？ ST クラスの内部配列のサイズを２べきに揃えるときに埋める値がよろしくなかった>AC。■ACL などまともなライブラリのセグメント木を使ったことがあれば単位元がパラメータ(の１つ)だということがわかったはずだ。この動画を見ていたら op と e の２つをテンプレートパラメータとして渡していて、「あっ、そうなんだ」とお勉強になりました。で、あらためて Wikipedia を読むと「定義……結合律…….単位元の存在……を満たすならば……モノイドという。」と書いてあるわけ。だけどね、痛い目を見るまではそういうお約束的な決まり事って無視しちゃうよね(イケナイ)。■これまでで 15 番目に良い順位だっただけに unrated の無念もひとしお。一入はありふれた漢字の組み合わせで難読。一目で覚えたい。たとえば階層主義か平等主義か、自由主義か共同体主義か、王冠と祭壇か啓蒙主義か、部族主義か世界主義か、悲劇的ヴィジョンかユートピア的ヴィジョンか、名誉を重んじる文化か尊厳を重んじる文化か、集団志向の道徳的基盤か個人志向の道徳的基盤かなど。」とあるが、名誉と尊厳の対立がよくわからなかった。これって同じ側の言葉に見える。思いつく原語は honor と dignity あたりなんだけど、日本語の意味が十分に掴めていないか、日本語にするときに重要なニュアンスが消えてしまっているか、なんにせよ理解が曖昧な部分があるとわかって気になってしまった。雰囲気で違いをでっちあげると、名誉は外から贈られるもので、尊厳は内から出てくるものかなと思ったけど、これまでそういう風に考えたことはないし、それが対立する状況も想像できない。こういうのに答えるの、ChatGPT が得意な分野という気がする。実際の使われ方から意味にあたるものを抽出すること。■■■@2023-04-26 別の本だけど『ファスト＆スロー』(ダニエル カーネマン)の上巻 102 ページから、プライミング効果に関する内容だけどそのことではなくて例示されたものについて。「
世界には、ひんぱんに尊敬を思い起こさせる文化もあれば、神を思い出させる文化もある。また、「親愛なる指導者」の大きな写真を使って、服従というプライムを国民に与える国もある。」 先々週(14日)に書いたように名誉と尊厳の対比はよくわからなかったけど、この本に書かれている２者＋１は、人を上に置くか人の及ばないもの(神)を上に置くかという違いで理解してもいいだろうか。尊敬という一語だけで対象を人に限定してしまう用法に違和感があったけど、明鏡国語辞典によれば「
「尊敬」は多く人間とその行為に限られるが、「敬う」は、尊い存在として敬意を払うべき高位のものに及ぶ（恩師［祖先・神仏］を敬う）。「崇める」は、敬うべき絶対的な存在に向けられることが多い（釈尊［神仏・太陽］を崇める）。」とあるのでむしろそういうものらしい。ひょっとしたら２つの本は同じことを指しているのかもしれないと思った。名誉=尊敬、尊厳=神威。無理か？ それはそれとして、人と神の対比は、神格化される人がいたり神を代弁する人がいたりして曖昧に感じる。それよりも、人であるか神であるかにかかわらず自分の上に他者を置く心性、分を弁え身を修め奉仕する心のありようが共通していると思った。日本人が外国人に対して「無宗教です」と伝えるつもりで「無神論者です」と伝わってしまってやべー奴だと誤解されてしまうというエピソードがしばしば語られるけど、無神論者のやばさって、そういう心性の欠如として理解すればいいのだろうか。アナーキストに近い概念だと説明されることがあるけど、無宗教・無神論に対するイメージが実はよくわからない。無というよりは反で、反宗教的な活動家、みたいな？
得られるスコアの期待値を 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 だったということなので、いじって出し直すと逆に悪化したりする。解答の方針を転換する妙案もなく。