1 日に複数本の道を使うことはできないことに注意してください」の一文を念頭に置いて考えれば、むしろどうしてこれが問題になるのかわからなくなった。パスとか何日目に訪れたとか関係なく、街の集合を一日一日拡大していくことを考えるだけ。とはいえ制約が厳しい。新しく訪問した街があればそこから移動できる未訪問の街を最初に訪問可能になるのが何日後かをセグメント木で管理した。■提出 #32487113 (AC / 995 Byte / 1952 ms)。2183 ms で TLE になったので 200 ms をミクロなチューニングで稼いでの AC。「Ruby によるすべての提出」を見ると他３つの AC はプライオリティキューを使用していて時間も 1216 ms から 1804 ms と余裕があるようだった。たぶん
W[X] (X 日目に訪問可能になる街の集合を記憶する配列)に相当する役割を担っているんだろう。■提出 #32487597 (AC / 1027 Byte / 1210 ms)。自分でもプライオリティキューで書いてみた。ずいぶんシンプルに書けた気がしたけど、セグメント木とプライオリティキューのコード量の差により実際にはサイズが増えている。こちらの方が簡単に書けて簡単に読めるけどね。それにも関わらずプライオリティキューを使うんだというヒントをもらうまでは思いつきやしなかったけどね。■■■精進２。第６回PAST-K「共通クーポン」。DP ができなくて解けていなかった問題。■提出 #32492522 (AC / 480 Byte / 340 ms)。N の上限が 10 万だけど、N=10000 で TLE になる明らかにまずい DP をしている。ケースが弱い。■提出 #32492799 (AC / 431 Byte / 215 ms)。こちらが正しい DP。これなら前処理を省いても十分に時間が足りたと思う。この問題の入力は DP よりも前処理の方が効果的であるようなものだけど。1 日に複数本の道を使うことはできないことに注意してください」に阻まれている。それを言われてしまうと厳しい制約の三重苦のもとでどういう状態管理が許されるのかわからなくなるんよ。
strong と yowai_sushi ってそういうことか(２本のソート列)。そして、その提出によれば２本のソート列から K-X 個を取るパートはない。１本目のソート列から X 個を超えて取る方が良くなるケースは、X を増加させた後のループで試行されるのを待てばいいのだから、それはそう。そしてだからこそ、40 行目 tmp = intstrong[t] + intyowai[k - t] + t*t において K 個の実際の種類数が t 種類より多くてスコア計算が不正確であっても(不当に低くても)無視して良い。難しいなこれ。ある時点のループにおいてベストを求めなくていいし不正確でもいいということを見極めて受け入れるのは。sk か sk%P かという違い。余りをとるコストをケチってかえって Bignum のコストを支払って TLE になっていたのだった。あほ。■F 問題「Operations on a Matrix」(青 diff)。昨日は問題を読みもしなかった。やることは明らかだけどどう効率的に実装するかという問題。□最初の提出 #32096736 は TLE/MLE になった。長さ 20 万になりうる配列を最大 20 万回複製しようとしていたのだから、40 ギガを数倍したコストが予期される。TLE/MLE も当然。□次の提出 #32097180 で AC。クエリ先読みで必要な値だけ覚えるようにした。典型です。最近では ABC202-E「Count Descendants」を解くときに同じことをした>TLE、AC。E 問題を AC してから 50 分だから、%P を %P とタイプするだけの手間で E 問題を AC に持って行けていれば６完もありだった。幸せな皮算用。n 頂点の木から辺を 1 つ取り除いてサイズ n の連結成分を作ることはできません」ので、Sn が 1 の場合も不可。他には、木において辺とは頂点集合を左右２つの連結成分に分けるものなので、Si と Sn-i が食い違う場合も不可。ここから答えの構築を考えた。大きさ１の連結成分から始めて１つずつ大きくして N/2 までの連結成分を作る。N/2 より大きい連結成分は大きさ N/2 以下の連結成分の片割れとして自動的にできあがっているので考えない。Si が 1 の場合、直線状に伸ばすことで大きさ i の連結成分が生じるようにする。Si = 0 の場合、葉を生やして横に大きくすることで大きさ i の連結成分が生じないようにする。最後に余った頂点をすべて葉としてくっつけて始末する。■提出 #31963209 (AC / 403 Byte / 131 ms)。以前に解こうとしたときは、大きさごとに連結成分を分けてプールして、小さい連結成分を組み合わせることでより大きい連結成分をプールするような処理を考えていた。実はプールする連結成分が１つだけでいいことと、大きさ１の連結成分(葉)がすごく便利に使えることに気がついたので今日は解けた。■コメントアウトしてある部分は、解答と入力に矛盾がないことを確かめるために、解答から入力と同形式の文字列を作って比較している。そのために judge.rb27 を書いた。■ブログを読んでいたら、解答のような木には「キャタピラ木 (Caterpillar tree)」という名前がついているらしい。わざわざ名前を付けて区別して嬉しい理由があるのでしょうね(調べない)。
ans -= N if X == 0 がはまりやすい罠に見える。X がゼロの時、同一頂点をペアにして数えてしまうのを除外している。もしやと思って直前の WA 提出 #2757181 を調べてみるとこれが抜けていたのが原因だった。WA から３分半で気がつくかあ。無理だよ。他に Ruby で解いている人はゴルファーが一人いるだけ。古い問題なのもあるだろうけど、一見して面倒くさく見えるのも影響してそう。■ブログ記事を７つ読んだけどどれも LCA で相殺を利用していた。考える前に手を動かしている脳筋はいないのか、脳筋は。