数式に弄ばれた男の備忘録です
コンテスト概要
オムロンプログラミングコンテスト2025（AtCoder Beginner Contest 397）
開催日:2025年1月11日 21:00-22:40
A - Thermometer
考察
if-elseの練習問題。だが、初心者的には出力や小数というこまごましたトラップが多い。
この後の複雑さを物語るかのようなA問題だった。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
float n; //入力は小数なのでintでとらない
cin >> n;
if(n >= 38.0) cout << "1" << endl;//38度以上なら1番
else if(n >= 37.5) cout << "2" << endl;//38度以上ではなく37.5度以上なら2番
else cout << "3" << endl;//それ以外なら3番
}
B - Ticket Gate Log
考察
ioio...の順になるように前から順に確認したい。
まず、直前に見た文字を持っておく(最初はoにする)
直前の文字と今の文字が同じ場合、間に別の文字を挟む必要がある。
最後がiであるときに気を付けながら、間に文字を挟んだ回数が答え。
ちょっと混乱し汚く無駄のあるコードに。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
//ひとつ前の文字
char now = 'o';
int ans = 0;
for(auto x:s){
//前の文字と同じなら間に挟む
if(x == now) ans++;
else{
//違うなら文字を更新する
if(now == 'i') now = 'o';
else now = 'i';
}
}
//一番後ろがiならoが必要
if(s.back() == 'i') ans++;
cout << ans << endl;
}
C - Variety Split Easy
考察
なんだかんだ一番簡単だったかもしれない。
前からと後ろからで種類数をメモしておく。あとは順番に和の最大値を求めればOK。
一応空集合は足してはいけないのだが、どうせ空集合を足したところで1番にはなれないのでさほど注意する必要はなかったり。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<int>num (n);
for(int i=0;i<n;i++) cin >> num[i];
//前からと後ろからの種類を管理する配列
vector<int> fr (n+1,0),bc (n+1,0);
set<int> st;
for(int i=0;i<n;i++){
//setに突っ込めばsize=種類数になる
st.insert(num[i]);
fr[i+1] = st.size();
}
st.clear();
for(int i=n-1;i>-1;i--){
//後ろから見るときは添え字に注意
st.insert(num[i]);
bc[i] = st.size();
}
int ans = 0;
for(int i=1;i<n;i++){
//足して最大値を見る
ans = max(ans,fr[i]+bc[i]);
}
cout << ans << endl;
}
D - Cubes
考察
シンプルに$x$を$10^6$まで調べるもWA10。
というのも$x^3-y^3\leq10^{18}$の時$x\leq10^6$は必ずしも成り立たない。
この方針の場合$5.8\times10^8$程度必要になる。この時$x^3$は$10^{25}$くらいになるので少々無茶である。
だからうまく計算式をいじる必要があったんですね(敗北)
E - Path Decomposition of a Tree
考察
末梢から見ていけば何とかなりそうとE問題から取り掛かる。
方針としては葉である頂点から隣接頂点にパスの数を伝え葉を刈る。
頂点のパス数がKを越えたら失敗。Kぴったりならそこを1つのパスとして取り除く。
で進めるもがっつり枝分かれを許しており1ペナ。
伝えられた頂点の数を管理しやすいようにDFS。
で伝えられた頂点が2つの時Kピッタリ以外だと失敗であることを見落とし2ペナ。
いい感じに修正してAC。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n,k,siz;
string ans = "Yes";
vector<bool> gone;
vector<vector<int>>path;
int DFS(int pos){
//到達フラグを立てる。
gone[pos] = true;
int ct = 0,sum = 1;
for(auto x:path[pos]){
//すでにフラグが立っているなら無視。
if(gone[x]) continue;
int s = DFS(x);
//パスが完成していないなら合計に加算
if(s != 0){
ct++;
sum += s;
}
}
//3点以上つながっているなら失敗
if(ct > 2) ans = "No";
//パスの長さがKを越えているなら失敗
if(sum > k) ans = "No";
//2点つながってるのにパスの長さがKじゃないなら失敗
if(ct == 2 && sum != k) ans = "No";
//パスの長さがKなら刈り取る。
if(sum == k) sum = 0;
return sum;
}
int main(){
cin >> n >> k;
siz = n*k;
gone.resize(siz,false);
path.resize(siz,vector<int>(0));
for(int i=0;i<siz-1;i++){
int x,y;
cin >> x >> y;
x--,y--;
path[x].push_back(y);
path[y].push_back(x);
}
//パスの長さが余っているなら失敗
if(DFS(0) != 0) ans = "No";
cout << ans << endl;
}
結果
ABCE(3) 4完 69:34
順位 1332位
パフォーマンス 1448
感想
4完で1300位というなかなかに怖い回。
3完なら3000位というのも怖さに拍車をかける。
逆にこういう回のほうが差がついていいのかもしれない。
...いや、不安になるから普通でお願いします。