コンテスト
A問題
感想
Sを順番に見ていって、a,e,i,o,uのいずれかならスキップ、それ以外は出力する。
コンテスト中提出コード
int main() {
string s = in_str();
fore(si,s){
if(si=='a' || si=='i' || si=='u' || si=='e'||si=='o') continue;
else{
cout << si;
}
}
cout << endl;
return 0;
}
B問題
感想
真ん中の日を$mid=sum(D_i)$とする。
また、月の初期値を1とする。
$D_i$を順番に見ていって、$mid <= D_i$なら月とmidを出力する。
そうでないなら月を1足して、$mid-=D_i$にする。
コンテスト中提出コード
int main() {
ll m = in_ll();
vll d = in_vll(m);
auto sd = sum(d);
ll mid = (sd+1)/2;
ll t = 1;
fore(di,d){
if(mid <= di){cout << t << ' ' << mid << endl;break;}
else{ mid-=di;t++;}
}
return 0;
}
C問題
感想
Nカップのアイスの中から2つ選んで満足度を最大化する。
満足度の定義を見ると、一番美味しいアイスは確実に選ばれる。
なので、一番美味しいアイスと他のアイスで計算して一番満足度が大きいものを出力する。
本番中は考えてなかったけど、美味しさが最大のアイスが複数ある場合も考える必要があった。
結果的には一番美味しいアイスの種類はなんでも良い。
美味しさが最大で種類が違うアイスがある場合、最大としてどちらを取ってももう一方の種類とのペアは探索することになり美味しさの最大値は変わらない。
美味しさが最大で種類が同じアイスがある場合、最大としてどちらを取っても結局ペアを探索することになり美味しさの最大値は変わらない。
実装としては、Sの昇順でソートして一番後ろを美味しさ最大のアイスとする。
配列の$0$から$N-1$まで最大と、$i$番目のアイスの満足度を計算し、最大の満足度を求める。
ソートの計算量が一番大きく、計算量は$O(NlogN)$となる。
コンテスト中提出コード
int main() {
ll n = in_ll();
vector<pair<ll,ll>> fs(n);
ll f,s;
rep(i,n){
cin >> f;
cin >> s;
fs[i] = mp(s,f);
}
sort(all(fs));
auto tp = fs[n-1];
ll ans = 0;
rep(i,n-1){
if(tp.second == fs[i].second) { chmax(ans, tp.first+(fs[i].first/2));}
else{chmax(ans, tp.first+fs[i].first);}
}
print(ans);
return 0;
}
D問題
感想
解法がわからなかったのでコンテスト中はスキップした。
単純にやると1手続きあたり$O(HW)$の計算回数がかかる。
1手続きで印をつける最低の行または列は1つなので、最大で$H+W$回かかる。
なので、合わせて$O(HW(H+W))$かかる。
単純な方法では間に合わない。
公式解説を見ると色別に管理するといいらしい。
色はアルファベットになっているので26種類ある。
縦横それぞれにどの色がいくつあるかカウントしておく。
こうしておくと、1手続きあたり$26(H+W)$になる。
なので、合わせて$26(H+W)^2$になり間に合う。
実装で大事そうなことを書いておく。
- 色が1種類か判別するために、行と列の残り個数を計算しておく。残り個数と一致する色があれば、色が1種類だとわかる。
- 印をつける操作は行と列それぞれを調べた後なので、どの行or列がどの色で1色だったのか覚えておく必要がある。
- 印をつける操作は行と列ごとに管理する。例えば行$i$に印をつける時$x[i]=true$にするなど。
- 行に印をつける時は、各列から印をつけた色の個数を引く必要がある。
E問題
感想
ある本を読むには他の本を読んでいる必要があり、本1を読むためにはどのような順で本を読めば良いか、という問題。
適切な順序を選ぶことで全ての本を読むことができると書いてあるので、読むべき本を順に辿っていっても循環することはなく、前提が必要ない本に行き着くはず。
$i$番目の本を読む前提になっている本$P_{i,j}を$i$から$P_{i,j}$への辺をもつ有向グラフへと読み替えると、DFSで解ける。
実装としては再帰的に関数を呼ぶようにする。
$i$から行けるところを探索し、探索が終わったら(関数を抜ける前に)その本を読んだとして、$i$を保存しておく。
$O(N+N)$となる。
コンテスト中提出コード
vector<bool> done;
vll ans;
vvll g;
void f(ll i){
if (done[i] == true)return;
fore(nx, g[i])f(nx);
done[i] = true;
ans.pb(i+1);
}
int main() {
ll n = in_ll();
g.resize(n);
ll c;
rep(i,n){
cin >> c;
rep(j,c){
ll t = in_ll();
g[i].pb(t-1);
}
}
done.resize(n,false);
f(0);
ans.erase(ans.end()-1);
print(ans);
return 0;
}
コメント