ABC202の感想
エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）に参加しましたのでその感想を書いていきます。問題はこちらから。
結果はこんな感じでした。
ABCD(65:43+1WA)
順位：1852 / 8714
パフォーマンス：1154
前回と同じく4完でした。ただ今回は少し悔しいですね。まず、Cで1WAを出したのは大変よろしくないです。コーナーケースではなく簡単なミスでした。また、D問題ももう少しスムーズに行けたと思います。考察自体は5分ほどで済んだのですが、オーバーフローに悩まされました。反省点がいくつかある回でした。
A問題
３つのさいころの裏の目を和を求めます。問題を開いて20秒ぐらいで問題を理解しまして、15秒ぐらいで7から引けば裏の目が求まることがわかりました。そして、入力を受け取っているあたりで、21から目の和を引いた方が速く書けるな、と気づいたため、そんな感じで書きました。
これで提出時間は1:02です。サンプルを試したのはありますが、それでも相当早く書けたと思います。でも、速い人はとんでもないですね。どんな思考でやっているのでしょう。不思議です。
B問題
文字列を180°回転する問題です。
これは6を9にして、9を6にする。そして、文字列の前後を反転させればいいことがすぐにわかりました。
これを実装したのですがなぜか答えが合いません。それもそのはずで、エディタの予測で書いていたのですが
reverse(s.begin(),s.end())
とするところが
s.reserve()
となっていました。地味にこのミスに気が付かずなかなかに時間を消費ました。これを修正して無事ＡＣ次に進みます。
C問題
A[i]とB[C[i]]で一致する個数を求めます。
愚直にやるとO(N^2)ですので、どうやったら線形になるかを考えました。結局は一致するインデックスというよりかは、どの数字で一致するかに着目すればいいんじゃないか、という考えに至りました。
A[i]とB[C[i]]でどの数字が何回出現するかカウントしてそれを掛ければ答えです。
このとき、かけ合わせる数字を n までとしてしまい1WAでした。実装の時に出現する最大の数を N = 1e5 としていたために、n と混同しました。MaxのMとした方がよかったかもしれません。注意力の問題ですが、ミスや勘違いをしない書き方を常日頃から意識したいです。
D問題
aとbを辞書順に並び替えます。
この問題を見たときに真っ先に2回前のABCのE問題が思い浮かびました。
要はこれの簡単版です。ですので、割とあっさり考察は終わりました。5分ぐらいでしょうか。
ただ、combinationの計算に永遠と時間がかかりました。いつもはmodintに頼りっきりなのでオーバーフローは特に意識していないのですが、計算結果が64bitに収まる場合に、計算過程でオーバーするときの処理を書くのに手間取りました。
分子を掛けて、分母を割るのですが、このときに分母を小さい順に割ることにより、必ず余りを出さずに計算することが可能（日本語が下手ですみません）
ということに気づきました。気づいたというよりかこれ以前にも同様の問題で躓きました。これを機にまた復習しておきます。
combinationの不具合を修正したらそのままACまでは一直線。だからこそ、このミスは良くなかったですね。大反省です。
E問題
グラフの問題です。
まず、各頂点の深さを求めます。その深さの頂点数を管理すれば一歩答えに近づけます。
ただ、近づいたところでおしまいでした。ここからなにも考察が進みませんでした。上の頂点数を各頂点に対して適用した情報が欲しかったのですが、これはどうしてもN^2の要素数になってしまいます。計算量以前に、メモリが足りません。
ここで時間切れです。残念。
F問題
見ていませんが、どうやらとっても難しいみたいです。
あとがき
反省の多い回でした。解ける問題はきちんと解くことができましたが、スマートに解く、という点からは程遠いです。この辺が競技プログラミングの競技性の部分なんですかね。言ってしまえば「速く解く」ということなんですが、よりシンプルに、よりバグなくを追求することでゲーム性が生まれています。とっても面白いです。次はよりスマートを意識して臨みます。
色々と書きましたが、レートは伸びたのでよしとしましょう。少しずつですがレートは上がっていますし、パフォーマンスも安定してきています。このまま水色まで行きたいなあ、と思う所存でございます。
この記事が気に入ったらサポートをしてみませんか？