i 番目 (1≤i≤N) の候補者はその候補者より多く票を獲得した候補者が M 人未満であるとき、かつその時に限り当選します」について。当落を分ける分岐点がどこにあるかをしっかり把握しなければ二分探索の判定関数が書けない。人 i の得票が上から M 番目の人の得票に並んでいるとき、人 i は当選する。逆にいえば、上位 M 人の全員が人 i の得票を１票でも上回っていれば人 i は落選する。判定関数はこう。答え X を二分探索するとき、X を除いた票を上位 M 人に配って底上げした結果、M 人全員が
A[i]+X+1 以上になるなら、判定は偽。落選する。では M 人全員を A[i]+X+1 以上に底上げするのに必要な票数がどう計算できるだろうか。自分は最初 M 人の中間獲得票数の合計と追加票の合計で平均を出すような計算をして間違えた。平均は出さなかったけど、M 人の総得票数だけで考えて間違えた。トップの人が過剰に票を持っていたとしても、その余剰分を底上げにまわすことはできない。じゃあ M 人のうち何人が中間時点で A[i]+X+1 以上の票を持っていたかがわかればそれらの人を除外して累積和で必要な追加票数がわかるね。これは解の二分探索の中でさらに行う二分探索であって TLE だった。提出 #58232088 (TLE×19)。これが 22 時 22 分。昨日のコンテストはここまで。■提出 #58278984 (AC / 456 ms)。解の二分探索をやめました。X 票を人 i を含む M+1 人に分配したとして、底が上位 M 人のどの人とどの人のあいだにあるかを二分探索した。さっきの二重の二分探索の中の方を外に出した感じ。18 行目と 19 行目にある、不可判定(-1)と無条件当選判定(0)であるとか、15 行目と 20 行目にあるボーダーラインの -1 だとか、こちらの解法にはさらに罠が多い。TLE になった log ２つの素直な解法とランダム入力に対する答えを突き合わせてデバッグをした。ま、ボーダーラインの方は目指すべきグラフ(ヒストグラム？)の形がイメージできていたので間違えなかったけど。■提出 #58279635 (C++ / AC / 303 ms)。これは log ２つの、解を二分探索する素直な解法の C++ バージョン。C++ では log^2 が許されていたのだ。■制約に殺されたというにはしっかり難しくて満足できる問題だった。いや実際に制約に殺されてるんだけどね、お前に殺されるなら悔いはない。過去２、３回の経験に加えて今回も言えるんだけど、log １つの差って、ちょっとした視点の違いなんですよ。ちょっと見る角度を変えれば２つ目の log は消える。これが Pairs の教え (20210401p01)。■■■二分探索を尺取りで置き換えることで計算量のオーダーを改善する常套手段にのっとって、ついに二分探索の log を２つとも取り除いた。提出 #58342253 (AC / 970 Byte / 313 ms)。これでますます制約に殺されたとは言いにくくなるんだけど、これがコンテスト時間内にすらすら書けるなら青といわずとっくに黄色になっている。b = [m,[k-m,10].min].min)。多数派が b より多くなると多数派の真贋が決まるので、即座にグループを閉じて次の要素からまた新しいグループを始める。グループが多いほどグループをまたいだ比較をせずに済んでクエリが節約できる。まだあった。グループを処理する F 関数を実装しているときに、残りの要素の真贋が同数のケースに対処する必要があると思った。未判定コインの中に本物と偽物が同数ある場合。多数派がないからお前が偽物だ(本物だ)と決められない。これはすでに真贋が明らかになっている要素との比較で対処することにした。F 関数の引数 hint がそれ。この対処が実際に必要だったかどうかはわからない。たとえば 890 回のクエリで 979 個の本物を見つけたときに(※10 回のクエリで 11 個の本物が見つけられるのでした)、残りのコインは 10 対 11 であって、問題なく判別できる。残りのコインが９対９になるとか、８対８になるとかのクエリの成り行きが、N=1000,M=10 というパラメータに対して存在しているかどうかはわからない。ビル i とビル j の間にビル j より高いビルが存在しない」という i と j のペアを数えるんだけど、えっとね、i のビルの高さはなんにも関係ないんだよ。サンプル１の解説とサンプル１の出力例を突き合わせて自分の理解の誤りが明らかになったのが 22 時 20 分だったのだ。出力形式もやっかい。合計じゃないんだよ、さりとて j を基準にした数字でもないんだよ。問題を解く筋道を規定されるようでとことん振り回された。解法は後ろから見ていって増加列の列を管理する。いや……ただの増加列なのか。無駄なことをしたかも。■E 問題「K-th Largest Connected Components」。一読してスター型のグラフに殺されるなどうしようかなと考えたときに k が 10 以下との制約が目に入って解けたと思った。連結な頂点のことを隣接頂点だと勘違いしていたのに気がついて途中で UnionFind を(頭の中から)ひっぱり出してきた。連結な頂点に自分自身を数えることも最初はわかっていなかった。Array#max メソッドの戻り値がソート済みではないと知らなかった。そんな感じで実装に 15 分。D 問題のせいで解ける E 問題を落とすのは悔しすぎるので残り 20 秒で間に合って良かった。■F 問題「Teleporting Takahashi 2」。30 分から１時間を残してじっくり考えたかったけど、すべては D 問題のせい。■F 問題。K×N の表を作成していて、K と N がどちらも大きいんだけど、k 行目の値を決めるのに斜めに k 項の和が欲しい。k の２乗はダメだ。左にあって一番近い意味のある頂点が t 個前にあるとして、k-t 番目の値を参照すればいいのかな。■■■F 問題。TLE×8、TLE×27、TLE×12。なんで最初が一番ましなのか。最初だけ送っていて、あと２つはもらっている。TSP 問題ではもらう方が速いのだけど、逆に遅くなる理由がどこにあるのかわからない。■AC！ でも Ruby の他の提出では全部で４つの AC がいずれも 1500 ms 前後しかかけていない。自分のはやっとで 2055 ms。25 % 遅い。正直なにが AC と TLE を分けたのかもわかっていない。他の人の提出を読んだ(眺めた)けど、なんか遷移がシンプルだよね。DP のために用意する配列のサイズが N+K だったり N から継ぎ足して N+K だったり、最初から最後まで N だったりもする。自分は 2M×K の２次元配列(※)を使った。明らかに何かが違って効率が悪い。むむむ。※ C 言語では２次元配列と配列の配列(jagged array)を区別するけど、Ruby には片方しかないので……。■たぶんだけど、ある頂点の場合の数を記録している添字をずらしていくことで１つ先への移動をノーコストで行うんだと思う。初期にはそういうことも考えていたけど、移動したら移動元には場合の数が残らないはずなのに、考え違いをしていて一歩ずつ加算していかなければいけないような気がしていた。今日も実装を始めたときにはまだその勘違いをしていて、過大な答えが出たりしていた。勘違いで解法を潰してしまっていた。提出 #58036342 (AC / 1430 ms)。ほらね、1500 ms グループの仲間入り。提出の中でなんで y から x を引いてまた x を足してるのかはわかりません。差分が生きるような気がしたけど、気の迷いだった。
<< もしくは >> になっているかどうか。これも４、５分かけたんだよね。どうにもすっきり実装できなかった。ソート関数に比較関数を渡すことも考えたけどやらなかった。他の人の提出を見ると、入力から２つを２回選んで比較するだけで答えが出せるみたい。■B 問題「Taro」。b=='F' は無視する。b=='M' のとき a が最初かどうか。これも実装で下手をして次男にも Yes と答えていた。■C 問題「Make Isomorphic」。N の制約が８以下ということで、8!*8*8/2 小なり 130 万なので頂点番号の入れ替えを全通り試すだけ。答えが合わなくてずーっとあれこれしていて、ついに明らかになった原因は、辺の操作コスト A を受け取るときに -1 していたことだった。勝手にコストを減らしてはいけない(二度と役に立たない戒め)。頂点番号を０始まりに補正するコードに引きずられて、コピペでもないのにマイナスしていた。グラフが２つと三角形のコスト表という、入力を受け取るのが一番難しい問題だった。■D 問題「1D Country」。累積和と二分探索。これ D 問題かなあ。二分探索の境界のイコールの有無と、数列の添字と累積和の添字の区別に注意をする。こういうことをどこかで読んだことはないんだけど、C++ の２種類の二分探索が lower_bound と upper_bound なのって、イテレータの半開区間の下限がイコール付きで上限がイコールなしなのを踏まえた命名であって、本来それだけの意味しかないよね？ C++ を離れたら通じないよね？■E 問題「I Hate Sigma Problems」。主客転倒で数字ごとに寄与する範囲の数を数える。ここまで 20 秒かからないのに結局 21 分かけてるのはなんで？ ２つ目のシグマが j=i から始まってると認識したのが遅かった。そこからはまともに範囲の選び方を考える(考え直す)ことができなかった。範囲の選び方が N*N かな N*(N-1)/2 かな N*(N+1)/2 かなと定まらないのは 20240831 とまったく同じ展開。他には余事象を試してみたり、答えが合わないせいでいつまでも思いつく限りのテキトーをやっていた。愚かだ。■F 問題「Takahashi in Narrow Road」。集団を寄せて移動するのは ABC365-F Takahashi on Grid を思い起こさせる。違うのは集団の中ほどで分裂することがあることかな。それでも集団の数は N 個を超えないし、クエリごとに集団の数が０個以上減る一方、増える数は最大で１個なので、ソートした状態で集団(端の位置、幅(=数)、累積数)の管理ができれば良さそう。併合分裂は N+Q のオーダー。でも道具がない。X の値域が広いために BIT で管理するためにはとりうる値が予め列挙できなければいけないが、できない。■■■予め値を列挙しておかなくても自動的になんとかしてくれる BITSet を盆栽したけども、普通に BIT を使う場合より 2.5 倍くらい遅くなった。たとえば制限時間５秒の問題 ABC365-F への提出で 2675 ms かかっている #56361608 が 2.5 倍遅くなると TLE になるんだよね。ABC371-F への Ruby での提出が未だゼロなのは、つまり、あきらめなのですか？ 制限時間３秒だしなあ。■■■F 問題。提出 #57862947 (Ruby / TLE×3)。普通に配列の要素を削除・挿入しただけだけど、35 ケースは通った。TLE のケースが実際にどれだけかかるのか、４秒なのか、30 秒なのか。C++ で map を使ったものは 289 ms で通った>提出 #57864113 (C++ / AC)。C++ で提出時刻が早いものを見てると、LazySegtree を使うものが多いみたい。それはどういう解法か……。■F 問題。Ruby で通った！ 提出 #57872364 (Ruby / AC / 1772 Byte / 1047 ms)。値が大きいから座標は BIT の添字にできないけど、累積人数を BIT の添字にすることはできる。N=9 だとして、座標左から 2,3,4 人の３つの集団があるとすると、BIT の 0 から N+1 の範囲に 0,2,2,5,5,5,9,9,9,9,10 という値を記録する。両端は番兵(提出コードで番兵を使っていないのは(69 行目と 86 行目)、バグがあると番兵が機能しないからなのですね。普通に処理対象にされて削除されてしまう番兵さん……)。座標は累積人数(2,5,9)を添字にして配列から引く。BIT 上の二分探索で隣の集団を見つけることができるけど、対数時間がかかるのをケチってこれも配列(Pv,Nx)に記録した。なんとかなってしまうものだなあ。そうするとコンテストで通せないのは精進が足りないせいってことになる。それは……つらい。■実は累積人数をキーにする発想は C++ で map を利用するときに必要に迫られて出て来たものだった。最初は、座標をキーにしてソートしておきながら、値のひとつである累積人数を参照して二分探索をしたいと思っていたが( T 番目の高橋くんを見つけるために)、そういうことをする比較関数を渡すことはできなかった。それは当たり前の話で、キーについてソートされているなら、キーについてしか二分探索はできない。値である累積人数で二分探索できると思ったのは、座標でソートした結果が累積人数でソートした結果と同じだと知っていたからで、だけど座標をキーにするのも累積人数をキーにするのも同じことだとはまだ気がついていなかった。■■■F 問題。LazySegtree で解いていた何人かが座標を補正することで高橋くんの幅をゼロにしているようだった。なんのこっちゃ。たとえば t 番目の高橋くんが座標 g に移動するとき、t+1 番目の高橋くんは g+1 を下限とするように、t+2 番目の高橋くんは g+2 を下限とするように移動しなければいけないし、逆を見れば t-1 番目の高橋くんは g-1 を上限とするように、t-2 番目の高橋くんは g-2 を上限とするように移動しなければいけないのだけど、t 番目というのを座標に織り込んでしまうことで、全員が同じ座標を目指すことができる。これは BIT を使う場合にも嬉しいことがあって、座標の数が N+Q 個に絞られるので座標圧縮ができる。提出 #57916028 (AC / 1503 Byte / 1366 ms)。最初の提出よりやや短く素直に実装できてるけど、座標の補正(35 行目と 41 行目)がややこしい。特に目的地の補正の必要性と、どう補正するかが、なかなかわからなかった。要するに、今やっとわかったけど、１人目の高橋くんだった～という座標に初期位置をずらし、１人目の高橋くんだったら～という座標に目的地をずらしているのだ。こういうテクニックは過去に２回利用したことがあり、そのときはポテンシャル云々と勝手に呼んでいたけど、今回のように目的とメリットが見えにくいなかで発想するのは難しい。実際に座圧できるというメリットがあったんだけど、テクニックを提示されてさえすぐにそうとは気付けなかった。コンビニ店員やってるときにこれはいやだなあ。コンビニ接客なんぞに自分の大事な人格を使いたくない。ヒト型の機械でありたい。お友達の誘いを断るときなんかにはもちろん理由添えますよ、ごめんなさい暑さで参ってて公園いけないんです（あなたが嫌いなんじゃないよやむをえないことなのよ）とか、でもコンビニの箸ごときにそういう体温入れたくない〜！！！」 要するに、正反対のものを求めているのだ。自分は人間を機械扱いすることに気が咎めるけど、レジの向こうでは機械でありたいと望まれていた。「いりますか」「いらない」を望まれていた。すでにこちらが非人間の扱いだった(自分が欲しい返答しか許容しないというのは傲慢なのよ。機械なら嫌とも感じずにこなしなさい)。自分はこういう人間のふりをした機械には、人間のふりをしているという理由で腹が立つので、さっさと人間をやめて機械になってもらっていいかな。機械の動きしかしないのがヒトの顔を貼り付けて立っていることがもうトラブルの種なんだ。実際にトラブルを起こすと老害って声で埋め尽くされるのを見てきているので自戒するけども。こういうミスマッチがあるなあと「老害」に感情移入して眺めていたのだ。だけど機械になりたがっているとは想像もしなかった。マニュアル人間って、機械にしかなれない人間を指す言葉だと思っていた。元々のツイートについては何が嫌か書かれていないので真意はわかりませんよ。
=> が組み合わさったらハッシュリテラルしか解釈のしようがないやろと期待したのだけど。しかもエラーが Hash の 'key'=>'value' の 'value' の部分を指して「syntax error, unexpected string literal, expecting local variable or method」と出るから意味がわからなかった。'key'=>'value' を 'key'=>value に書き換えたからって有効な構文にはならんやろ。なんかよくわからん => がある、というエラーなら解釈違いだと理解できたのだけど。■B 問題「Binary Alchemy」。1-indexed なのがやっかいといえばやっかい。Ruby での提出を見ると WA がちらほらと、B 問題にしては多い目に確認できて、だいたいどれも元素１に対して元素２から N を作用させているようだった。無視できないレベルでパターン化できそうな間違え方だと思った。■C 問題「Word Ladder」。要素数最小が最初に求められているので、S の各文字を T の各文字に一致させていく操作しかできない。操作には S の文字を大きくする操作と小さくする操作がある。前から小さくし、後ろから大きくする。■D 問題「Cross Explosion」。BIT を使ったけど本当は D 問題に BIT は使いたくない。Ruby での他の人の提出を見ると、同じように BIT を使っている人のほかに UnionFind を使っている人がいた。これはまったく想像がつかない。ほかに BIT より効率的な実装をしている人もいた(#57555275)。■E 問題「Avoid K Partition」。わりと途方に暮れる制約。DP がしたいんだけど、K がでかいし A もでかいので、この２つで状態数を抑え込むことはできない。数列を左から見ていって現在の要素を終端とする全累積和を列挙することはできるけど……。自分が解けなくて４年のあいだ問題を開いて考えて実装しては答えが合わなくて閉じるということを繰り返していた ABC017-D サプリメントに似てるのかな。この問題を思い出して、似てるなら時間内には解けないだろうなと恐れていた。A 数列の２番目以降の要素について、直前に区切りを入れた場合と入れない場合を考えていく。制約を乗り越えるポイントは、区切りを入れない場合に DP 配列をそのまま次の要素にパスできるように状態を記録すること。全体に一律に加算するなら、実際には加算せず加算する値だけを記録する。初期値を決めるところで手間取った。どう初期値を決めても N 個の A 数列を処理すると答えが合わなかったので、最初の１要素を取り出して初期値とした。■F 問題「Cake Division」。完全に途方に暮れる制約。答えの形式から何か手がかりが得られたりしないかな。しないか。■D 問題。BIT より効率的な実装をしようとしたら UnionFind の Find 関数みたいなものを書いていた。UnionFind 解ってつまりそういうこと？ 提出 #57562030 (AC)。各マスに上(下左右)にある壁の位置を記録しておき、このマスに壁がある、というところまでマスを辿る。辿った結果を書き込むことで経路圧縮になる。■■■精進。F 問題。二分探索はわかる。その中で、N 個の切れ目のそれぞれを１カット目とする N 個の累積和について解の判定をするのもコンテスト中にやっていた。そのとき気付かなかったのは、ある切れ目を１カット目とする累積和が最適解を満たさない場合、その切れ目は最適解を満たすどの切り方においてもカットされないということ。つまり答えの２項目目がこのようにして数えられる。そしてもうひとつわからなかったのがダブリング。コンテスト終了後に目に入ってきていた。あとは実装するだけだけど、他の部分が Nlog^2 だからと尺取りできるところで２つ目の log を付けると TLE になるので、オーダーに影響しない定数倍の改善にも励む。■提出 #57605764 (AC / 480 Byte / 4781 ms)。これはコンテスト中には通せません。オーダー的には問題ないはずの提出 #57604731 (TLE×60) がサンプル以外通らなかった。これをコードテストで９秒、７秒と改善していった結果がさっきの AC。定数倍改善に１時間近くかけた。やったことは主に３つ。１．二分探索を尺取りで置き換え。２．N 回のコールバック(ブロック実行)を伴うメソッド呼び出しを N 引数のメソッド呼び出しで置き換え。３．判定関数をこころを込めてインライン展開。コピペをしたくないからペナルティを承知で関数化していたので、代わりにトリッキーなことをしてる(lastcut 変数)。■この問題を DP 的な状態をたたみ込む視点で眺めると、ある切れ目でカットするというとき、それが何カット目であろうとも以降に起こることは同じであり予め計算して結果を流用できるということ。ややこしいのは円環であることから、１カット目の位置に応じてありうる最終カットの位置が変わるということと、１カット目の位置を変えた N 通りを並行して考えないといけないあたり。だけど２周分だけ考えれば間に合う。木全体で一つのvectorに突っ込んでしまえる」「
自分は子への辺を2回走査したが、解説の実装例では1回しかやってなくて」「
最大値を更新するタイミングでそれまでの最大値を（最大値である可能性が今なくなったので）vectorに入れていた」というのを手がかりにして、なんとか１パスで、最大値を取り合うような実装をひねり出した。提出 #57461586 (AC / 321 Byte / 822 ms)。提出したあとでもまだ化かされてる気がしてる。答えが見えなければ実装法も見えない。難しすぎる。■■■けんちょんの解説が上がっていた。「AtCoder ABC 369 G - As far as possible (3D, 黄色, 600 点) - けんちょんの競プロ精進記録」。そこに「
ここで重要な考察として、 K = 2, 3, \dots のときは、頂点 v_{1} を使うものとしてよいことがわかる」と書かれているが、自分が思考停止してしまったのがここで(つまりわからなかった)、K=2 の場合に K=1 の答えを選ばない最適解があるような気がしてしまったのだった。読んでも頂点の位置関係がうまく把握できなかったので自分で考えますよ。K=1 の頂点 V1 とは異なる V2、V3 を青木君が選んだとする。他に根 V0 と、V2、V3 の LCA として C0 が頂点として存在する。V0=C0 の場合もある。いま、V1 と V2、V3 との LCA が C0 より根に近いか、V2、V3 の方に近いかを考える。LCA が C0 と一致する、もしくは V2(V3) に近いとすると、V2(V3) を V1 に置き換えた方が青木君の得になる。置き換えても V1、V2 と V3 との関係は変わらない一方、LCA より先は V2 より V1 の方が長いのだから。LCA が C0 より根に近い場合も頂点を置き換えた方が青木君の得になるし、LCA と C0 との距離の分だけよりスコアを稼ぐことができる。K=3、4... についてはわからないけど、けんちょんのページには書いてありますよ。コンテストのことを考えると難しいのは、「K=2 の場合に K=1 の答えを選ばない最適解があるような気がしてしまった」ときに、それは最適ではないのではないかと疑って、自分の直感を否定するような証明を考えることができるのかということ。できないんだよなあ。たぶんこうでしょで深く考えないのが自分の性分であれば。間違いだとはっきりするまで間違いを疑ってもいいことないじゃない。