今回はアルゴリズム・ヒューリスティックどちらも振り返ります。
アルゴA問題(diff:8)
またしても簡単
pythonで書きました
ACコード(python:63ms,c++:1ms)
S=input()
print(int(S[0])*int(S[2]))
AC時間:1:05
アルゴB問題(diff:25)
$X!=N$ であるような $X$ を求めるだけです。何回かループ回せばできます。
計算量は $f(x)=x!$ の逆関数を $g(x)$ として、$O(g(x))$ です。
ACコード(1ms)
#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問題(diff:255)
発想はすぐ出ました。しかし僕はここで大きな勘違いをしていました
「* (配列名).end()=配列の終わり」と考えていましたが、実際には「*(配列名).end()=配列の終わりの次の要素」でした。((配列名).at(s-1)(sは(配列名)の要素数)ってすれば間違えなかったのに…)
発想が似ている問題をちょっと前に解いていたのでめっちゃ沼らなくて良かったです。計算量は $O(Q)$ です。
ACコード(237ms)
#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問題(diff:749)
解けませんでした
数学系の中でも幾何学苦手なので強くなりたいです。
入力例3見て「こんなに2025関連の問題を作れるwriterさん達はすごいなぁ」と思いました。
ヒューリスティック
ヒュでも入茶しました!(記事は書きません)
問題文見た瞬間「atcoder社いくらなんでもクリパ遅すぎでは」と思いました。
問題文を読み進めていると「頂点の座標はスコアに直接寄与はしない」ということが分かりました。実際提出したコードでは $x_i,y_i$ の入力処理をしていません。
初期解は-1をひたすら1000個並べるだけの作業です
int main() {
int N, M, H;
cin >> N >> M >> H;
//-1をN個出力
}
スコア:7584268
次の発想として、BFSをやることにしました。
$0, 1, \dots, N - 1$ の順に、もしまだその頂点が未探索ならその頂点からBFSをする、といった感じでやりました。
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で最終順位は723位でした。
なんとなくヒューリスティック的な考え方というものが掴めてきた気もします。
2025/01/20追記:terry_u16さんのスライドによると、BFSよりDFSのほうがスコアが良かったようです
感想
パフォーマンスはABC389が642、AHC041は1019でした。
本当にアルゴリズムの方がちょっとやばいですね…
C問題のようなことにはならないよう今後気をつけます。