おはようございます。しほみんです。
最近、やってなかった競技プログラミングについて振り返ります。今回は参加したくせにひどい成績でした。
ちゃんと振り返りたいと思います。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは1000程度になりました。緑中堅へ。
・C#でクラスとかつかってアプリケーションは作れます。
・pythonで自然言語処理勉強中....。
＜Atcoderでのスタンス＞
・アルゴリズムについて問題でいろいろ学ぶ。第3回PAST70点で中級取得。
・基本的に本番でやっている。現在60回以上参加、2年目。
・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスは1000以上、できれば水色（1200以上）は欲しい。
今回はABしか解けませんでした....マジでてんぱってしまったので反省してます。CもDもちゃんと解けたのに...レートも920まで下がっちゃいましたね。再起図ります。
E問題はどうやら行列の回転対称動作みたいですね（まあ余力なのでスルーします）
今回はA,B,C,D問題を解説します。
ここから問題です。問題は簡潔に書いています。
A問題
スロットマシーンで3文字出されます。
どれも同じ文字の場合あたりです。
その判定を行ってください。
string型で読み込めば、s[0],s[1],s[2]で分離できます。
なのでs[0] == s[1]かつs[1] == s[2]であれば、Win
そうでなければ、Lostにすればよいです。
B問題
お酒をN杯飲みます。
各杯、量はVi ml, アルコール度数はP%です。
お酒の許容量はx mlです。
このとき、許容量を超えるのは何杯目ですか？
普通に頭からアルコール摂取量を計算して、足していきます。
毎回判定を入れて途中、アルコール量が許容量を超えたら、その飲んだ数を出せばよいです。
ただし、数値判定には注意が必要です。今回、アルコールは小数になります。
プログラミングの世界って小数の処理が苦手なのです。（厳密に表記できないので）
だから、素直に100倍して、整数の状態で判定します。
つまり、ViPiを足していって、これが100x超えたらアウトとすればよいです。
C問題
N枚の皿の上にみかんがAi個乗っています。
ここで、l<=i<=rを満たすi番目のお皿のミカンをx個ずつ取ります。（ただし、すべてx個以上ミカンが乗っています。）
このときとれるミカンの数を求めなさい。
まあ、はいやらかしましたが普通にl,rの通りを全部確認して出すだけでよいです。その中で最小を出して最小の個数に(r-l+1)をかければよいです。
ただ、ちょっと工夫しないとなりません。毎回最小を出している時間はないので。
lを固定して、最小を出します。
そのあと、rをどんどん増やしていくときに増えたArのものと最小を比較して、最小を更新していけばよいです。
今回制約がN=10の4乗なので、o(Nの2乗)は通らないと勘違いしていたのが敗因です。普通に通るので10の8乗ぐらいなら何とかなると覚えておきます...。
D問題
N個の文字列があります。これらSiはANDかORです。
このとき、以下の配列があります。（xi, yiはTrueかFalseのみ）
・y0 = x0
・Si = ANDのときyi = y(i-1) & xi
・Si = ORのときyi = y(i-1) | xi
です。
yn が Trueである。通り数を求めなさい。
まず、全部で2のN乗あります。なので、全探索で調べると最大o(2の60乗)で到底枚に合いません（私はここを勘違いして間違えて実装してる）
なので普通にo(N)で解けないか考えます。
そうすると、
・i-1とiの状況は予想できる（AND,ORなので）
・それぞれはTrueかFalseしかない。なので、Trueの場合をf(i)とすると、
Falseは（2のN+1乗）- f(i)になる。
ということで、漸化式ができるのでdpで解けます。
そして、ANDのとき、i-1とiが両方Trueの場合だけ、Trueなので、
f(i) = f(i -1)
ORのとき、i - 1がTrueのとき、どちらでもよく、i - 1がFalseのとき、Trueのみなので、
f(i) = 2*f(i - 1) + (2のi乗) - f(i - 1) = f(i -1) + (2のi乗）
となります。
なのであとは実装するだけです。
取り掛かりにくいですが、よく考えるとわかる問題です。
最後に...
まあてんぱったのがダメ。あと普通に思想として忘れている。
これを機に思い出していこうと思います。
ではでは。
