問題概要
「$P_i$ が変数の値以上ならば変数の値を $A_i$ だけ増やし、そうでなければ変数の値を $B_i$ だけ減らす (ただし、これにより変数の値が負になりそうなときは $0$ にする)」という操作 $N$ 個の列がある。
$Q$ 個のクエリ $X_i$ それぞれについて、変数の初期値を $X_i$ としてこの操作列を順に実行した際の最終的な変数の値を求めよ。
自分が立てた方針
変数の初期値が大きいとき、最初に変数の値が $P_i$ 以下になるまでは変数の値を減らし続ける。
そこで、どこまで変数の値を減らし続けるかを二分探索し、その地点からはそのまま操作列を実行する。
実行結果は「実行を開始する位置」「実行を開始するときの変数の値」をキーとしてキャッシュする。
$P_i$ は位置によって異なるため、「どこまで変数の値を減らし続けるか」を正確に求めるのは難しそうである。
そこで、かわりに「どこで変数の値が $P_i$ がとりうる最大の値以下になるか」を二分探索し、この地点から操作列を実行する。
提出したコード
提出 #68626565 - AtCoder Beginner Contest 417
実行時間制限 2sec のところ、110ms で AC となった。
嘘だッ！！
解説を読むぼく「DPわかんないっピ……ん、待てよ！？」
自分のコードをよく見ると、操作を開始した位置でしかキャッシュの判定をしていない。
これでは、「実行を開始するときの変数の値」や「実行を開始する位置」を1ずつ変えて操作を走らせることで、毎回長い操作を行わせ、長い計算時間を消費させることができそうである。
キャッシュなどという普段競技プログラミングで使わない概念を持ち出さず、変数の値が $P_i$ がとりうる最大の値以下になった後普通にメモ化探索をすればよかったはずである。
テストケースの名前を見ると sample と random しか無く、テストケースが弱いようである。
撃墜
以下のようなテストケースを用いることで、「実行を開始するときの変数の値」や「実行を開始する位置」を1ずつ変え、できるだけ手前から始まる長い操作を行わせることができそうである。
- 操作の数 $N$ とクエリの数 $Q$ は最大にする
- しきい値 $P_i$ と足す値 $A_i$ は適当な値にする
- 引く値 $B_i$ は最大にする
引く値を最大にすることで、「次に引かれたら探索ゾーンに入る」というゾーンの幅を最大にでき、幅広い「実行を開始するときの変数の値」を用いて「実行を開始する位置」の消費を抑えることができる。
以下のプログラムで、このようなテストケースを作ることができる。
N = 10000
P = 1
A = 1
B = 500
Q = 500000
print(N)
for _ in range(N):
print("%d %d %d" % (P, A, B))
print(Q)
for X in range(Q):
print(X)
しかし、このテストケースは 3 MiB 以上になり、512 KiB 制限がある AtCoder のコードテストでは入力できない。
そこで、解答コードの入力部分を変更し、$N$ と $Q$ だけを入力として受け取り、残りのデータはコード内で生成するようにして実行した。
int i;
if (scanf("%d", &N) != 1) return 1;
for (i = 0; i < N; i++) {
//if (scanf("%d%d%d", &P[i], &A[i], &B[i]) != 3) return 1;
P[i] = 1;
A[i] = 1;
B[i] = 500;
sum[i + 1] = sum[i] + B[i];
}
if (scanf("%d", &Q) != 1) return 1;
for (i = 0; i < Q; i++) {
//if (scanf("%d", &X[i]) != 1) return 1;
X[i] = i;
}
すると、実行に約 2300ms かかった。
残念ながら 2sec の制限に間に合わず、TLE となるだろう。
修正したコード
提出 #68626848 - AtCoder Beginner Contest 417
実際に、メモ化探索に切り替えた。
変数の値が $P_i$ 以下のときは変数に $A_i$ が加算され、変数の値が「$P_i$ がとりうる最大の値」を超えることがあることに注意し、メモの要素数を決定した。
同様に入力部分を変更してコードテストで実行を行うと、約 55ms で実行が完了した。
実際には入力を読み込む処理の時間もかかることを考えても、十分に高速に動作することが期待できる。