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)を数えているあいだに何を数えているのかを忘れ、目的を思い出しているあいだに数えた和を忘れるという始末。深刻だ。