(a-x)*dy<=(b-y)*dx (遅い) か dx * px + dy * py >= threshold (速い) かに由来している。演算子の数が違うからね。だけど３つのペクトルをどう組み合わせれば引き算部分を事前に済ませておけるのかわからない。もうひとつ 10 行目の offsets.max_by もわからなかったよね。自分は辺と点の関係をあっち側こっち側の２値でしか扱わなかったから、値の大小を比較する max_by が選択肢になかった。外積が平行四辺形の面積なら値の大小は高さの大小であり符号と絶対値は辺のどちら側にどれだけ離れているかを表している。こちら側に一番離れている点が選ぶべき代表点であり、それを max_by で選べると事前準備の M 回の繰り返しがすごくシンプルになる。自分の提出は少なくとも２つの点で遅れをとっていた。■というのを踏まえて整理しました。提出 #31797336 (AC / 333 Byte / 1575 ms)。短く速くなった。速さは同じくらいに追いついたけどメモリ使用量がほぼ例外なく 1.5 倍くらいあるのがよくわからない。とくに富豪的な無駄遣いはしてないはずだけど……(多重代入？)。事前計算については意味を考えず単純に展開してクエリと無関係な定数部分を括りだして覚えておいた。c+d を文字列の連結のつもりで書いたけど 7 行目で .chars ではなく .bytes を呼んでるので文字コードの足し算になってしまってる。それだと a と d が位置を交換している場合と b と c が位置を交換している場合など、異なる文字コードの組み合わせだけど和が一致する場合を区別できない。A 問題は運営の想定でセット内で最も易しい問題です」。すっごく難しかったよ。■最初は長さ４の文字列をすべて切り出して「UTPC」との不一致を数えればいいと思った>提出 #31608295 (WA×13)。これはスワップによる交換回数の節約が考慮できていない。■そこで交換が１組ある場合と２組ある場合を列挙した。提出 #31608534 (WA×6)。これはスワップしていない部分が「UTPC」と一致していることを(勝手に)条件にしていて列挙に漏れがあった。■提出 #31608677 (WA×3)。一致不一致とスワップを独立して数えるようにしたら WA が３つ減った。だけどこれは３つ組４つ組が位置をローテートしている場合の交換回数の節約が考慮できていない。■提出 #31608753 (WA×3 / 列挙漏れ)。提出 #31608788 (WA×3 / 列挙漏れ)。■提出 #31609353 (WA×1)。ようやくローテートしているものを考慮することで WA が２つ減ったけど、唯一残る WA は「UTPC」との一致がゼロでスワップもゼロで「UTPC」のアナグラムでもないケース。つまり考え得る最悪のケース。全列挙して数えたけど、実は交換回数の最大は４回ではなく３回だった。■提出 #31609535 (AC)。すっごく難しかったよ。
ds.sum/2 (相当)を ds.sum-ds.max に変えるだけでいけると思ったけど駄目だった>提出 #31435269 (WA×20 / AC ×14)。■今日の提出 #31585826 (AC / 1068 Byte / 1671 ms)。答えをね、見ました。「Hは与えられた点を連結にする辺だけ残した部分木を考えて、それの辺数の2倍から直径を引く」。引くのは目についたテキトーな数字(ds.max)ではなく直径だと。言われれば、うーん、まあ、うーん、そうかもね、という感じ(わかっていない)。木の直径についてはこのとき(20211004p01.02)に一応のイメージを持っていたが、自分では見つけられない。A = 1,1,1,1 のとき答えが食い違う。えっテストケースざるでは？ Yes であるための必要条件ではあるけど十分条件ではないのだな。A.max*B.min と A.zip(B).map{|a,b| a*b } に限定していいのかわからない。この一連のツイートが Day2 の B 問題についてのものだろうか。「@kotatsugame_t これならひっかかってませんか？ https://t.co/CFIYrhdR68」「～のときは、区間は短いほど得なので、長さ１の区間のみで十分です。」 ああなるほどって思えないからこれが関連ツイートなのかどうかわからないんだよね。