脳log[20230617]

2023年06月17日 (土) [AtCoder] 今日はトヨタ自動車プログラミングコンテスト2023#3(AtCoder Beginner Contest 306)があったけどジャッジが詰まりまくっていて Unrated になった。「このコンテストは full-feedback 形式のコンテストです」が嘘だったからかな。終了後 20 分経つ現在でも時間内に提出した F 問題が WJ のまま止まっていて生殺しの状態なのだ。今日は既視感のある問題ばかりで 36 分で E 問題まで通ったのだけど、そこから１時間ちかく誤読した F 問題を考え続けていた。■F 問題「Merge Sets」。方針はすぐに立った(この方針が正しいかどうかはまだ不明)。集合を全部まぜまぜしてソートして、ある要素の後ろに何個の要素があるかを二分探索で調べる。つまり、ある要素が他のいくつの要素の添字を押し上げる効果を持っているかを計る方針。ところでね、f(A,B) の計算において A と B は可換ではない。そして求める総和というのは i<j であるすべての f(Si,Sj)。だけどずーーーーっと i<j を区別しない f(Si,Sj) について考えていた。最後に割る２すればいいんじゃないのって考えていた。■制約について１つ気になって確認したことがある。A∩B が空集合だとは書いてあるけど、つまり A と B に共通する要素がないとは書いてあるけど、A の中、B の中に限ったときに共通する要素がないとは書いていなかったと思う(※)。だから添字を使って同値の要素に便宜的に大小関係を導入したんだけど、誤読が明らかになったときにソート列の二分探索から BIT を使う解法に変わったのでそんな面倒な手順は必要なくなっていた。提出 #42363020 (AC) に残ってるのは虫垂みたいなもの。この日記を書いてるうちに AC の結果が出ていた。もう終了から 40 分経ってるよ。ちなみに誤読なしでストレートに実装するとこれだけシンプルになる>提出 #42370906 (AC)。■コンテスト成績証。へなちょこに Unrated を嘆いたりやる気を削がれたりしている暇はないのだ。順位表の１ページ目にいる人たちなんて最初から Unrated なんだから。各色相当の実力があればなるべくしてその色になる。Unrated ばかりならその機会がないけど現状はそこまでひどくない。がっかりするのは上振れに期待しているから。毎回青パフォ以上を出せばいいだけ。建前はそう。でもそれができないのだから、調子がいいときに Unrated なのはつらい。■※「A と B に共通する要素がないとは書いてあるけど、A の中、B の中に限ったときに共通する要素がないとは書いていなかったと思う」 やっぱり書いてあったのかなあ。部分文字列の定義は連続するかどうか曖昧だけど、集合の定義は多重かどうか曖昧ではなかったりする？ 反則的だとは思うけど「A={Ck1​​,Ck2​​,…,Ck∣A∣​​} となるような k1​,k2​,…,k∣A∣​ をとる」ことが曖昧でなくできることから逆説的に重複する要素がないと判断できる？ ……あった！ 「i1​!=i2​ または j1!=j2​ ならば Ai1​,j1​​!=Ai2​,j2​​」って書いてある！ とことん読み違える問題だったなあ。