ABC389とAHC041の振り返り

今回はアルゴリズム・ヒューリスティックどちらも振り返ります。
## [アルゴA問題](https://atcoder.jp/contests/abc389/tasks/abc389_a)(diff:8) ##
またしても簡単
pythonで書きました
ACコード(python:63ms,c++:1ms)
```python
S=input()
print(int(S[0])*int(S[2]))
```
AC時間:1:05
## [アルゴB問題](https://atcoder.jp/contests/abc389/tasks/abc389_b)(diff:25) ##
$X!=N$ であるような $X$ を求めるだけです。何回かループ回せばできます。
計算量は $f(x)=x!$ の逆関数を $g(x)$ として、$O(g(x))$ です。
ACコード(1ms)
```c++
#include <bits/stdc++.h>
using ll = long long;
using ull = unsigned long long;
int main() {
  ull X;
  cin >> X;
  ull tmp = 1;
  for(int i = 2; i < 100; i++) {
    tmp *= i;
    if(tmp == X) {
      cout << i << endl;
      return 0;
    }
  }
}
```
AC時間:4:53
## [アルゴC問題](https://atcoder.jp/contests/abc389/tasks/abc389_c)(diff:255) ##
発想はすぐ出ました。しかし僕はここで大きな勘違いをしていました
「* (配列名).end()=配列の終わり」と考えていましたが、実際には「*(配列名).end()=配列の終わりの次の要素」でした。((配列名).at(s-1)(sは(配列名)の要素数)ってすれば間違えなかったのに…)
[発想が似ている問題](https://atcoder.jp/contests/abc335/tasks/abc335_c)をちょっと前に解いていたのでめっちゃ沼らなくて良かったです。計算量は $O(Q)$ です。
ACコード(237ms)
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
  int Q;
  cin >> Q;
  vector<ll> que(1, 0);
  ll len = 0;
  int cnt = 0;
  for(int i = 0; i < Q; i++) {
    int query;
    cin >> query;
    if(query == 1) {
      ll l;
      cin >> l;
      int s = que.size();
      que.push_back(que.at(s - 1) + l);
    }
    else if(query == 2) {
      len += que.at(cnt + 1) - que.at(cnt);
      cnt++;
    }
    else {
      int k;
      cin >> k;
      cout << que.at(k + cnt - 1) - len << endl;
    }
  }
}
```
AC時間:25:10
## [アルゴD問題](https://atcoder.jp/contests/abc389/tasks/abc389_d)(diff:749) ##
解けませんでした
数学系の中でも幾何学苦手なので強くなりたいです。
入力例3見て「こんなに2025関連の問題を作れるwriterさん達はすごいなぁ」と思いました。
## [ヒューリスティック](https://atcoder.jp/contests/ahc041/tasks/ahc041_a) ##
ヒュでも入茶しました!(記事は書きません)
問題文見た瞬間「atcoder社いくらなんでもクリパ遅すぎでは」と思いました。
問題文を読み進めていると「頂点の座標はスコアに直接寄与はしない」ということが分かりました。実際提出したコードでは $x_i,y_i$ の入力処理をしていません。
初期解は<code>-1</code>をひたすら1000個並べるだけの作業です
```c++
int main() {
  int N, M, H;
  cin >> N >> M >> H;
  //-1をN個出力
}
```
スコア:7584268
次の発想として、BFSをやることにしました。
$0, 1, \dots, N - 1$ の順に、もしまだその頂点が未探索ならその頂点からBFSをする、といった感じでやりました。
```c++
vector<vector<int>> G;
vector<int> dist(1000, -1);
vector<int> par;
int main() {
  int N, M, H;
  cin >> N >> M >> H;
  vector<int> A(N);
  for(int &o : A) {
    cin >> o;
  }
  G.assign(N, vector<int>(0, 0));
  for(int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    G.at(u).push_back(v);
    G.at(v).push_back(u);
  }
  par.assign(N, -1);
  for(int i = 0; i < N; i++) {
    if(dist.at(i) != -1) {
      continue;
    }
    dist.at(i) = 0;
    queue<int> que;
    que.push(i);
    while(!(que.empty())) {
      int v = que.front();
      que.pop();
      for(int next_v : G.at(v)) {
        if(dist.at(next_v) >= 0) {
          continue;
        }
        if(dist.at(v) == H) {
          continue;
        }
        que.push(next_v);
        dist.at(next_v) = dist.at(v) + 1;
        par.at(next_v) = v;
      }
    }
  }
  //parの内容を順に出力
}
```
スコア:55988632
なんとなく山登り法的なものをやってみたかったので、色々やりました
- BFSを $N - 1, N - 2, \dots, 0$ の順でする(スコア:55976294、悪化)
- 一般に $a_1b_1+a_2b_2 \le a_1b_2+a_2b_1(a_1 \le a_2,b_1 \le b_2)$ であることから、頂点 $i$ の美しさが小さければ(この時は $A_i <= (Aの平均)$ か?という判定)BFSを行う(スコア:56112492、改善)
- $A_i <= (Aの平均)$ 等の判定をせず、$A$ を美しさを基準にしてソートすることにより、美しさが小さい頂点からBFSを行う(スコア:56212409、改善)
- 両方を結ぶ無向辺のある頂点 $i,j$ について、75%の確率でその2つの頂点を同じ根付き木に所属させる(スコア:乱数固定56098936、完全ランダム56141529、少し悪化)
- 根しかない根付き木の根である「孤独な頂点」を他の根付き木にくっつける(何故かWA、コンテスト中にACを出せなかった)

という感じでやりましたが、最終スコアは$A$ を美しさを基準にしてソートする解法の56212409で最終順位は<strong>723</strong>位でした。
なんとなくヒューリスティック的な考え方というものが掴めてきた気もします。
2025/01/20追記:[terry_u16さんのスライド](https://speakerdeck.com/terryu16/ahc041jie-shuo)によると、BFSよりDFSのほうがスコアが良かったようです
## 感想 ##
パフォーマンスはABC389が642、AHC041は1019でした。
本当にアルゴリズムの方がちょっとやばいですね…
C問題のようなことにはならないよう今後気をつけます。