東大卒のお金やりくり奮闘記~株、家計、趣味、経済~

東大卒でメーカー勤務の私がセミリタイアするために投資や競プロを頑張っていこうという趣旨で始めたブログです。既婚男性です。株、家計、趣味、経済の話をメインにゆるゆる話します。

競技プログラミング~ABC189~

おはようございます。しほみんです。

 

最近、やってなかった競技プログラミングについて振り返ります。今回は参加したくせにひどい成績でした。

 

ちゃんと振り返りたいと思います。

 

 

自分の競技プログラミングへのスタンスです。

<自分のプログラミング力>

・レートは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乗)

となります。

 

なのであとは実装するだけです。

取り掛かりにくいですが、よく考えるとわかる問題です。

 

最後に...

まあてんぱったのがダメ。あと普通に思想として忘れている。

これを機に思い出していこうと思います。

 

ではでは。