//なんだこれ?区間DPかと思いきや、全探索が間に合うやんけ!(面白い) //数列を2つのグループに分けてどちらかを取るゲームと考えられる。同じ値だけなら要素数1として見る。 //数列を分ける様子を木で表すと、高々N頂点の木になる。よって、高々N頂点のゲーム木探索になり、全探索が間に合う。 //数列の切れ目を探す時間を累積和、2分探索で高速化すれば十分間に合う。 #include #include #define int long long using namespace std; int n; int a[100000]; int ra[100001]; bool dfs(int l, int r) { if (l >= r) return false; if (a[l] == a[r]) return true; int s = ra[r] - ra[l]; int ave = (s + (r - l - 1)) / (r - l); int i = lower_bound(a, a + n, ave) - a; bool res = false; if (i < r) { res |= !dfs(l, i); } if (i > l) { res |= !dfs(i, r); } return res; } signed main() { int i, j, k; cin >> n; for (i = 0; i < n; i++) { //aはソート済み cin >> a[i]; ra[i + 1] = ra[i] + a[i]; } bool res = dfs(0, n); if (res) cout << "First" << endl; else cout << "Second" << endl; return 0; }