ABC193反省会

レーティング255とかいうカスみたいな数値を叩き出したので反省会です。

1.A問題

定価の何％引きか出すだけ。定価$A$円の物が定価$B$円で売られているので、$(A-B)/A*100$で出せます。最後に100を掛けて百分率にすることを忘れないように。(1敗)

2.B問題

問題の意味を理解するのに2分ぐらいかかった。

まず店舗に到着するまでに在庫がどれだけ減るかというのを出す必要がある。$0.5,1.5,2.5,...$つまり$0.5+n(nは0以上の整数)$のときにすべての店舗で在庫が1減少するが、徒歩$A$分は整数値なので、1分経過ごとに在庫は1減少することがわかる。

つまり、到着までに在庫は$A$個減少する。

あとは最安値を出力するので、最安値を更新し続ければ終わり。

最初、tupleを使って値を取ろうとしていたけど、そんなことをしなくてもできることに気がついた。

tupleを使ってコードを書いてたときの残りカスのせいでコードをバグらせていた。

全体を書き直すならコードをまるごと消したほうが良さそう。

3.C問題

やらかした問題。最初素数問題だと思って考えていたけど、残り2分で$6^2$はカウントしないということに気がついて絶望した。

試しに50ぐらいまでは書き出すべきだった。

ずっと、素数の累乗数だけをカウントすれば答えが出ると思っていたので、$16=2^4$ぐらいではまだ問題文の解釈を間違ったことに気がついていなかった。

終わったあと、解説とtwitterを見て何をやるかは理解した。

1. $a^b(ただし、aとbは2以上の整数)$で表すことができるものをカウントする。←ここは思いついていた
2. 最大$\sqrt N$まで調べればよい。$b$の最小値は2であるため。←ここも思いついていた
3. $a$を全数探索すればよい。←これが思いつけなかった
4. 全探索すると衝突する数(例えば$64=2^6=8^2$)はhash_setで対処できる

そういうことで、コードは次の通り。ほぼ解説通りです。

hash_setなんてコンテナを完全に忘れていました。最近全く使ってなかったから・・・。いや、昔使ったのはhash_mapだったか。

どっちにしろ難しい方のB問題やC問題で使うことがあるのでもう一回覚えよう。

4.その他調べて知ったこと

4-1.素数判定など

スニペットに登録しよう。templateを使った一般的なものはネットに転がってないので自分で書く。

4-2.繰り返し2乗法

繰り返し二乗法

これもスニペットに登録しよう。特にlong long型は標準ライブラリのpow関数では計算できないので気をつけよう。

4-3.整数判定

ceil関数(天井関数)とfloor関数(床関数)を用いるとできるらしい。

今回は、平方根を取ったときにその値が整数かどうかをすべて出力するプログラムを書いた。

このように、平方根を床関数と天井関数に通して一致したら整数になっていると判別している。

ところで、珍しく三項演算子を使って書いたが、括弧が多すぎて見にくい。ここまで多いとif文のほうがいい気がする。これを書いてるときも括弧の対応を間違えてた。

4-4.long long型でのsqrt関数

long long型ではsqrt関数は使えません。どうするかというと、自分で実装します。参考;long long int

ただ、平方根を使う状況というのは基本的に素因数分解のときに$\sqrt N$まで探索するというシチュエーションが多い気がします。それならば、わざわざ平方根を使わずに、

for(long long i = 0; i * i <= n: i++)

とi*iの形で記述したほうがいいと思います。

4-5.型の最大値の定数

螺旋本をやっていたときに見慣れない物があったのでググったら出てきたやつです。long long型ならLLONG_MAXのように定まっています。これらはclimitsヘッダに含まれます。

最小値を更新し続けるプログラムでの初期値に用いれるかなという感じです。

4-6.大文字小文字判定

いつかのA問題かB問題で使ったもの。

アスキーコードならば、大文字が65~90、小文字が97~122になります。数字は48~57です。これらの数値を使って判定できます。ただ、よく忘れるので、isupper関数を使うほうが楽だと思います。これは大文字かどうかを判定してくれます。小文字の判定の場合はislower関数があります。

大文字から小文字の変換ならtolower関数など、localeヘッダには判定に便利な関数があります。

5.おわりに

レーティングが40燃えたので次は+50ぐらいできるように勉強します。