問題
これの
これです。
解いてから解説を見たのですが、難しそうでした・・・
数学的な手法もよく知らず、頑張ってどうにかした例を紹介します。
変わったコードを見るのが好きな方はぜひ。
説明
問題はざっくり、
- ステージがN個ある
- ステージの中には試合がA回ある
- 試合に負けると、そのステージの残りの試合は飛ばして次のステージへ進む
- 「最大の連勝数がちょうどX回」(多いのも少ないのも不可)になるパターン数を求める
という感じです。
基本方針
まず、「ちょうどX連勝が存在する」パターンだけを数えることにします。
「ちょうどX連勝」であれば何回あってもよい点が少しややこしいですね。
# ステージ
↓ステージごとに「丁度X連勝」のパターンは1つのみ
↓連勝最後のステージは0勝の場合も含む
(X連勝の後で1回負けるまでが範囲)
位置i
#############===============##############################
~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
前側 後側
「X連勝以上(※)」を除いた 「X+1連勝以上」を除いた
パターン数 パターン数
※X連勝も弾くことで、位置iを最初のX連勝の位置とする
X連勝の開始位置をずらしながら、
「前側のパターン数」 × 「丁度X連勝のパターン1通り」 × 「後側のパターン数」
の合計を加算していけば良いはずです。
「位置iを最初のX連勝開始とする」工夫によって、重複しないようにしています。
X連勝の前側と後側の考え方
前側と後側では、条件なしの総パターン数から「条件を満たさないパターン」を削っていきます。
条件を満たさないとはつまり、連勝しすぎになってしまうケースですね。
前側の考え方
今度は減算するためのパターン数を数え上げます。
前側で気をつけなければいけない点は、
最後のステージを連勝で終わってしまうと次のX連勝に繋がってしまうので
間違ってカウントに入れてしまわないようにすることです。
# ステージ
x連勝
末尾によりパターン数がある↓ 次の「x連勝」の開始位置
位置i ↓
#############===============################===
~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~
前側 後側 ↑末尾は-1通りとする
この範囲は再帰で x連勝以上はすべて数えてよいので
パターン数を数える この範囲は単純な総パターン数でOK
位置をずらしながら、
「前側のパターン数」 × 「x連勝のパターン数」 × 「後側のパターン数」
これを総パターン数から減算していった結果が「この範囲のパターン数」となります。
再帰の部分は分かりにくいですが、取れるのは「x連勝未満だった」パターン数なので
重複してカウントしてしまうことはありません。(ここは本当に分かりづらい)
後側の考え方
前側とほぼ同じですが、
最後は連勝で抜けてもよいので「末尾の-1通り」が要らない点だけが異なります。
事前計算
数字もかなり大きくなるので、計算量の削減も重要そうです。
分かりきっているものは何回使うか分からなくても先に計算しておきましょう。
- 先頭からそのステージまでの総パターン数
- 先頭からそのステージまでの総パターン数 (このステージを連勝で抜けない場合)
- そのステージから末尾までの総パターン数
という感じで、「末尾は-1通り」のパターンも計算しておきます。
(具体例はコードのコメントに入れてあります)
キャッシュ
「前側」「後側」の計算は、パラメータ自体はとても単純です。
- 開始位置
- 終了位置
- 指定された連勝数
これらが同じであれば、もちろん計算結果も同じです。
使用メモリ次第ではありますが、キャッシュしておくのは有効そうです。
コード
速度面は、テスト9,10でも0.07〜0.08秒だったのでとりあえず大丈夫そう。
オーダーは謎です。
実際のところ、事前計算よりもキャッシュが大きく貢献するようです。
// Copyright © 2024 https://qiita.com/tanin_no_sorani
// Released under the CC0 1.0 Universal license.
'use strict';
// (参考) 入力例3における事前パターン計算(0は飛ばしている)
// [
// Stage { a: 0n, prev: 1n, last: 1n, next: 1n },
// 1 Stage { a: 8n, prev: 9n, last: 8n, next: 80831520000n },
// 2 Stage { a: 5n, prev: 54n, last: 45n, next: 8981280000n },
// 3 Stage { a: 9n, prev: 540n, last: 486n, next: 1496880000n },
// 4 Stage { a: 7n, prev: 4320n, last: 3780n, next: 149688000n },
// 5 Stage { a: 6n, prev: 30240n, last: 25920n, next: 18711000n },
// 6 Stage { a: 9n, prev: 302400n, last: 272160n, next: 2673000n },
// 7 Stage { a: 9n, prev: 3024000n, last: 2721600n, next: 267300n },
// 8 Stage { a: 8n, prev: 27216000n, last: 24192000n, next: 26730n },
// 9 Stage { a: 2n, prev: 81648000n, last: 54432000n, next: 2970n },
// 10 Stage { a: 8n, prev: 734832000n, last: 653184000n, next: 990n },
// 11 Stage { a: 1n, prev: 1469664000n, last: 734832000n, next: 110n },
// 12 Stage { a: 4n, prev: 7348320000n, last: 5878656000n, next: 55n },
// 13 Stage { a: 10n, prev: 80831520000n, last: 73483200000n, next: 11n },
// Stage { a: 0n, prev: 1n, last: 1n, next: 1n }
// ]
let N = null; // 総ステージ数
let X = null; // 最大の連勝数
const A = [] ; // 各ステージの試合数 最大N+2個(head,tail)
const cache = {}; // 同一計算防止のためのキャッシュ
class Stage {
a = 0n; // このステージの試合数 (0はリストに入れないため実際は1以上)
prev = 1n; // 先頭からの総パターン数
last = 1n; // 先頭からの総パターン数(このステージを連勝で抜けない場合用)
next = 1n; // 末尾からの総パターン数
constructor(a) { this.a = a; }
}
require('node:readline').createInterface({ input: process.stdin })
.on('line', line => {
if (N === null) { // 先頭行
[N, X] = line.split(' '); N = Number(N); X = BigInt(X);
A.push(new Stage(0n)); // head
} else {
const a = BigInt(line);
(a === 0n) ? (N--) : A.push(new Stage(a)); // 0は飛ばして収集
}
})
.on('close', () => {
A.push(new Stage(0n)); // tail
// 双方向から総当たりのパターン数を事前計算
for (let i = 1; i <= N; i++) { A[i].prev = A[i-1].prev * (A[i].a + 1n); }
for (let i = 1; i <= N; i++) { A[i].last = A[i-1].prev * (A[i].a ); }
for (let i = N; 1 <= i; i--) { A[i].next = A[i+1].next * (A[i].a + 1n); }
// 全体探索 (「最大X連勝」が必須、それより多いのも少ないのも不可)
let total = 0n;
for (let i = 1; i <= N; i++) {
// 位置「i」から、X連勝した後のステージ位置「j」を特定する
let remains = X;
let j; for (j = i; (j <= N) && (0n <= remains); j++) { remains -= A[j].a; }
// X試合残っていなかった時点でこれ以上は存在しないことが確定
if (0n < remains) { break; }
// 「X連勝した範囲の外」で総パターン数を算出する
// (前方だけX連勝以上を除外することで、位置「i」が最初のX連勝の開始位置となる)
const prev = search_range(1, (i - 1), X ); // 前方はX連勝以上を除外
const next = search_range(j, N , (X + 1n)); // 後方はX+1連勝以上を除外
total += (prev * 1n * next);
}
// 部分探索 (指定された連勝数x以上を除外)
function search_range(start, end, x) { // (endはその位置を含む)
if (end < start) { return 1n; } // 前or後がない場合 1通り
if (x <= 1n) { return 1n; } // 全敗であれば範囲に関わらず 1通り
// 引数の組み合わせでキャッシュがあればそれを返す
const c = cache[`${start}-${end}-${x}`]; if (c) { return c; }
// 指定された範囲の総パターン数を取得 (ここから減算していく)
let range_total = patterns(start, end);
for (let i = start; i <= end; i++) {
// 位置「i」から、x連勝した後のステージ位置「j」を特定する
let remains = x;
let j; for (j = i; (j <= end) && (0n < remains); j++) { remains -= A[j].a; }
// 末尾endのステージまで連勝範囲が及んでいる場合で、
// endが全体の末尾ではない場合、次のステージが連勝開始の起点のため、
// 最後のステージを連勝で抜けるパターンを除外する
// (連勝で抜けるパターンしかなかった場合はremainsが0→1となり次の判定で抜ける)
if ((end < j) && (end !== N)) { remains++; }
// x試合残っていなかった時点でこれ以上は存在しないことが確定
if (0n < remains) { break; }
// x連勝以上になってしまうパターンを算出し、総パターン数から減らす
// ・前のパターン数: 総パターン数からx連勝以上を除くため、再帰呼び出し
// ・位置「i」からの連勝パターン数: j-1の位置のステージで許容されるパターン数
// ・後のパターン数: 指定範囲の総パターン数でよいため、再帰は不要
const prev = search_range(start, (i - 1), x);
const next = patterns(j, end);
range_total -= prev * (1n - remains) * next;
}
return (cache[`${start}-${end}-${x}`] = range_total); // キャッシュに保存して返す
}
// 指定された範囲の総パターン数を取得
function patterns(start, end) {
if (end < start) { return 1n ; } // 前or後がない場合 1通り
if (end === N) { return A[start].next; } // 最終ステージまでの場合 (計算済)
if (start === 1) { return A[end ].last; } // 先頭ステージからの場合 (計算済)
return (A[end].last / A[start-1].prev); // endのステージの連勝を除いたパターン
}
// (BigIntのまま渡すと末尾にnが付くためtoStringは必須)
console.log((total % 1000000000n).toString());
});
感想
なかなか数字が合わず、原因探しに時間がかかりましたがなんとかなりました。
Sランクの問題だけですがどうにか一通り出せました。
ここまで読んでいただき本当にありがとうございました。