例えば 1,173,9090 は “Neq Number” です。」とあるが、１と１が並んでいるのに Neq Number であるとはどういうことかと、Neq Number の定義を何度も何度も読み直してしまった。この日記を書いている今気がついたことだけど、３桁区切りと４桁区切りが混在している不自然さを読み取らなければいけなかったのですか。■C 問題「Not Median」。どういうときに区間の幅が伸びていくかというと、ある数の左側にある数列が、ある数との比較において高低高低高低高低……と並んでいて、反対側には低高低高低高……と並んでいるときに、どういう区間を選んでもある数が中央値になることが避けられない。問題は、そういう均衡を破る最初の位置を効率良く見つける方法。過程を飛ばして結論を書くと、高高となる位置と低低となる位置を記録する２本の BIT を使った。高低は相対的なので処理順を１から N の順にした。そうすると最初は低低の位置はどこにもなく、すべての位置が高高の並びになる。これをスタートにして BIT を更新しながら答えを計算した。ところで、左右の端にある要素については効率良く数える方法がわからなかった。例えば入力が
4 3 5 6 2 1 7 で、４を中央値にしたくないとしよう。４との相対で数列を書き直すと 4 低 高 高 低 低 高 となる。高高や低低の並びを検索したとしても項数を奇数に揃えた途端に釣り合いがとれて４が中央値になってしまう。4 の左に低もしくは高のどちらでも存在していれば即座に答えが確定できるのだけど。だから両端の要素については線形時間を使って答えを出した。■B 問題「Make Many Triangles」はね、解ける人は 30 分くらいで解くみたいだけど(Ruby では２人)、自分にはさっぱりだった。３点以上が乗る直線を引いてグループを作ったとして、どういう規則でトリオを作っていけばいいのか、そういうやり方で答えが出せるのか、何もわからなかった。複数のグループに属する点の扱いもわからなかった。■■■@2024-03-14 B 問題。E8 さんの解説画像を見ました(それと類人猿の人の)。ダメなケースから考えていけば良かったみたい。たとえば、全てが一直線上に乗っているとき、三角形は１つも作れない。では１つだけ直線から外れていたら？ 直線上から２点を選んで１つだけ作れる。以下順々にくりかえし。直線上の点が先になくなったときは、直線上にない点を選べばいいんです(※)。テキトーに３点を選べば大体の場合において三角形は作れるんです。だから作れないケースから考えている。そのためには最も多くの点が乗る直線を１本見つければいい(※)。提出 #51223271 (AC / 272 Byte / 342 ms)。へー、なるほどねー。ネタバレを読んだあとではいくらでも知ったかぶりができますけどね。当日は早々に見切りをつけて C 問題に専念していたわけで、次にこのような問題が出るときも、やっぱり途方に暮れて全く手が出ないと思うな。■※を付けた２つの部分に飛躍がある。自分では超えられない飛躍が。たとえば直線上の点がなくなったとき、他に選べる点が他の１つの直線に乗っている点だけだった場合は？ わかりやすく２本の直線に半分ずつの点が乗っているとき、交互に２個と１個、１個と２個で組を作っていけば無駄なく三角形を作っていけることはわかるけど、いつでもこんな風にうまくいくだろうか。１本の直線にだけ注目して答えにたどり着くことが、やっぱりまだできない。