コンテスト中の考察
- ある1点をナシにしてGCDをとる。それを全探索すれば解ける。ただ、計算量が$2^N$になってしまう（たぶん）
- DFS書いたからDPできないか考えたけど無理っぽい。計算途中ではどの値が最適かわからないので最大値をとるとか最小値をとるとかができないので。
- GCDときたらLCMなのでLCMをとってみる。なにもわからない。
- なんもわからん。終了
反省
詰まった部分
- あるひとつの要素を取り除いてGCDをすればいいことはわかったがこれではTLE。その先どう考えればいいかわからなかった。
- 全体のGCDを取ってからある要素を取り除きたい気持ちになったが、GCDは復元みたいなのができないので無理だった。例えば和だったら全体の和を求めてからある要素を引けばいいけどGCDはそれができない。
解決策
- 両端からGCDを累積する。
- 発想としては簡単だが思いつけなかった。累積といえば累積和という固定された知識があったから思いつかなかった気がする。全体からある要素を取り除いた結果を知りたかったら、両端累積するとよさげ（類題解いてないからなんとも言えんが）。これは後から復元できない演算で有効っぽい？例えばGCDの部分がOR演算とかAND演算でもこの問題は同じようなことができそう。
解法
- 両端からGCDの累積をとる
- 取り去る要素を全探索する。そのとき、あらかじめ求めた累積GCDの左右の要素のGCDをとる。そして、その値の最大値が答えとなる。
コード
# include <bits/stdc++.h>
using namespace std;
# define int long long
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
int N;
int A[111111];
// 1-indexed
int l[111111]; // 左から累積
int r[111111]; // 右から累積
long long gcd(long long a, long long b) {
if (b == 0) return a;
return gcd(b, a%b);
}
signed main() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> A[i];
}
for (int i = 0; i < N; i++) {
l[i+1] = gcd(l[i], A[i]);
}
for (int i = N; i >= 1; i--) {
r[i] = gcd(r[i+1], A[i-1]);
}
int ans = 0;
for (int i = 1; i <= N; i++) {
int tmp = gcd(l[i-1], r[i+1]);
chmax(ans, tmp);
}
cout << ans << endl;
return 0;
}
要点
- ある要素だけいらない場合を考える時、両端から累積をとると良い
- 累積＝累積和ってイメージが強かったし、今までそれしか見たことなかったのでGCDでもできるのかぁってなった。
- GCDに限らず、ORやANDでも使える（和とか積でも使えるけど使って嬉しい場面がなさそう）
- 累積テーブルは連続的に処理していく演算をしている全ての問題に適応できる。逆から累積和を使うテクは、その演算に結合法則が成り立つ場合に使える。って強い人が言ってた
メモ
- 3N Numbers。これ類題らしい。他にも類題あったら教えて欲しい。
- 解けなかったクッソ悔しい。ていうかGCD使う問題本番で解けたことないんだけど。