A に含まれない最小の非負整数」を 0 からカウントアップしていって、その数字が答えになる操作回数を逆に求めた。それを効率的にやる。
-1.0/0 から -10**12 に変えただけで劇的に改善した。意味的には無限大にしたいし遅いのを知りつつそう書いてきたんだけど、TLE になるほど遅くなるなら制約の範囲外の整数値を使うしかないなあ。■■■精進２。第11回 PAST-I「お片付け」。これも同ブログでデータの持ち方を教えてもらった。自分で書いた TLE 解では文字列化した盤面全体をキーにしていた。だけど記録すべき特徴というのはすぬけくんの位置と荷物の位置という２つの数値だけなんだな。なんでわからないんだろう。■提出 #35384851 (AC / 1950 ms)。制限時間４秒なのでまあまあ。N=10; A=3,4,4,5,6,7,8,9,9,10 のとき、自分の答えが 7 で、AC 提出の２つが 8 を返している。あー！！！ ほとんど同じ構成だけど事前に重複している本を処理していた tinsep19 さんの提出 #35285896 が処方箋だった。最初に見たときは自分も同じことをしてると思ったけど、同じではなかったのだな。■提出 #35324229 (AC / 224 Byte / 228 ms)。すがすがしいほどの完敗だよ。ローカルで小さいケースをいくつも作ってデバッグしていたんだけど(成果なし)、答えを用意する人間が間違っていてはどうにもならない。プログラムは完全に意図通りに動作していたが答えを間違えていた。どうでもいいことだけど提出したスクリプトの変数 read は過去分詞なので【réd】と読みます。どうでもいいね。■勇気づけられるツイート。「アライグマ「ABC271だったのだ！ C問題は最初の方の巻から順に「読みたい巻なら読む。もう読んだ巻なら売る。読みたい巻より先なら、一番後ろの巻から2冊売って読みたい巻を買う」を繰り返せばいいのだ！」 フェネック「それだとA=(2,2,3,4)のときにWAだねー」 https://t.co/Jh41vbHFqP https://t.co/MLXPSXt5tm」 ちなみにこれに「じゃあ答えを二分探索するのだ！」というツイートが続く。この流れも想定の範疇にあった。別の解法なら落とし穴を踏まないのではないか二分探索ではどうかと考えていた。でもそういうときに意地になっちゃうんだよね。最初の解法を修正することに拘ってプランＢが選べない。そういう性質だと知っているし開き直って受け入れている。■■■精進。今日の ABC271-F「XOR on Grid Path」(ぎりぎり青 diff)。半分全列挙の問題が半分全列挙だと教えられる前に解けたためしがない。強いて言えば制約の数字に特徴が現れるが、手掛かりがなさすぎる。■提出 #35327661 (AC / 477 Byte / 472 ms)。最初から半分全列挙だとわかっていればやることはほとんど愚直解法なので。やっぱり TLE だよね、というのを確認していたものを手直ししただけ。■TLE 回避のために半分全列挙でない問題を半分全列挙みたいに解いたことがあるけど、無駄すぎる>20220726。点数とパフォーマンスにつなげたい。
L+1 を L に変更しただけなんだな。off-by-one エラーってやつ。TLE である 04_corner_11.txt はどんなコーナーケースか。ppppp....ppppp だろうことは想像に難くない。■提出 #34804490 (AC / 64 ms)。連続する p を一塊で扱うようにした。一番後ろの p を使わないで得をすることがないので。■■■C 問題「Lights Out on Tree」(水 diff)。与えられた頂点集合の上下関係を知るためにダブリングを書いたり、深さの偶奇が関係するかと思って深さを記録したりしたけど、実は直接の親子関係しか関係しなかった。ボタン操作の基本は「表向いてる親を裏返して、つられて反転した子孫ノードを裏向きに戻すために直接の子を再度裏返す」なんだけど、直接の子が最初に表向きだったノードなら操作回数が節約できる。■提出 #34798597 (TLE×18)。クエリのたびに子ノードのリストをたどる愚直解。■提出 #34799643 (AC / 422 ms)。子ノードは数だけ数えておいて一律に操作回数を計上し、子から親を調べることで足しすぎた分を引く。終了 12 分前に２完のノルマ達成。■■■B 問題と C 問題の配点が同じだから AC の２完遅解きは AB の２完遅解きと同じであり、２完遅解きは A の１完早解きに毛が生えたパフォーマンスしか出ない。-27。ARC にはレートを吸われてばかり。上昇したレートだけ数えたらもう赤なのではないか(頭がパー)。未来のレート上昇を演出するために現在のレートを捧げるのだ。2つの文字列のどっちを前にした方が得か考えてソートするのだ」というのが無意識に作用していた。二項関係だけでソートしていいんだと、知らずに気付かされていた。推移律はどうですか？ よくわかりませんよね。祈りながら提出したら AC だっただけです。■ゴルファーの提出(#34766963)を見てると複素数を使ってるんだけど、そういえば自分が書いたソートのための比較関数が外積と同じ式だった。この前の外積を使う問題(ABC266-C「Convex Quadrilateral」)を自分は複素数で解いたから(#34376180)、なにかしら関係があるのだろうか。ソートからどうして複素数が出てくるのか飛躍がありすぎてさっぱりわからんけど。「（解説を見て）なるほどこれ「Xの個数/1の個数」の降順にソートしてたのか」という声もあるけれど、こちらもさっぱりわからない。俺にもなるほどさせてくれ。
職場に一人はいる」という表現で一人対その他の構図を設定するところが卑怯だし生理的に受け付けない。
center = now #中心 とあるな。……使われてないけど。770 ms と自分の倍くらい速いのなんで？ 直径を構成する頂点のリストを用意して、U から直径までの距離を愚直に(１ずつ)数えてる。１回のクエリごとに高々半径と同じだけの遡行回数で直径に行き当たるだろうけど、それでいつでも大丈夫？ しかしこんなややこしいことをしていて早いし速いし間違えてないのすごいなー。■直径を幹として他のすべての頂点を幹から分かれた枝(※)と見る木のイメージはこれまで持ったことがなかったなあ。※枝の長さは分枝点から直径の両端までの距離のうち短い方より短いか同じ。■提出 #34582537 (tinsep19 さん / 1606 ms)。クエリ先読みもありか。そうか。まねまね>提出 #34647156 (AC / 1826 ms) うーん、遅い。■■■精進２。先週末あった ARC147-C「Min Diff Sum」(青 diff)。コンテスト中に三分探索を書いていたんだけど、そのときも今日も３分点を求める式を間違えていた。(l+l+r)/3 とか l+(r-l)*0.3 が書けなかった。もっとも、それが書けても不満度を妥当な計算量で求めるのがまた難しかったんだけど。この部分問題には ABC の C 問題と D 問題の中間くらいのポジションをあげてもいいと思う。■提出 #34655113 (TLE×23)。三分探索が書けて判定式が書けて不満度の計算ができても、ローカルで６秒かかっているのでジャッジサーバーでは３秒くらいかかると思う。TLE。■提出 #34656235 (AC / 746 ms)。ループの中の線形時間の処理を累積和＋二分探索に書き換えて AC。■提出 #34660104 (AC / 1739 ms)。整理していくと結局区間の左端の数と右端の数を数えるだけになって、三分探索も二分探索も不要になった。速くなるかなと思ったけど倍以上遅くなった。さっきの 746 ms がソート(NlogN)+累積和(N)+二重探索(log^2(N))で、今度の 1739 ms がソート(NlogN)+線形探索(N)。オーダーは O(NlogN) で変わってないけどね、だからこそこんなに差をつけられて、しかも負けてるのが納得しがたい。考察が進んで遅くなるとか……。ローカルで若干速くなってるものがジャッジサーバーでは２倍遅くなってたりするから、ジャッジが詰まりまくってた影響があったりする？ あとローカルでは入力の受け取り方を変えるだけで３秒が２秒になったりした。入力サイズがでかい。■提出 #34661754 (AC / 658 ms)。ちょこっと速くなった。二重探索に対して妥当な改善だと思う。