ABC400の振り返り

ついにABCも400回目、おめでとうございます
AJL2025summerも始まったので頑張っていきたい

A問題(diff:7)

やるだけ
$400 \equiv 0(\mod A)$ なら $\frac{400}{A}$ 、そうでないなら-1となります。
計算量は言うまでもなく $O(1)$ です。
ACコード(pypy56ms,C++1ms)

A = int(input())
if 400 % A:
  print(-1)
else:
  print(400 // A)

AC時間:1:05

B問題(diff:33)

これもやるだけ
順に $N$ を掛けて足して $10^9$ を超えたらinfとすれば良く、もし全部終わったら総和を出力すれば良いです。
計算量は $O(M)$ です。
ACコード(1ms)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//library end

int main() {
  int N, M;
  cin >> N >> M;
  ll X = 0, p = 1;
  for(int i = 0; i <= M; i++) {
    X += p, p *= N;
    if(X > (int)1e9) {
      cout << "inf" << endl;
      return 0;
    }
  }
  cout << X << endl;
}

AC時間:3:55

C問題(diff:702)

面倒そうなのでDを先にやりましたが、この問題は最後らへんまで考察ができましたがそこからACすることができませんでした
答えは $\sqrt{\frac{N}{2}}+\frac{\sqrt{N}}{2}$ になるようです。かなり惜しい

D問題(diff:1026)

多分元ネタ&類似問題
Dのグラフに強すぎる
あるマスにおいて、隣接するマス(もしくは1つ飛ばした先のマス)の状態が#ならコスト1、そうでないならコスト0の辺を張ります(1つ飛ばした先のマスの場合、飛ばしたマスかもう一方のマスの状態が#ならコスト1、そうでないならコスト0)
あとはダイクストラやります、01-BFSをいつか学ぶかもです(多分学ばない)
計算量は $HW(logH + logW)$ です。
ACコード(837ms)

#include <bits/stdc++.h>
using namespace std;
//ここからグラフ探索系
struct edge {
  int to;
  ll cost;
};
edge make_edge(int a, ll b) {
  edge ans;
  ans.to = a, ans.cost = b;
  return ans;
}
using Cost_Graph = vector<vector<edge>>;
using D_heap = priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>>;
//グラフ探索系終わり
//library end

Cost_Graph G;
vector<int> dist(1000100, -1);

int main() {
  ll H, W;
  cin >> H >> W;
  vector<string> S(H);
  for(auto &o : S) {
    cin >> o;
  }
  G.assign(H * W + 1, vector<edge>(0));
  for(int i = 0; i < H - 1; i++) {
    for(int j = 0; j < W; j++) {
      edge e = make_edge(i * W + j + 1, 0);
      e.cost = (S[i][j] == '#'), G[(i + 1) * W + j + 1].push_back(e), e.to += W, e.cost = (S[i + 1][j] == '#'), G[i * W + j + 1].push_back(e);
      if(i == H - 2) {
        continue;
      }
      e.to -= W, e.cost = (S[i][j] == '#' || S[i + 1][j] == '#'), G[(i + 2) * W + j + 1].push_back(e), e.to += 2 * W, e.cost = (S[i + 1][j] == '#' || S[i + 2][j] == '#'), G[i * W + j + 1].push_back(e);
    }
  }
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W - 1; j++) {
      edge e = make_edge(i * W + j + 1, 0);
      e.cost = (S[i][j] == '#'), G[i * W + j + 2].push_back(e), e.to++, e.cost = (S[i][j + 1] == '#'), G[i * W + j + 1].push_back(e);
      if(j == W - 2) {
        continue;
      }
      e.to--, e.cost = (S[i][j] == '#' || S[i][j + 1] == '#'), G[i * W + j + 3].push_back(e), e.to += 2, e.cost = (S[i][j + 1] == '#' || S[i][j + 2] == '#'), G[i * W + j + 1].push_back(e);
    }
  }
  int A, B;
  cin >> A >> B;
  D_heap que;
  que.push(make_pair(0, (A - 1) * W + B));
  while(!que.empty()) {
    pair<ll, int> v = que.top();
    que.pop();
    if(dist[v.second] != -1) {
      continue;
    }
    dist[v.second] = v.first;
    for(edge next_v : G[v.second]) {
      if(dist[next_v.to] != -1) {
        continue;
      }
      que.push(make_pair(v.first + next_v.cost, next_v.to));
    }
  }
  int C, D;
  cin >> C >> D;
  cout << dist[(C - 1) * W + D] << endl;
}

AC時間:66:19

E問題(diff:1226)

$2^{k - 1} * 100 (k \in \mathbb{N})$ 回目のABCで、「Ringo's Favorite Numbers $k$」が出題される説

感想

久々の緑パフォ&瓦取り返し(パフォ1000,レート723)
AJLも好調な滑り出しになったのでこの調子をキープしていきたいです。