AtCoder abc399 振り返り
AtCoder Beginner Contest 399 の振り返りです。
ABC399の振り返りです。 今回はABCの3問が解けたものの、C問題を後回しにしてしまいACまでに時間がかかってしまったため順位がふるわずレーティングを下げてしまった。
A Hamming Distance: Solved
与えられた同じ長さの２つの文字列のハミング距離を求める問題。ここでハミング距離とは、前からn番目同士の対応する文字が異なる個数のことを指す。
特になんの捻りもなく二つの文字列の文字を前から一文字ずつ比較していき、異なる文字の個数をカウントしていくだけ。
B Ranking with Ties: Solved
1〜N番目の人の得点からランキングを出力する、ただし同じ得点の場合は同じランキングを出力するという問題。
順番と得点とランキングという３つの情報が混在するため、ちょっとややこしいけれど実践的な問題。
得点と順番をpairを使って、それぞれの情報を保持しておき、得点が同じかどうかを確認しながら順番通りにランキングを表示していく感じ。
int main() {
int n;
cin >>n;
vector<pair<int, int>> p;
for(int i = 0; i < n; i++){
int x;
cin >> x;
p.push_back(make_pair(x,i));
}
sort(p.rbegin(), p.rend());
vector<int> a(n);
int t = p[0].first;
int r = 1;
a[p[0].second] = r;
for(int i = 1; i < n; i++){
if(t == p[i].first){
a[p[i].second] = r;
} else {
a[p[i].second] = i+1;
r = i+1;
t = p[i].first;
}
}
for(int i = 0;i<n;i++){
cout << a[i] << endl;
}
}C Make it Forest: Solved
無向グラフにおいて、閉路のないグラフにするには辺をいくつ取り除けば良いかという問題。
グラフ問題がとても苦手なので、苦戦するかと思いきや全く同じ問題についての解説を見つけたため解けてしまった。 その分、理解も浅いままなので要復習といった感じ。
苦手を意識せず、もっと早く手をつけておけばよかった。
D Switch Seats: Unsolved
解けなかった。。。
pairを要素とするSetを使った問題だということまでは気がつけたのだが、そこから例外ケースやら重複排除やらがうまいこといかず。
しかも与えられているテストケースは早々に通ってしまったので、例外ケースを探し当てなければならなくなったものの、なかなか見つけられず途中で諦めた。
所感
結果としては3問解けて、レーティングが−5という、良くはないけれど、すごい悪いわけでもない微妙な結果に終わった。 今回こそはベストレーティングを更新しようと意気込んで臨んだものの、C問題を後回しにするという判断ミスが響いてしまった。 ちゃんと問題を見極めて、着実に得点しようという基本的な学びを得ました。
そして、次回に向けてグラフ問題の復習をちゃんとしようと思います。