注意

この解説文は、問題そのものの解説ではなく、マルチテストケース問題一般に対して言及するものです。また、やや発展的な内容であり、茶色以上を想定読者として書かれています。

要約

競技プログラミングにおいては、グローバルに変数を置くことがよくあります。マルチテストケースの問題を解く際は、グローバル変数の初期化忘れに注意しましょう。

例

ABC275D『D - Yet Another Recursive Function』 を改題した以下のような問題を考えます。

\(2\) 以上の整数 \(N,A,B\) が与えられます。\(f_{A,B}\) を次のように定めるとき、\(f_{A,B}(N)\) を求めてください。
\(f_{A,B}(k)=\begin{cases} 1 && k=0\\ f_{A,B}(\left\lfloor\frac{k}{A}\right\rfloor)+f_{A,B}(\left\lfloor\frac{k}{B}\right\rfloor) && k\geq 1 \end{cases}\)

この問題は、以下のようなメモ化再帰で解くことができます。

#include<bits/stdc++.h>
using namespace std;

map<long long, long long>memo;
long long f(long long a, long long b, long long k){
  if(k==0)return 1;
  if(memo.count(k))return memo[k];
  memo[k]=f(a,b,k/a)+f(a,b,k/b);
  return memo[k];
}

int main(){
  long long n,a,b;
  cin >> n >> a >> b;
  cout << f(a,b,n) << endl;
}

この例題をマルチテストケースにした問題に対して、以下のような実装ではWAになります。

#include<bits/stdc++.h>
using namespace std;

map<long long, long long>memo;
long long f(long long a, long long b, long long k){
  if(k==0)return 1;
  if(memo.count(k))return memo[k];
  memo[k]=f(a,b,k/a)+f(a,b,k/b);
  return memo[k];
}

void solve(){
  long long n,a,b;
  cin >> n >> a >> b;
  cout << f(a,b,n) << endl;
}

int main(){
  int t;
  cin >> t;
  while(t--)solve();
}

メモをした連想配列 memo を初期化し忘れ、前のテストケースの結果を参照してしまうことが原因です。対応策としては、solve() の中で初期化を行うことや、メモの key を \((a,b,k)\) の組にすることが考えられます。

グローバルに変数を置かないことが最も有効な対策の一つですが、競技プログラミングにおいては、実装にかかる量・時間とのトレードオフを理由に「グローバル変数を”気をつけて”使う」というのが一般的です。