😸
ABC274の個人的な振り返り(A~E問題)
コンテストの振り返り
個人成績
成績：5完2ペナ（82分15秒）
順位：825位
パフォーマンス：1579
レート変化：1598→1596(-2)
パフォーマンスのボーダー
| 2400(理論値) | 2000 | 1600 | 1200 |
|---|---|---|---|
| 6完(ABCDEG)100:56 | 5完40:20 | 5完89:26 | 4完55:55 |
A~G問題の最速攻略時間
| A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|
| 0:36 | 0:48 | 2:29 | 3:48 | 5:20 | 12:02 | 7:02 |
各問題の振り返り
A問題
最速との差：4分52秒（+0ペナ）
自分の解法
誤差がこわかったので
0 埋めのマニピュレータの名前を探すのにてこずりました。
double a, b;
int main(){
cin >> a >> b;
int num = b * 10000 / a;
num += 5;
cout << num / 10000 << "."<<setfill('0') << right <<setw(3) << (num % 10000) / 10 << endl;
}
上位・運営陣に見られた解法・実装
誤差を恐れずに愚直に出力したものがFAだった。[1]
反省点
-
setprecision(3)とすれば小数点以下3 - 誤差には気を付けたいので、FAは見習わないようにする
復習のためにも、コンテストに取り組んでる様子を録画するべきなのかなぁと感じました。
B問題
最速との差：1分11秒（+0ペナ）
自分の解法
int h, w;
char c[1010][1010];
int main(){
cin >> h >> w;
REP(i, h)REP(j, w)cin >> c[i][j];
REP(j, w){
int cnt = 0;
REP(i, h)if(c[i][j] == '#')cnt++;
if(j)cout << " ";
cout << cnt;
}
cout << endl;
}
上位・運営陣に見られた解法・実装
あまり差はありませんでした。
反省点
とくに差が見られなかったので、合格とします。
C問題
最速との差：2分54秒（+0ペナ）
自分の解法
愚直に実装しました。
int n;
int a[202020];
vector<int> g[404040];
int ans[404040];
int main(){
cin >> n;
REPS(i, n){
cin >> a[i];
g[a[i]].emplace_back(i * 2);
g[a[i]].emplace_back(i * 2 + 1);
}
REPS(i, 2 * n + 1)ans[i] = HINF<int>();
ans[1] = 0;
queue<int> q;
q.push(1);
while(!q.empty()){
int cur = q.front();
q.pop();
for(auto to : g[cur]){
if(ans[to] == HINF<int>()){
ans[to] = ans[cur] + 1;
q.push(to);
}
}
}
REPS(i, 2 * n + 1){
cout << ans[i] << endl;
}
}
上位・運営陣に見られた解法・実装
- 親のアメーバに関する答えを持ちながら、入力されるデータをを待てばいい[2]
反省点
- 考察を挟まずに愚直に実装してしまった。
この程度の考察であれば
D問題
最速との差：25分27秒（+0ペナ）
自分の解法
DPをしました。どこかでバグを生んだせいでタイムロスしてしまったのですが、どこか忘れてしまいました。
int n, x, y;
int a[1010];
int geta = 10005;
bool can_move[1010][20010];
int main(){
cin >> n >> x >> y;
REP(i, n)cin >> a[i];
x += geta;
y += geta;
can_move[0][geta] = true;
can_move[1][geta] = true;
for(int i = 0;i < n;i++){
int cur = i;
int nxt = i + 2;
if(i == 0){
can_move[nxt][geta + a[i]] = true;
continue;
}
REP(j, 20010){
if(j - a[i] >= 0) can_move[nxt][j - a[i]] |= can_move[cur][j];
if(j + a[i] < 20010)can_move[nxt][j + a[i]] |= can_move[cur][j];
}
REP(j, 20010)can_move[cur][j] = false;
}
int last_even, last_odd;
if(n % 2){
last_odd = n;
last_even = n + 1;
}else{
last_even = n;
last_odd = n + 1;
}
if(can_move[last_even][x] && can_move[last_odd][y]){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
}
上位・運営陣に見られた解法・実装
反省点
- バグ取りに時間をかけてしまった
考察にはあまり時間がかからなかったので、実装の方針に問題があると感じました。
E問題
最速との差：76分55秒（+2ペナ）
自分の解法
DP[（訪れた都市の集合）][（最後に訪れた都市）][（使ったブースターの数）]
という形のbitDPをしました。計算量は
上位・運営陣に見られた解法・実装
-
std::hypot()を使う[6] - 拾ったブースターの数は、訪れた都市の集合から求まるので、情報として持たなくてよい[6:1]
- そもそも、
2^i
反省点
- 最初、
2^i i
まとめ
DPの実装の遅さが結果に響いているので、DPの問題を精進する際は、実装する速度を上げる訓練を積もうと思いました。
Discussion