ABC205の感想
AtCoder Beginner Contest 205に参加しましたのでその感想を書いてきます。問題はこちらから。
結果はこんな感じでした。
ABCD（43:49+2WA）
順位：2094 / 8834
パフォーマンス：1073
レートは下がりましたが、まあ良くできたのかなと思います。D問題が茶色diffらしいですが、いつも解いている茶色よりは難しかったと思いますし、E問題の考察も面白いところまで詰めることができたと思います。解けなきゃ０点なので、なんとも言えないですが、次の段階が見えてきたという感じですかね。
感想行きます。
A問題
小数点の問題で少し焦りました。でも、あまり難しいことは考えなくてもいいですね。
A*B/100
でおしまいです。一応、doubleで受け取っておいたので、計算過程で切り捨てられることはない、ことは意識しました。
B問題
同じ配列を作ります。これは数が重複なく出現すればいいですね。出現を監視しながら新たに出てきた数字をカウントしましょう。
それがN種類あったらYesを出力します。
このとき、Yesの大文字小文字には最新注意を払いました。
C問題
powの問題です。久しぶりにこういう問題が来てドキドキしました。問題を見てから決意までは速かったです。
全部場合分けをしよう
ということでif文です。いっぱい書きました。まずはCの偶奇です。偶数なら、AとBの絶対値の大小で比べられます。奇数の時はもっとうまく場合分けをします。
一応実装はできましたが、コーナーケースが怖くて5分ぐらい試してました。特に問題も見当たらず、提出。無事ACです。
D問題
この問題に突入した段階で1000人以上が既に解いていたと思います。ちょっと焦りました。それも相まって、問題を見た瞬間に、mex（minimum exclude）の問題でライブラリを貼れば一瞬だと考えました。ただ、悲しいことにmexのライブラリは作っていません。これは困りました。
と思ったのですが、よくよく読んでみるとMexじゃありませんでした。少しだけ安心です。
早い段階で次の方針が立ちました。
二分探索で X を決め打ちする。細かい添え字は気合で合わせる。
早速実装です。大体の二分探索は5分ぐらいで書けました。
ここから気合です。OKの条件の = を付けたり消したり、lower_boundやupper_boundを試したり、OKの値の±1ぐらいを出力してみたりと、色々やりました。結局、=はつけないで、upper_boundで、OK+1とやると無事答えになります。
早速提出。
あまりにもWAが多すぎて「AtCoder壊れたか？」と思いました。先週に引き続き嘘解法を投げてしまったかもしれません。
さて、デバッグです。コードを睨むとすぐにバグが見つかりました。入力をintで取ってました。このミス定期的にやりますね。どうにかならないもんなんですかね。
long longにして提出。
先ほどから綺麗にACとWAが入れ替わりました。この時点で、解法は合ってそうだなとなりました。コーナーケースを疑ったんですが、これといってやばそうな入力はなく、どうしようかなと悩みました。5分ぐらい悩んだところで、二分探索の最大値が間違ってることに気が付きました。最大値は
1e18+1e5
ぐらい必要ですね。これを直して無事AC。焦りました。
E問題
F問題の方が「正答者/提出者」の割合が大きかったので先にFを見てました。でも5分ぐらいで帰ってきました。
ボールを並べます。まずは、20分ぐらいお絵描きをしてました。
DFSでやっても計算終わらなさそう。
枝刈りしても大変そう。
dpなんじゃないか？
制約小さければ解けるのにな
と考えたあたりで、
これ、総数からNG数を引くんじゃないか
とひらめきました。結果的にはこのアプローチは合ってました。ということで、NGになる条件を考えます。例えば、3個目のボールでNG時には、3個目までのボールの種類は一意に決定するし、4個目以降はその全ての組み合わせがNGとなるため、O(1)で求めることが可能となります。
i 個目でNGとなるので、i 個目より前ではNGになってはいけません。とすると、2個ずつ組み合わせがシフトするなーと考えて、それを前計算しておきました。i個目より後ろは余ったボールの組み合わせの計算で答えが求まります。
これを、0->N-1まで行えばO(N)で答えが求まります。
ですが、ここで時間切れです。残念ですね。
F問題
ちらっと見ました。
Nクイーン問題って知っていますでしょうか。あんな感じなんかなーって考えて、黙ってEに戻りました。
あとがき
結果としては、あんまりという感じですが、コンテスト中の立ち回りとしてはなかなかに良かったんじゃないかなと思います。なによりも、成長を感じましたし、ちょっと上の段階が見えたような気がします。
E問題はどうやら黄色だったようですね。ぼくが初めて考えた、黄色は今でも覚えています。ARC104の「Fair Elevator」です。一応解説も書きました。もう難しすぎて、解くのに3日解説に２日とかかかりました。
それをなんかいい感じに考察出来ているのは、感慨深いですね。おkんテスト中に通せるかといわれるとまだ微妙ですが、各日にやつらを追い込んでいます。いつか倒せる日が来ることを信じて頑張ります。
この記事が気に入ったらサポートをしてみませんか？