0=a1<...<an=M-5 や 5=a1<...<an=M など、初項 a1 が取り得る値が 0 から 5 の 6 通り考えられるのでこれを掛ける。困ったのは、+3 操作の上限を決めて 0 個、1 個、2 個と挿入する場合の数の合計も、+1 操作の上限を決めて 0 個、1 個、2 個と挿入する場合の数の合計も事前に累積和を計算しておくことで定数時間で求められるのだけど、初項が取り得る値のバリエーションを累積和に掛ける方法がわからなかった。たとえばメインループで +3 操作の回数を決め打ったとする。追加で可能な +1 操作回数の上限がわかるので累積和を引く。しかし +1 操作回数が 0 回のときに初項が取り得る値の種類数と 1 回のときに取り得る種類数は異なる。+1 操作の選び方に階段状の倍率を掛けたものの累積和が欲しい。倍率はスライド式であり、×5,×4,×3 かもしれないし、×3,×2,×1 かもしれない。あるいは初項の前へのプラス操作が他と統一的に数えられたら。困ったときはお風呂で考える。普通の平坦な累積和と階段状の累積和を組み合わせればいける。いけなかったのは、N,M の制約上限が普段より厳しい 10 メガなのであり、コンビネーションの事前計算に加え累積和を２本も作成する 3N の処理で制限時間の４秒を超えてしまったこと。10 秒まで実行されるコードテストで 4.4 秒からなかなか縮まなかった。■提出 #36313584 (AC / 773 Byte / 3938 ms)。C1 メソッドの値から A 数列を作成するときに呼び出し回数を半分に節約したり、メソッドの中身をインライン展開したり、メインループの共通項を ICI として括り出したり、fn 数列の前部を切り捨てて添字のオフセット計算を省略したり、いじましい努力の結晶ですよ。Ruby によるすべての提出を見ると、tinsep19 さんの提出は最悪ケースこそほぼ同じタイムだけど、内訳を見ると１秒早かったり倍早かったりするものが多い。４秒ぎりぎりの最悪ケースの位置が異なってるのが面白い。向こうの最悪ケース(１つだけ)はこちらの最悪ケース(13 個)ではないのだ。■メインループを逆順にすると必要なのが累積和の末項だけになって事前の作成が不要になる気がするなあ。■提出 #36318378 (AC / 736 Byte / 3061 ms)。メインループを逆順にして累積和が配列２本から変数２個になった。*smallN* ケースだけやけに遅くて最適化の余地があるみたいだけど、それ以外は概ね良好かな。汚いという意味では良くないけど。■「スナネコ「ABC276Gの解説に追記しました」 https://t.co/9pw10g1SOS https://t.co/bRGlSd8RcW」。異次元からの眺め。さっぱりすぎる。(1+2+...+N-1)/N <= X/Y = (1+2+...+N-M)/N < (1+2+...+N)/N) 以前はそもそも上と下の両方を抑えようという意識が働かなかったと記憶している。雰囲気で片方を抑えてそれで？って感じ。ぼんやりしてら。■しかし罠が２つ。提出 #36180781 (WA×8)。考えられるすべての N と M を N の昇順に出力することが求められていたのに１組しか出力していなかった。提出 #36180916 (WA×5)。分子と分母にまったくどうでもいい数が共通に掛けられているケースに対処できていなかった。「ただし、入力は既約分数とは限らない」とはそういう意味。約分している場合もそのままの場合もあるというだけではなく、無駄に数字をふくらませている場合があった。■提出 #36181139 (AC)。テストケースがあればデバッグが捗っただろうけど、古い ARC のは公開されていない。
直前の要素から連続するのかそうでないのかでコスト計算が変わってくる」ことがわかっていても「
直前の要素を使用しているかをフラグとして持ってあげるとよい」と明示されることが問題解決のヒントになるのだなあ。■提出 #36122711 (TLE×4 / 2191 ms) のち 提出 #36123362 (AC / 1864 ms / 107396 KB)。Ruby によるすべての提出を見ると他の２つの AC 提出と比べてメモリ使用量が５倍以上ある。なんか違うことをやってんだろか。■提出 #36124108 (AC / 1452 ms / 45264 KB)。メモリ使用量の差は Hash か Array かの違いだと思ってまねしてみたけど、時間もメモリもなんか違う。それに AC 提出の片方のメモリ使用量を１桁読み間違っていたこともわかった。18 メガじゃなくて 180 メガだから自分のと大差なかった。だいたい同じことをやってるよ。
オリジン間 HTTP リクエストのリスクの緩和に役立てています」とはどういう皮肉か。■きっかけはこのツイートだったんだけど、「@chokudai AtCoder の API に Access-Control-Allow-Origin など CORS 指定がないのにはなにか理由があるのでしょうか？ これがあれば、有志ウェブサイトが AtCoder の API を叩くためだけに Heroku などに依存する必要がなく、GitHub Pages などでの静的ホスティングが可能になると思うんですが…」、Heroku を利用することで何がどう可能になるのかがまだわかっていない。難しいね。Heroku の無料プランがなくなるんだっけ？ そうすると有志ウェブサイトは何ができる？
t = (A+dx).fdiv dv。これは「追いつく」関係のときに追い越してしまって幅 A の区間から出てしまうタイミングを計算する式。正しくは t = dx.fdiv dv。２つめは 11 行目と 19 行目 でハッシュのキーに 0 を使っているところ。0 と 0.0 をソートしたら結果が不定になった(Ruby 2.7 の場合)。それではハッシュを入る方と出る方の２つに分けた甲斐がない。実数で閉区間は扱いにくいんよ(どうして区間を x+A 未満にしてくれなかったのか)。キーが 0 であれ 0.0 であれ入る方を必ず先に加算しなければいけないのにできていなかった。３つめは「追いつかれる」ケースの処理を忘れていたこと。■提出 #35903826 (AC / 712 Byte / 2942 ms)。これだけミスがあって時間もかかるなら解けた喜びしかない。なんにも惜しくない。■■■精進２。同じ ABC174-E 問題「Booster」(水 diff)。時間中は F 問題にかかりきりで読まなかった。ブースターを使う使わないを総当たりしてダイクストラ法かなと考えたりもしたけど、どうにもはまらない。むしろ巡回セールスマン問題(TSP)だった。■提出 #35902406 (AC / 674 Byte / 1847 ms)。これまで２問くらい TSP(roblem) を解いてるけど久しぶりすぎて忘れていた。ワーシャルフロイド法と同じ見た目をしていることを思い出すのに時間がかかり、何とか書き上げても TLE を２回食らった。以前にタイムを詰めに詰めてこれが決定版と言えるものを作ったんだけど、内容を覚えていないしどの問題かも思い出せなかった(そのときに競ってアイデアを提供してくれたアカウントは覚えている。精進中に見かけた名前を最近またコンテストで見るのは嬉しいものだけど、逆もあって寂しい)。唯一思い出したのが 12 行目の １,０ = (N+M).times.partition{|b| 0<vs[b] }。これで TLE が解消した。big |= 1<<k とか big ^= 1<<k になる。|= や ^= が =、|、^ を使ったシンタックスシュガーだとしたらそれも残念だけど(でもそうだよね？)、1 ビットに作用させるためだけに Bignum の一時インスタンスを作成して、桁数に比例したビット演算をさせているのが(たぶん)、もったいなくて仕方がない。リファレンスを漁るけど flip メソッドが見つからない。bitset みたいな特別な道具としてではなく普通の整数で多倍長のビット演算ができるところが、速度で不利になりがちな Ruby が強みにできるところであるので、機会を逃さず Bignum を酷使していきたいと思っている。これは昨日の日記(20221019)への言及。