D[a][b]==INF だと考えてしまっていた。考えなかったわけではなく、勘違いしていた。無条件に c 書き込んでいいのか一瞬考えて、問題ないと判断していた。■無向グラフにワーシャルフロイド法を使用するとき、ループの回数を半分にすることで TLE の可能性を減らすことができるのは、ABC369-E を通して刻み込んだ学び (20240831)。■C 問題と E 問題についても書きたいけど、まだ解けてないので書けない。■精進２。ARC185-A mod M Game 2 (緑 diff)。すぐにむりむりわからんと投げ出したくなるけど、緑 diff だというのをもう知っているし、テストケースの多さからもシンプルに解けるのがわかる。ちょっとこらえて視覚的に考えてみると (M おきに印が付いた数直線にそって場のカードの和を表す棒グラフが伸びていくイメージ)、そのときどきで出してはいけないカードが高々１枚しかないとわかる。N<M だしね。最後の１枚になるまではどちらも絶対に負けない。2N 枚のカードの数の和で Bob の負けが判定できる。これだけではサンプルが合わなかったのでまだ考える。Bob が最後の１枚を決め打って温存するなら、Alice が N 枚目のカードを出したときの場の和を Bob が N 通り選ぶことができる。その N 通りに M の倍数が含まれるなら Alice を負かすことができる。Bob はその１枚を最後まで温存できるのだろうか。できるに決まってる。出してはいけないカードはあるけど出さなければ負けるカードはない。そんな当たり前のことも確認しなければわからない。提出 #58815966 (AC / 121 Byte)。かけた時間で判断すれば 300 点問題。事前知識を考慮して高めに見積もっても 400 点。<追記>できるに決まってはいなかった。２枚持っていて一方が出してはいけないカードならもう一方を出すしかない。温存できるの？</追記>■精進３。ARC185-B +1 and -1 (水 diff)。右の要素の高さを左に寄せることで右上がりの坂を作る。右に寄せられるなら何の問題にもならないけど、左にしか寄せられない。制約から判断して要素を左から見ていくことにする。二度見三度見は許されない。ネックになるのは、均した結果がある高さになるとしてその右側がへこんでしまうのがいけない。そのへんをうまくやるために４つのパラメータを記録した。すなわち、(現在の要素までの総和、均してもこれより低くできない高さの最大高さ、その位置、その位置までの総和)。提出 #58816249 (WA / 294 Byte)。A 問題から 31 分でまずは WA。提出 #58816379 (AC / 295 Byte)。その修正に 15 分。小なりを小なりイコールに修正した。文字にして初めて思ったけど、なんで小なりと equal がくっついてひとつの言葉を作ってるの？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 を足してるのかはわかりません。差分が生きるような気がしたけど、気の迷いだった。