おはようございます。しほみんです。
2週間前にあったABC169を復習します。荒れるに荒れた感じがしますが、結果オーライだった気がします。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは800程度になりました。緑と茶をうろちょろしています。
・C#でクラスとかつかってアプリケーションは作れます。
＜Atcoderでのスタンス＞
・アルゴリズムについて問題でいろいろ学んでいる。第3回PAST70点で中級取得。
・基本的に本番でやっている。現在48回参加、ほぼ1年。
・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスは1000以上、できれば水色（1200以上）は欲しい。
今回はABDE、75分でした。C問題解きたかったですね....正直こういう桁捨ては難しいですね....。Eは気が付けば解ける問題だったんですが差が大きいですね。これが解けたおかげでパフォーマンスは1321で初の水色です。レートも 883→935で上がりました。
Cはとりあえずもっと精度のよい型を使えばよいのが分かっただけでも大きいです。
今回はF問題まで全部解けたので振り返ります。
長くなるので前半はC問題まで書きます。前回に引き続き考察をメインに書きます。
コードは別に上げます。
以下問題です。
A問題
A*Bを求めてください。
普通にA*Bを出力しましょう（それ以外いうことがない...）
B問題
数列Aが与えられます。
A1×A2×A3×...×Anを求めなさい。
ただし、10の18乗よりおおきければ、-1を出力しなさい。
まあ10の18乗以下であればA1からかけていけばよいわけですが....問題は10の18乗より大きいときです。long型でも10の19乗まで行くとオーバーフローしてしまうので、単純にかけたときの判定ではできません。
なので、あらかじめ答えが10の18乗を超えるかどうかをまずは判定してそのあと計算しないとなりません。
その判定方法ですが、10の18乗を用意してA1から割っていく。この時、割っていって0になるならそれより大きい数なので-1を出します。
このとき、あまりは切り捨てて問題ありません。
もし、全てかけたとき10の18乗を超えないとすると、割ったときどんな割り方をしても必ず、商は1以上になると保証されます。
なぜなら、10の18乗を超えるときは、どこかの割るタイミングで、商が1小さくなるので、割っていくと、必ず分母が分子より大きくなって0になるからです。
ただ、この時0で割ると破綻します。ただ、0がある時点で答えは0なので0で出せば問題ないです。
（こんなふうに考えていった）
つまりまとめると、
1.ソートしてみる
2.初項が0なら0を出す。
3.それ以外なら10の18乗を全Aiで割って、0になるなら、-1を出力。
4.最後に普通にかけて出力する。
が妥当な案です。
C問題
a*bを求めなさい。ただし整数で出力してください。
aは整数、bは小数第二位までの10までの数。
問題は単純ですが、桁落ち問題で簡単には解けません。
方法は2つあるかと思います。
1. decimal型で処理。
どんな処理かわかりませんが桁が27-28桁まで保証されます。それならこの計算しても答えが出せます。
2. bを整数型で取り出して、a*bをして100で割って答を出す。
bは小数なので、誤差が生まれていることに注意が必要です。
理由は単純で、小数型を2ビット表記すると
1/2, 1/4, 1/8, 1/16,....というように表記されます。（整数型が2のn乗なら、小数型は1/2のn乗でビット表記されます）
つまり、0.01という数は厳密に表せず、丸め込まれてしまいます（1/64と1/128の間の数を厳密に出せない）。だから100倍して計算しても誤差はあるわけです。
なので、bをうまく、整数として読み込んで考えましょう。
たとえば、bを文字列にして、文字列の長さに応じてそれぞれ抽出すればよいです。
まあそんな工夫をして計算すればおっけーです。
C問題結局ACできませんでしたが、小数型はそもそも精度が出せないことを本格的に理解した気がします。あとは、文字列を使ってうまく出せたらいいなあって感じです。
最後に.....
C問題単純ですがよい問題な気がします。今回B問題も結構考察しないと解けなかったのでセットとしては重めだったような気がします。
ではでは。
