ABC125

C - GCD on Blackboard

考えたこと：

・双方向から累積gcd

・すべて素因数分解してごちゃごちゃ

（バグったのでＤに行きました。ＡＣ出来ませんでした・・・）

解説：

この問題を言い換えると、「Ｎ個の要素からＮ－１個選んだ時、ＧＣＤが最大になるようなものの値を求めよ。」です。

なので、Ｎ－１個のＧＣＤを求めることを考えます。

普通にやるとＮ＾２なので間に合いません。

双方向から累積和の要領でＧＣＤを取っていきます。

ＧＣＤには逆元がないので、普通に累積和を取っても引くことが出来ません。

しかし、この問題では１つだけ除いたものを求めればいいので、添え字０から除くものの１つ手前までのＧＣＤと、添え字Ｎ－１から除くものの１つ前までのＧＣＤが解ればそれら二つのＧＣＤを取ることで答えは求まります。

このほかにも、セグ木を貼ればO(N log N)で計算できたはずです。

私にとってこの問題は解かなければいけなかった問題です・・・

実装です・・・

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

int main() {
  int N;
  cin >> N;
  vector<int> a(N + 2), l(N + 2, 0), r(N + 2, 0);
  for (int i = 1; i <= N; i++) cin >> a[i];
 
  for (int i = 1; i <= N; i++) l[i] = gcd(l[i - 1], a[i]);
  for (int i = N; i >= 0; i--) r[i] = gcd(r[i + 1], a[i]);
 
  int ans = 1;
  for (int i = 1; i <= N; i++) ans = max(ans, gcd(l[i - 1], r[i + 1]));
 
  cout << ans << endl;
  return 0;
}

D - Flipping Signs

考えたこと：

・上手くやれば、数個を除いてそれ以外を最適化できるのではないか？

・ＤＰ

１つ目も考えましたが、結局ＤＰに走りました。

ＤＰには自信があったからです。（ＤＰまとめこんを最近やったので）

今はもう。

解説：

dp[i][k]:=今i番目を見ていて、i番目をひっくり返すか否か。(k=0ならひっくり返さない、k=1ならひっくり返す。）　と定義します。

それぞれの数字の符号は、前に戻ってひっくりかえすことはないので順に考えることが出来ます。

実装：

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

signed main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++) cin >> a[i];

  static int dp[101010][2];
  dp[0][0] = 0;
  dp[0][1] = -INF;

  for (int i = 0; i < N; i++) {
    dp[i + 1][0] = max(dp[i][0] + a[i], dp[i][1] - a[i]);
    dp[i + 1][1] = max(dp[i][0] - a[i], dp[i][1] + a[i]);
  }

  cout << dp[N][0] << endl;
  return 0;
}

本番ではメモ化再帰でごちゃごちゃしていたのですが、適当に書いたので上手くいきませんでした。（←最悪なやつです。）

この問題は冷静に見ても、今の私には解けなかったと思います。（ＤＰで解く場合。）

もっと遷移を見て、丁寧にＤＰをするべきでした。

勉強になりました。

感想：

今回のブログは感情が入り乱れている状態で書いたので、解説ブログではなく日記のようになってしまいました、すみません。

結果は二完でした・・・

勝ち筋としては、Ｃをしっかり通してからＤを丁寧に解いていれば・・・という感じです。（しかし、終わったことです。）

調子の悪いときに如何に精進するかが肝だと思うので、頑張りたいと思います！