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」。異次元からの眺め。さっぱりすぎる。