ABC275感想など

ABC275の感想や解法についての言及です。
C++の人向けです。

人生初6完でした！！！
やったぜ！！

がんばった

A問題

A - Find Takahashi

最大の橋が何本目か出力してね。

C++では max_element という関数を用いることで簡潔に書くことができます。

#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> H(N);
  for(auto&& h : H) cin >> h;
  cout << max_element(H.begin(),H.end())-H.begin()+1 << endl;
}

詳しく知りたい人はイテレータを調べてみるとよいです。

B問題

B - ABC-DEF

$${A\times B\times C-D\times E\times F \mod 998244353}$$ してね

制約を見ると、
$${0 \leq A,B,C,D,E,F \leq 10^{18}}$$ とあるので、オーバーフローに注意が必要だとわかります。
そこで、$${\mod}$$ はどこでとっても結果は変わらないことを利用します。
よくわからない人はここを見るとよいです。
また、C++では負の数に対する$${\mod}$$は負の数になってしまうので、注意が必要です。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr ll mod = 998244353;
int main(){
  ll A, B, C, D, E, F;
  cin >> A >> B >> C >> D >> E >> F;
  A %= mod, B %= mod, C %= mod;
  D %= mod, E %= mod, F %= mod;
  ll a = A * B % mod * C % mod;
  ll b = D * E % mod * F % mod;
  cout << (a - b + mod) % mod << endl;
}

C問題

C - Counting Squares

$${9\times 9}$$のグリッドにポーンがあるから正方形が何個あるかを確かめてね。

実装はがんばってください。
気合です。

僕の方針は、左上と左下のポーンを全探索→ベクトル的に残りの$${2}}$$つのポーンをチェックするにしました。

Cは書き直すのが面倒なので、いろいろ割愛します…

int main() {
  vector<string> S(9);
  for(auto&&s:S)cin >> s;
  ll ans = 0;
  auto ng = [](int a) { return a < 0 || a >= 9; };
  // 左上
  rep(r1, 9) rep(c1, 9) {
    if (S[r1][c1] == '.') continue;
    // 左下
    REP(r2, r1, 9) REP(c2, c1 + 1, 9) {
      if (r1 == r2 && c1 == c2) continue;
      if (S[r2][c2] == '.') continue;
      ll dr = r2 - r1, dc = c2 - c1;
      ll r3 = r1 - dc, c3 = c1 + dr;
      ll r4 = r3 + dr, c4 = c3 + dc;
      if (ng(r3) || ng(c3) || S[r3][c3] == '.') continue;
      if (ng(r4) || ng(c4) || S[r4][c4] == '.') continue;
      ans++;
    }
  }
  cout << ans << nl;
}

D問題

D - Yet Another Recursive Function

こんな感じの関数があるから計算してね～

見ればわかりますが、わかりやすくメモ化再帰しろって言われています。
フィボナッチ数列を再帰で解いたことのある人は、すぐに気づいたのではないでしょうか？
素直に $${f(x)}$$ を定義してしまうと何回も同じ計算をするために無駄に時間がかかってしまうのを、メモ化して改善するものです。
今回は最大値がとても大きいのと、使わない値が多そうなのでmapを使います。

また、$${\lfloor \frac{k}{2} \rfloor}$$と$${\lfloor \frac{k}{3} \rfloor}$$ に着目すると、調べられる数は極めて少ないことがわかり、十分高速に動作します。

using ll = long long;
map<ll,ll> memo;
ll rec(ll k){
  if(k==0) return 1;
  if(memo.count(k)) return memo[k];
  return (memo[k/2] = rec(k/2)) + (memo[k/3] = rec(k/3));
}
int main(){
  ll N;
  cin >> N;
  cout << rec(N) << endl;
}

E問題

E - Sugoroku 4

確率を計算してね

さあ、久しぶりなせいで書くのが面倒になってきました。
制約を見ます。DPっぽいですね。DPをします。
書いている私は実装をバグらせまくりました…
結果、$${N}$$番目の更新忘れだったのですが、なんかいろいろしてたら通ったので、そのまま書きます。

$${dp[i][j]\coloneqq i}$$ 回ルーレットを回して $${j}$$ にいる確率とします。
僕は配るDPで各出目 $${k}$$ に対して$${dp[i][min(j+k, 2*N-(j+k))]\text{+=}\frac{dp[i][j]}{M}}$$と更新するようにしました。

#include<atcoder/modint>
using mint = modint998244353;
int main() {
  ll N, M, K;
  cin >> N >> M >> K;
  // dp[i][j]:=i回目のルーレットでjにいる確率
  vector dp(K + 1, vector<mint>(N + 1));
  dp[0][0] = 1;
  mint ans;
  mint div = mint(1) / M;
  rep(i, K) {
    //元のマス目
    rep(j, N) {
      // 出目
      REP(k, 1, M + 1) {
        // 次のマス目は j+k か 2N-j-k
        ll next = min(j + k, 2 * N - j - k);
        dp[i + 1][next] += dp[i][j] * div;
        if (next == N) ans += dp[i][j] * div;
      }
    }
  }
  cout << ans.val() << nl;
}

F問題

F - Erase Subarrays

なんやかんやしてね。

DPをします。
左から使うか使わないかを決めていくと、一般的なナップサックDPです。
そこに、最小で何回かの情報を持たせます。
その時に、連続しているかの情報も必要なので、それも持たせます。

よって、次のDPをしたくなります。
$${dp[i][j][k] \coloneqq i}$$ 番目まで見て総和が $${j}$$ で $${k}$$は$${A_i}$$を使ったか としたときに必要な操作回数の最小値
実際にこのDPはうまく動きます。

int main() {
  ll N, M;
  cin >> N >> M;
  vll A(N);
  for(auto&& a : A) cin >> a;
  // ☆方針☆
  // dp[i][j][k]:=iまで見て総和をjとしたときに必要な操作回数の最小値
  // ただし、k=1の時iを使い、k=0の時iは使わない。
  vector dp(N + 1, vvll(M + 1, vll(2, INF)));
  dp[0][0][0] = 1;
  dp[0][0][1] = 0;
  rep(i, N) {
    rep(j, M + 1) chmin(dp[i + 1][j][0], min(dp[i][j][1] + 1, dp[i][j][0]));
    rep(j, M) {
      if (j + A[i] > M) continue;
      // 配るdp
      chmin(dp[i + 1][j + A[i]][1], dp[i][j][1]);
      chmin(dp[i + 1][j + A[i]][1], dp[i][j][0]);
    }
  }
  auto ans = dp[N];
  REP(i, 1, M + 1) {
    ll a = min(ans[i][0], ans[i][1]);
    cout << (a < INF ? a : -1) << endl;
  }

まとめ

今回、とんでもDP回でしたね(DもDPみたいなもんだよね)。
なんかいい感じにできてよかったなーと思っています。

実は今回大成功回で、再入水・初青パフォ・コンテスト中初6完を達成しました！
前回の入水は次の日に落緑したこともあり…つらかったので、入水記事書こうかな…？と思っています。

以上です。