2021/1/23に開催されたAtCoder Beginner Contest 189に参加しました。
前回は、なんと灰色diffの問題を落としてしまい痛恨の茶色転落。
今回は、とりあえず緑に復帰できるようにと言う気持ちで臨みました。
AtCoder Beginner Contest 189 - AtCoder https://t.co/eKIoGpoGgG
— devgenjin77 (@devgenjin77) 2021年1月23日
参加します。前回のコンテストで茶落ちしたので、再度緑復帰できるように頑張ります!
今回の結果
そんなこんなで奮闘した結果、今回も安定の4完で終了です。
が、、パフォーマンスの方は上々の結果で、なんとか緑に復帰することができました!
devgenjin77さんのAtCoder Beginner Contest 189での成績:2206位
— devgenjin77 (@devgenjin77) 2021年1月23日
パフォーマンス:1108相当
レーティング:792→828 (+36) :)#AtCoder #ABC189 https://t.co/aJdz4dIhS1
4完緑パフォでまたまた緑復帰!😂
今度こそ、茶落ちしないように明日からも頑張って精進します!
振り返り
C問題でやや手間取りまして、結局E問題を解く時間もありませんでした。
A問題
且つかどうかを判定するだけ。問題なくAC。
B問題
お酒の量がmlで、アルコール度数が%の時、アルコールが何ml入っているかを計算して合算する問題。
そのまま計算すると、小数以下の値の計算で誤差が出ておかしくなる可能性もあるので、全て整数演算で済ますように工夫すればよい。
ということで、アルコール摂取量の上限を100倍し、の合計値と比較すれば問題ない。こちらも問題なくAC。
C問題
区間の最小値を求めるということで、セグ木使わせる系の問題!?と少し戸惑ってしまった。ここ最近のABCコンテストのCにしては、少し難易度が高めなんじゃね?
とか思いつつ、とりあえず使い慣れないセグ木を使ってみたら、これがサンプルすら通りません。
デバッグしながら、色々悩んでみたが、どうもセグ木の使い方が間違ってたということが判明。間違いを修正してなんとかサンプルが通る実装を完成させました。
んで、意気揚々と提出してみたら、これがなんとTLE。。。
それから、ループの回し方をなんとか小手先で修正してみたらなんとか1sec超えの結果ではありましたが、なんとかACを取ることができました。やれやれ。。
コンテスト後に改めて見直してみると、実はセグ木使わなくてもOKだったり、普通に工夫してループ回せば200ms程度でACできてたりと、全然考察がイケてないことが判明しましたー。まだ精進が足りないねえ。
D問題
見た目結構むずそうだったので、気後れしたが、なんとか解法を思いつきました。
dp[i][j]=i回目の演算が行われた時にTRUE(j=1)、またはFALSE(j=0)になる場合の数として、漸化式を以下のようにしたDPを考えました。
のとき
- dp[i][1]=dp[i-1][1]
- dp[i][0]= - dp[i-1][1]
のとき
- dp[i][0]=dp[i-1][0]
- dp[i][1]= - dp[i-1][0]
これで最後に、dp[N][1]を出力すればOK。
一瞬、今回Dはムリかもなどと考えていたが、なんとか4完は確保できました。
E問題
DでACを取ったのが、残り時間あと20分と少しというところ。
順位表では明らかにEの方がAC数が多かったので、とりあえず残り時間はE問題に賭けることにしました。
しかしながら、問題を見てみると実装が重そうな問題で、TLEを避けようと思ったら、クエリをソートするとかしないと難しそうな雰囲気。実装をあれこれ悩んでるうちに、時間切れとなりました。
F問題
問題文すら見てません。
これまでの実績
再度の緑復帰、しかしながら少しでも気を緩めてしまえば再度茶色転落の危険があるので、まだまだ喜んではいられません。
総括
今回のABCや最近のARCなどを見ると、今年は少しコンテストの難易度が上がっているような気がします。参加者のレベルが上がるのに合わせて問題も難しくしているような印象ですが、だとすると、自分もレベルを上げ続けていかないと現状のレートを維持するのも難しいという事になるのでしょうか。
ま、いろいろ考えるところはありますが、とりあえずは日々精進していくしかないというところでしょう。
というわけで、また、次回も頑張ります。