5*4*3*2*1 ではなく 5+4+3+2+1 だから…… n の場合は……１から n までのシグマ k は……わかんない、みたいなあほさで時間をとかしていた。頭が働かないときってあるよね。いつもこうじゃないよ、ほんとだよ。■D 問題「Bonus EXP」。ABC365-D AtCoder Janken 3 が解けなかったときのことを覚えている(20240803)。直前の２状態を記録・更新する DP。■E 問題「Sightseeing Tour」。N が 500 以下ではなく 400 以下であるあたりに温情を感じる。クエリが 3000 以下。クエリあたりの辺の数が５本以下。辺の並びと辺の向きを総当たりすると 3840 通り。3000×3840<1200万は通る。あとは全点間距離を O(N^3) で求めておけばいい。ということを確認してから飛ばした。400^3=6400万は N≦500 だった過去問に比べれば手心が加わっているといえるが、N≦300 でないと十分ではない。サーバースペックが向上していれば結果はわからないが、我が身で確かめるつもりがない。@翌日。たぶん実装したらしたで、今日になるまですっかり忘れていた多重辺への対応漏れで WA を出していただろう。ちゃんと自己辺はないけど多重辺はあるかもって明記してあったのにね。いっつも「単純」だから対応に慣れていない。■F 問題「Gather Coins」。問題自体は難しくない。よくある問題。BIT で列をキーとした情報を管理更新しながら行方向に処理を進めていけば効率的に数えられる。答えを提出しようとしてびっくりしたよね。経路の復元をしなければいけない。情報の持ち方に迷って何度もやり直しているうち、いつの間にか ABC360-G Suitable Edit for LIS でやった LIS の履歴の操作みたいなことをさせられていた(20240701)。提出 #57333067 (AC / 980 Byte / 653 ms)。時間内には通せませんでした。■tinsep19 さんの BIT を使わない提出 #57315658 を見て思ったんだけど、普通に(順方向に)経路を記録しながら LIS をするんで良かったんやろか。やってみた。F 問題の BIT なしバージョン。提出 #57336605 (AC / 690 Byte / 823 ms)。やっぱりやってることは LIS なんだなあ。ただし、履歴が必要。複製せずに履歴を分岐させたいので、リンクリストの頭を継ぎ足していく感じで LIS の記録をした(i を記録したのは無駄だった)。git のコミット履歴的な。そうすると、答えを作成するためにリストを後ろから前からたどらなければいけないややこしさは同じだった。■見たことのある解ける問題が６問並んでいて ABCD の４完は冴えないなあ。■■■精進。E 問題。提出 #57365216 (AC / 694 Byte / 3035 ms)。丁寧に 25 分かけて素直に実装したら、制限時間４秒のところ３秒強で一発 AC だった。Ruby が負っている定数倍のハンデについて認識を改める必要があるのかな。それでも昨日のムーブとしては、解ける問題のうち配点の高い F を優先するので間違ってなかった。両方を解く時間はどのみちなかったのだし、E 問題に至っては Ruby を使っている限りどうにもならない可能性もあったのだから。■精進２。E 問題。提出 #57365396 (AC / 692 Byte / 1965 ms)。前半のワーシャルフロイド部分のループをたぶん半分にしたらケースごとにばらつきがあるけど最大で倍くらい速くなった。無向グラフであることを利用したってことになるのかな。時間外ならこういうのも楽しいけどね。ところで、ループ部分をイチから書き直して、途中で再度書き直したんだけど、その結果が２行だけ数文字だけの差分になってるのちょっとすごい。まるでそこだけちょちょいと修正したみたいじゃないか。ところでところで、最初の提出からそうしてるんだけど、後半部分に D 問題プラスアルファの解答がまるまる入ってるんだよね。D 問題と同じ DP をしている。直後の E 問題がこれでは D 問題さんの立つ瀬がない。■■■取り繕います。普段なら 5+4+3+2+1=15 と 5*6=30=15*2 から、n+(n-1)+...+1=n*(n+1)/2 というふうに左辺と右辺が繋がって、終点と始点が一致していてはいけない場合(nC2=n*(n-1)/2)との区別を確かめてからスクリプトに埋め込むんだけど、最初の階乗のせいで何も考えられなくなった。全体の和(5+4+3+2+1=15)を数えているあいだに何を数えているのかを忘れ、目的を思い出しているあいだに数えた和を忘れるという始末。深刻だ。pop(K) かなと思ったけど、出力のしやすさから rotate(-K) にした。irb で確かめたら rotate(K) ではなかったから rotate(-K) にした。下から K 枚といういやらしい設定はちゃんと読めていた。■ B 問題「Decrease 2 max elements」。偶奇によらず A.sum/2 で間違いないことを確かめたと思ったらサンプルの２に殺された。場合分けをして祈りながら出した。こんなにはらはらさせられる B 問題はそうそうない。あ、シミュレートできる制約なんだ。無駄に考えてしまった。でも 100×100×100=100万のオーダーだと見積もるのも簡単ではないね。■ C 問題「Triple Attack」。シミュレートします。その際に、１周期(T を３増やして体力を５減らす)を超える処理は周期数を数えて一括して計算します。サイクルはどこから数えても１周した結果が同じだということを都合良く利用します。■ D 問題「Minimum Steiner Tree」。シュタイナー木とは見かけた名前だけど中身は知らない。調べませんよ。頂点を輪っかに並べて最小限の頂点と辺を選ぶアルゴリズムがあった気がしたけど、覚えていない。調べませんよ。テキトーに根を決めて、深さを計って、最も深い所から浅いほうへ向かって、必須の頂点を種にして、１つだけの共通祖先に行き着くまで親を取り込んでいくようにした。根に収束していくので頂点数程度の操作回数。テキトーに根を決めていいのか考えたけど、木は頂点間のパスが一意に決まるのでどこが根とか関係なさそう。終了条件を間違えて１ペナ。無条件にテキトーに決めた根までさかのぼってしまっていた。中断するときは、最も浅いところにある指定された頂点を取り込み忘れないようにする。X で見たけど、テキトーに決める根を V1 なり Vk なり必須の頂点の１つにしておけば何の面倒もなかったらしい。それは……頭がいいね。調べないと書いた２つ目は Auxiliary Tree という名前だったと X で見て思い出した。読めない名前はそのぶん手がかりが少なくて思い出しにくいかもね。そしてこれはこの問題には不適だったとも書いてあった。■ E 問題「Train Delay」。問題文が難しい。サンプルも利用して理解したところでは、ある１つの電車が遅延したとき、遅延によってできたはずの乗り換えが不可能にならないように、連鎖的に後ろの電車を遅延させていくと、遅延の合計はいくつになりますか、というもの。答えに選択要素はなく、無駄なく遅延させていけば答えになる。効率的にやるのが難しい。最初は電車の組み合わせを考えた。ある駅で発着する電車と電車で相互作用をさせる(相互ではない)。30 分かけて書いたこれは TLE だった。遅延の伝播をアドホックにやるのではなくトポロジカルソート順にやるのかと思って５分で書き直したものは、１つだけ TLE が減ったけどまだ TLE だった。たとえば半分の電車が駅１を発ち、半分の電車が駅１に着くとき、電車と電車の組み合わせは M^2 のオーダーなのだから、TLE はしかたがない。こういう、ダメな理由は、いざ TLE が出るまで考えないのです。途方に暮れていた時間を含めて 25 分でイベントソート版をでっちあげたら、総取っ替えの大手術だったにもかかわらず、TLE なしの WA×2 で筋が良い。その後５分で AC に至る。終了１分前。WA の原因は同時刻の発着を必ずしも着→発の順に処理していなかったこと。着イベントと発イベントを時系列順に再生しながら、駅ごとに最後に到着した電車の時刻(遅延込み)を記録しておくだけで伝播する遅延を確定していける。提出 #57090926 (AC / 397 Byte / 1847 ms)。昨日の日記(20240823)に「イベントを時系列順に並べることで考えるべき対象が限定できる」と書いていたことを思い出せたのが打開のきっかけ。■ F 問題「Dividing Game」。配点が同じなので最初に実装を始める前に F 問題まで問題を読んでいた。「ゲーム、Nim、Grundy 数、うっ、頭が……」ということだけ確認してから A 問題からの実装を始めた。F 問題が簡単だとは言わない。自分には解けない。答えに至る論理の道筋を納得しながら辿ることができないので。Nim の必勝法とか XOR のあたりで論理がお隠れになる。だから他の人も同じように解けないでいて欲しいのだけど、順位表を見ると 2454 人が通している。それはおかしいよ、俺に優しくないよ。ちなみに E 問題の方は 327 人。問題文が難しいし長かったからね、読みたくないからしかたないね。■自分のすべての提出。■精進……失敗。G 問題「Add and Multiply Queries」。前々回の F 問題 Maximum Composition を思い起こさせる設定。セグメント木なのかな、自分には乗せられないなと思っていたけど、「A,Bは正なのと、3つ目のクエリの条件より、区間内にB[i]が2以上な物は高々log(10^18)個程度しかない。B[i]=1の部分は、v+=A[i]をした方が良いのは明らか。よって各クエリに対し、B[i]=1の部分はBITを使ってA[i]の和を一気に加算し、B[i]＞1のところだけ加算と乗算どちらを取るか両方試していこう。」というのを読めば自分でも実装できる。提出 #57100689 (TLE×1)。こんなのってないよ。■最近タイプミスが多すぎるんだけど、たぶん爪が長い。白い部分が長いもので 6 mm ある(モニターの前に裁縫用のメジャーがあります)。短いのは 0 mm。むしろマイナス。ついつい噛んだり裂いたりしてなくなってしまいがちなので、触らないようにして最近は保護が行き過ぎている。長い爪というのは他の爪を攻撃しやすいのであり、また、長い爪というのは側面のちょっとしたささくれからぺりぺりと裂かれやすいのであり、攻撃力が高く防御力は低く、たいへん失われやすいものであるので、衝動を抑えていられる限りアンタッチャブルにしておきたいと思っているが、不便だな。ということをこの場所に書いているからには、不便を感じる機会が他にはあまりないということなんだな。■■■精進成功。G 問題。提出 #57153896 (AC / 918 Byte / 1161 ms)。配列の全長が高々 60 だとわかっていれば、長さ N の仮想配列に対する対数オーダーの処理を提供する BIT を使う必要はなくて、普通の配列に線形オーダーの基礎的な操作を施す方が定数倍がいいという話。というより、「次」を見つけるのに対数時間ではなく定数時間で済むという付加価値が大きいのかな。これでネタバレを恐れずに Ruby で唯一の AC だった konayuki さんの提出 #57098548 (AC / 1861 ms) を見に行ったら、クエリ３の答えをメモしていた。そう、１ケースだけだから、どういうクエリに弱いかを特定して対処しようと自分も考えていた。でもテストケースが見られないとなかなかわからないよね。■ちょっと勘違いをしていた。クエリ３の計算結果に制約があるのであって、1<Bi (i=1..N) なる要素の数が制約されているわけではない。だから B 数列の２以上の要素を管理するのに BIT ではなく Array を使うのにはリスクがある。ほとんどがクエリ２であるテストケースがあったら O(QN) で TLE だった。%w[...] リテラルに加工したけどな。■ C 問題「Attraction on Rainy Day」。配点は ABC-D。30 分かかった。KN≦2000万だから O(KN) が通らない可能性があって、余分に考えてしまった。DP なんだけど何をキーにして何を記録するのかひと目ではわからない。変数は「現在時刻」「濡れた量の総和」「アトラクションに乗った回数」。時刻ごと乗った回数ごとに濡れた量の総和を最小化する DP をする。スタートとゴールに近いときは考えるべき乗った回数が制約されるので、そこでループの回数をケチった。提出 #57009112 (AC / 1387 ms)。■ D 問題「Attend Many Events」。450 点。難しかった。30 分プラス２ペナ。頂点と辺とイベントの数がいずれも 1000 以下なので、いずれか２つの組み合わせが 100 万のオーダーで許される制約。イベントに参加するしないを総当たりはできないけど、イベントを時系列順に並べることで考えるべき対象が限定できる。つまり、あるイベントに参加するというとき、人の位置と時刻がそのイベントによって固定される。そのイベントに参加できるかどうかは、最後に参加したイベントもしくはスタート地点との距離によって決まる。過去のイベントを見て参加可能かどうか、それまでにいくつのイベントに参加しているかを見て最大のものを選んで現在のイベントに第３のパラメータとして記録する。O(KK) で許された。２地点間の距離は予め求めておく。２乗のアルゴリズムが許されるのでダイクストラ法を使わないで BFS/DFS でもたぶん大丈夫。提出 #57009717 (AC / 274 ms)。一度 WA を出した原因は、過去のイベントの中にはどうやっても参加不可能なものがあるということを適切に取り扱えていなかったこと。イベントに参加できていなかったのなら、その時刻その地点に居たという事実が存在しない、ということをきちんと反映させる。ところで、２乗のアルゴリズムを全頂点で実行したら３乗になってやばいのでは？ なんで全点間距離を愚直に求めて許された？ だからこその 1000 以下という、次の E 問題より小さい、２乗掛ける log が許されるやや小さめの制約か。■ E 問題「AtCoder Hotel」。どの制約も 5000 以下ということで、２乗の DP が許されたり TLE になったりしそう。何をキーにして何を記録する DP をしようか。結論を書くと C4B という変数名がすべて。つまり、B 人分の定員を確保するために C 円払ったということを記録する。B がキーで C が値。C を最小化する。ランクはどうなった？ これは人をランク要求で、客室をランクでソートすることで暗黙的に処理できる。客室ランクは大が小を兼ねるので、最もランク要求が厳しい人を満足させられる部屋だけで DP を行ったなら、その結果は次の人に対しても通用する。ただし、前の人が収まっているのでキャパシティが１減っている。提出 #57010115 (AC / 657 ms)。収容可能な人数として考慮すべき最大が徐々に減っていくのを考慮することでループの回数をケチった。C 問題と似たことを書いてるけど、こちらは 20 分しかかけていないので、C より E の方が簡単か。■ F 問題「Divide the Cake」。求められている答えから、更新しながら順番に判定をして最初の答えを見つけるんだと思うけど、どういう形式で記録すると高速に判定と更新ができるのかわからない。9..... だけ見て「はいはいいつものね」と油断した対応をしているけど、初心を忘れていなかった頃は、irb を開始して require'prime' して 998244353.prime? #=> true を確認していた。この数字をまともに読んだことも入力したことも一度もない。ずっとコピペしてる。覚えゲーは成立しないのです。だから素数って書いてあると嬉しい。* を補って全体を N 行 M 列に揃える。次に配列を transpose して reverse する。この時点でほぼ出力ができあがってるんだけど、各行末尾の * を取り除いてから出力する。■C 問題「Balls and Bag Query」。Hash で個数を管理してサイズを答える。カウント 0 になった要素は取り除く。■D 問題「Cuboid Sum Query」。３次元の累積和。具体的にイメージができないので、機械的に操作をする。うまく１次元の操作を２次元３次元に拡張できるといいね。行列計算がそうだしこの問題もそうだったけど、自分は必ず演算対象の次元数を勘違いしてエラーを出す。数値に対して配列のメソッドを呼んだりする。包除も機械的にやる。３つの次元について L を使うか R を使うかの２通りがあるので全体では 2^3=8 通りの累積和を足し引きする必要があるが、３つとも R を選ぶのが全体であり、そこから引いたり引きすぎたものを足したりするのだから、３個の R を選んだ場合をまずプラスにして、つまり奇数個の R がプラスで偶数個の R がマイナスになる。これはコンテスト終了後に AC が出たからわかったようなことを書いている。コンテスト中は飛ばして E をやっていた。D と E がどちらもたいへんなら配点の高い方に時間を使う。■E 問題「Manhattan Multifocal Ellipse」。D (入力値) の最大値が 100 万だということで、平面上のエリアを具体的に特定できると思った。X 座標と Y 座標を分けて考えるけど、それぞれプラスマイナス D の範囲に限ることができる。D×D は通らないけど、１つの軸を１つずつ走査しながらもうひとつの軸が効率的に数えられたらいい。(WA×1/TLE×5/AC×23) までは行ったんだけど、log の２乗は「効率的」ではないんだよなあ。でも尺取りをするのもたいへん。(WA×1/TLE×11/AC×17) の構造を崩して改善した結果がさっきの TLE×5 なのであって、さらにぐちゃぐちゃ書き直したくない。それが済んでも WA×1 が残る。■F 問題「Maximum Composition」。制約が小さい。K は 10 以下だし、(A,B) の組み合わせも 2500 通りしかない。ということは最大 20 万個の (A,B) には重複がたくさんあるのだが、K 個以上は K 個と変わらない。という感じでなんとなく状態数が少ないような気がしたからといって、メモ化再帰をするだけでは TLE になるのだなあ。コンテスト終了後に取り組んだけど TLE だった。■なんと ABC の３完だ。自分のすべての提出。いまもって E も F も AC が出ないのだから、D の AC が時間内か終了後かはどうでもいいよ。どっちでもだめだよ。■E 問題。AC 出たよ。提出 #56580497 (AC / 942 Byte / 642 ms)。一方の軸を走査しながらもう一方の軸について数えるのではない。それぞれの軸について独立に、座標を、距離の総和に変換する。あとは距離の列と列をソートして尺取りっぽく和が D 以下になる組み合わせを数える。そうしたら TLE が解消しただけでなくなぜか WA も消えていた。コードはほぼすべて先の２つの提出のコピペであって、なんの修正もしてないのに、謎だ。これで A から E まで AC が出たけど、100 分で５完の目がある問題セットではなかったな、というのが感想。D も E も実装が重い。かといって４完ではなく３完なのは全くの想定外。これまで２回くらい脳みそにクモの巣が張ってるって日記に書いてるけど、それってブレインフォグっていうんじゃあありませんか？(何かのせいにしたいだけ。キミはもともとそんなのだ)■F 問題。どうするのかなあ。引数が大きくなればなるほど A が作用する比重が B のより大きくなっていくのを利用して状態数を減らしたい気がするんだけど、A 対 B の２次元の表に線を引いてトップ K を選ぶことってできない。■D 問題の提出一覧を見てると、自分のが特に遅い。３秒制限ぎりぎりだから当然なんだけど、どこが遅いのか。３次元累積和の作り方が下手っぽい。自分のは余分にループが回っている。なにか標準的な手順があるのだろうか。自分はまず３次元空間を用意して、３つの軸について順番に一方向に寄せるように累積和を作成していった。無駄があるのは、３つのパスで順番に、１次元累積和の作成、２次元累積和の作成(１次元累積和のマージ)、３次元累積和の作成(２次元累積和のマージ)を行っていて、たぶん３つともに３乗の時間と空間が使われているところだと思う。どうもね、すでに更新済みの累積和を参照しながら１パスで３次元累積和を構築してる提出が多いみたい。それってややこしすぎません？sweet\nsweet を検索していたのを修正して sweet\nsweet\ns を検索するようにした。■B 問題「Grid Walk」。やります。B 問題にしては実装が重め。グリッドのサイズが小さくても実装量が減るわけではないんだよね、当たり前だけど。そこんとこ承知してくれているかな？■C 問題「Minimum Glutton」。C 問題で DP か？ と一瞬身構えたけど、最小値を求めるということで、２通りの貪欲法を比較するだけ。大丈夫です、最大値を求める DP 問題は E にあります。■D 問題「K-th Nearest」。二分探索してくださいという問題にしか見えなくて他に方法が思いつかないんだけど、制限時間３秒のところ、(１割増しの 3.3 秒ではなく) 3.22 秒かかって TLE だったので、220 ms ほどの高速化が必要。どうするの？■E 問題「Maximum Glutton」。C 問題の難しい版。甘さとしょっぱさの組み合わせを状態のキーにはできないけど、甘さとしょっぱさのどちらかと個数を組み合わせてキーにすることはできる。甘さをキーの１つにしたら、しょっぱさを最小化する DP をする。これもサンプルが教えてくれたんだけど、A 問題と同じ罠があります。同じ罠に落ちかけました。■F 問題「Range Connect MST」。どういう風に辺を引くことになるのか、イメージがしづらい。木なので本数は N+Q-1 本だと決まっている。それを最大 N×Q の組み合わせからどう選ぶと全域木になるのか。あれこれ考えてようやく納得できたのは、i=1..Q において、Li..Ri のあいだに連結成分が g 個あるなら、g 本の辺を引くのだということ。両手の 5+5 本の指を使って考えると、それで N+Q-1 本の辺が選ばれるようだったのでそう思った。答えが合わなくて時間内に提出できなかったんだけど、原因がしょうもなくて、貼り付けた BIT のイニシャライザにある初期化コードが今回は不要だと思って削除したけど、削除してはいけなかったという、そういう理由で答えが合わなかった。たとえばヒープだと、ソート済みの配列を内部データにする場合、初期化の必要がない。ソート列はそのままでヒープの要件を満たしている。だけど BIT の内部データは違うんだなあ。解ける問題だったなあ。１から数年前の自分なら解いていたなあ。■自分のすべての提出。最近ユーザー名の横に表示されるへの字。ノイズではあるんだけど、水色でもまだ 1500 台を維持しているなという慰めにもなっているもよう。■精進。D 問題。Q のループの中で二分探索をする中で二分探索を２回行って TLE を出していた。二分探索の上限を指定せずに TLE×11。上限を指定して TLE×7。最も内側にある２個目の二分探索を省けるときは省くようにして TLE×1。最内の２個目の二分探索を完全に省いて AC。これが 1765 ms なんだけど、Ruby で 627 ms で解いている人がいるんだよね。気になるけどネタバレは嫌だ。■D 問題。別解。提出 #56088391 (AC / 325 Byte / 340 ms)。log １つでできると読んだので、k 幅のウィンドウを二分探索で置いてみた。判定条件は、右端の要素が初めて左端の要素よりも b から遠くなる瞬間。そのひとつ手前では逆に、左端の要素が右端の要素より b から遠くなっている。この両者を比較する。二分探索の高速化っていうと尺取りが定番なんだけど、だから昨日はその方面で TLE 回避策を考えたりしてたんだけど、この D 問題はウィンドウの幅 k がクエリごとに可変だから、尺取りはうまくない。今日の提出では同じ二分探索を使っていてあまり違いを感じないんだけど、よく見れば二重の log が一重に減っている。log １つの差ってたしかにこれくらい微妙なものではあった。Pairs を解いていたときに書いている。「log ひとつの差ってちょっとした違いなんですよ。ちょっと見る角度を変えるだけ」。提出したあとでもういちどさっき読んだブログを読み返すと、まんま自分の提出がやっていることが書いてある。「初めて左端のが遠くなった場所を見つけてその一つ前も（存在すれば）候補なので比較して」。なんかよくわからんなあと思いながら読んでいたけど、実際今も「自分より１離れたもの同士を比較」「長さが１短い区間を考えて」「初めて右のが遠くなったら左のを付け加えてそれがそのまま答え」とかよくわからないんだけど、必要なことは一度読んだだけで頭の中に入ってるんだな！ 自分では思い出せないだけで。しじゅうく‐にち【四十九日】〘名〙 人の死後四九日目に当たる日。また、その日に行う法要。」とか書いてあって、これもうわかんねえな。いやホントはわかりますよ。「四十九日」「七七日」の２つと「四九日(目)」とでは使用時期にずれがある。辞典の言葉は収録される言葉よりも新しい。23 日を二三日と書くことの帰結として、10 月が一〇月になっていたのが先々週読んでいた小説。何を今更感しかないけども、そうなんだ、そりゃそうなるよな、だけど気持ち悪いな、その○はなんなんだ、漢字ではないよな、とひっかかってしまったのが今日の日記になっている。十月って書きたいよ。■ATOK で 10 を変換して出した一〇で使われているのは○ではなかった。U+3007 は「漢数字ゼロ IDEOGRAPHIC NUMBER ZERO」であり、U+25CB 「丸印，白丸 WHITE CIRCLE」とは異なる文字だった。〇が比較すると新しい字だけど数百年はさかのぼれるみたいなことが Wikipedia の漢数字のページに書いてある。お前漢数字なのか。漢数字とアラビア数字を区別して一方では位取り記数法を認めたくないっていうのは、単に好みや慣れや、旧弊に囚われているってだけなのか。自分はこれからも区別して用途を分けていきます。■用途を分ける(漢数字では位取り記数法を使わない)ことの別の一面は、「健康第１」とか「３位１体」とか「別の１面」とは書かないということ。算用数字を使うのは１、２、３と数を数える場面だけでいい。X と X+1 が可換な場合だけでいい。七七日 。