初めまして、SAIと申します！
本日より毎週、Atcoderのコンテストの参加記録をつけていきます！
まだまだ初心者ですが、少しでも競技プログラミングをやってみようとか思っている人がいれば見てほしいです。
Atcoderとは、日本最大級のプログラミングコンテストサイトです！多数のコンテストがあり、参加することによってレートが変動し、レートによってランクが決まります。このランクが近年では、多数のIT企業で就活に利用できます。
一般的には、数学とプログラミングを合わせたものが競技プログラミングといわれます。それほどまでに、論理的思考力が求められる世界ではあるため、論理的思考が苦手な方にはうってつけだと思います。ランクは色で分けられており、次のような順番で存在しています。
黒色→灰色→茶色→緑色→水色→青色→黄色→橙色→赤色
問題のランクも上の色で分けられており、例えば茶色レベルの問題であれば、茶diff'(difficultyの略)と表現されます。
青色以上ははっきり言って次元が違います。
私はもうすぐで緑コーダーの茶色コーダーです。(各色にいる人間のことを○色コーダーといいます。)
自分の復習と記録のために今後もここに記録していきます！少しでも何かお役に立てればうれしいです！
2021/01/23 21:00から開催されたAtcoder Beginnner Contest 189に参加をしてきました！
今回の結果としてはA, B, Dしか解けず😢
緑パフォーマンスは出たものの、満足のいく結果ではありませんでした。
C問題に時間をかけてしまったのが原因でした。
自分はパイソニスタなのですが、C問題はややオーダーが厳しかったです...
以下、問題を振り返っていきます！
- Slot
A問題ですので、とても簡単な問題です。標準入力さえ理解していれば、難なく解けるのではないでしょうか。
-
Alcoholic
二回もWAを出してしまった問題。久々のコンテストだったからか浮動小数点演算による誤差を考慮していなかったのが原因です。
誤差にさえ気づければあとは簡単。例1を考えてみましょう。
n=2, x=15で、アルコール飲料は二つ存在し、一つ目が200mlで5%、二つ目が350mlで3%です。
普通に考えれば、アルコールの量を求め、その合計量とxを比較する方法が思いつきます。
これを愚直に実装すると、次のようなプログラムとなります。
しかしこの方法を用いると、ループ内の除算によって、浮動小数点演算による誤差が生じていしまいます。
浮動小数点演算による誤差とは、割り算をした際に言語ごとに表現できる桁数に制限があり、それを超えてしまった際に生じる切り捨て誤差です。競技プログラミングではよくある問題ですので、よければ心にとどめておいていただきたいです。
これを回避するために、除算の乗算化を行います。そうすると、プログラムは次のようになります。
ここまでくれば、実装難易度自体はA問題と変わらないと思います！
-
Mandarin Orange
愚直に考えると、l, rを決定するために、次のように二重ループによる解法が思いつきます。
しかしこのプログラムだと、リスト内参照を含め、オーダーがおよそn^3となり、今回の制限時間である1.5秒に間に合いません。そこで、次のようにプログラムを改変します。
このように、改変することによって、毎回最大値を更新し続けることによって、オーダーをn^2程度に収めることができ、TLEにならずに通すことができます。
シンプルなループ回数の削減と時間削減問題でしたが、文章の癖が強く、苦戦した人も多かったのか茶difでした。
-
Logical Expression
この問題は、問題を以下に解釈し直すかが問題となってきます。まず考えるのがANDの場合の処理についてです。この場合、ともにTrueでなければなりません。逆にORであればともにFalseである場合を除いて、求める出力が可能となります。
したがって、次のようなプログラムが考えられます。
このプログラムでは、まず最大でも2^(n+1)通りしか存在しないことを理解しなければなりません。すべてがORであった場合、すべての値がFalseである場合以外が条件を満たすため、そのような考えに至ります。
そして次に、本プログラムではANDの場合の処理についてのみを考慮しています。なぜならORの場合は、すべてがFalseになる場合のみが条件を満たさないからです。ANDの場合は、ANDが出てきたのが何回目かに着目し、その回数を2の指数とした分だけ減らします。これは、解説のように漸化式的に表現をすることによって解釈をすることも可能ですが、私は次のように解釈をしました。
ANDが出てきた瞬間に先にも述べましたが、ともにTrueでなければ条件を満たしません。それゆえに、可能性はその時点で半分に減少し、さらにそれ以前の事象も考慮すると、2^(ANDが出てきた回数番号)分だけ減少すると解釈できるのです。
これによって、無事ACを勝ち取ることができます。
もう少しやれたかなというのが、正直な感想です。最近別のことで忙しく、あまり練習が出来ていないのが原因なのかも...精進しなければと痛感しました。無事レートは上がったので、今回は良しとしておきます。