1位賞金100万円コンテストで胸熱回。[Q] https://atcoder.jp/contests/abc286/tasks/abc286_f

・考察
1. 要素のループを作ろうと思う

1個ずつずれるような出力を与えようと思う。
・2 3 1
を与えれば、Nmod3が得られる
・5 6 7 4
を与えれば、Nmod4が得られる

・N = 2のとき
出力を
7
2 3 1 5 6 7 4
とすると、N=12まで特定できるはず。

N=2なので、
3 1 2 6 7 4 5
~     ~ が返ってくるはず。
差分で剰余がわかる。

index1が3になっているので、3 - 1 = 2 ... mod3
index4が6になっているので、6 - 4 = 2 ... mod4
 
3で割っても4で割っても2あまる数は2。

2. 中国剰余定理で、Nmod3かつNmod4を満たす最小のNが見つかるはず
3. ループの大きさを、"互いに素"にすれば、lcmだけバリエーションを持たせられる。
4. 
2, 3, 5, 7, 11, 13, 17, 19, 23 の総和が100だけど、lcmが1e9に足りない…。
2, 3, 5, 7, 11, 13, 17, 29, 23 とかにしてみるが、lcmが1e9に足りない。どこかで3倍くらい増やさないといけない。
5.
4, 9, 5, 7, 11, 13, 17, 19, 23 の総和108が正解だった。
素数ではなく、互いに素でありさえすればよかった。

Q.  なぜかTLEする。
cin.tie(0);
のせい。入出力を高速化するおまじないだが、coutを待たずにcinを始めてしまうから。

・実装

int main(){
  vector<ll> cand = {4, 9, 5, 7, 11, 13, 17, 19, 23};
  vector<ll> starts;
  ll M = 0;
  for(auto c: cand){
    M += c;
  }
  cout << M << endl;
  ll st = 1;
  // 5 6 7 8 9 => 6 7 8 9 5 にすればいい
  vector<ll> outs;
  for(auto c: cand){
    ll s = st;
    starts.emplace_back(s);
    rep(i, c - 1){
      outs.emplace_back(st + 1);
      ++st;
    }
    outs.emplace_back(s);
    ++st;
  }
  rep(i, outs.size()){
    cout << outs[i] << " \n"[i == outs.size() - 1];
  }
  pll ans = {0, 1};
  rep(i, cand.size()){
    ll a;
    cin >> a;
    // x≡2(mod5), x≡1(mod6) を満たす最小値を求める。
    // リターン値を (r, m) とすると解は x ≡ r (mod m)
    // 解なしの場合 (0, -1) をリターン
    // auto r = ChineseRem(2, 5, 1, 6); // 7 30 = {min, lcm}
    ans = ChineseRem(ans.first, ans.second, a - starts[i], cand[i]);
    rep(j, cand[i] - 1){
      cin >> a;
    }
  }
  cout << ans.first << endl;

  ////debug
  auto debug = [&](ll N){
    rep(i, M){
      ll f = outs[i] - 1;
      rep(j, N - 1){
        f = outs[f] - 1;
      }
      cerr << (f + 1) << " ";
    }
  };
  //  debug(349);
}

https://atcoder.jp/contests/abc286/submissions/38238376