ABC174に参加してみた
初めに
ABC174はAB完でした。Cが緑パフォの問題でDが茶パフォの問題だったんですが、 Cに置かれたら頑張って解こうとしちゃうんですよね(笑) ということでC問題について書いていきます！
https://atcoder.jp/contests/abc174
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
C - Repsept
この問題は7,77,777,…と続く数列の中に初めて入力Kの倍数が登場するのは 何項目かを求める問題で、倍数が存在しない場合は-1を出力します。
解説を見てからの回答
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL<<60;
typedef pair<ll,ll> Pair;
int main(){
ll K;
cin >> K;
ll x=7%K;
set<ll> s;
ll ans = 1;
// 同じ値が格納されていない間はループする
while(s.count(x) == 0){
// mod計算の結果が0の場合は第何項かを出力し終了
if(x == 0){
cout << ans << endl;
return 0;
}
// xの値を格納
s.insert(x);
// 掛け算・足し算の途中でmod Kの計算
x = (x*10+7)%K;
++ans;
}
// Kの倍数となる数列が無い場合は-1を出力
cout << "-1" << endl;
return 0;
}
まずは、数列がどのような規則で変化しているか確認してみると、
下記イメージのように増加している事がわかります。
どうような規則で変化していくかはわかりましたが、上記のように数列が増えていくと
値が膨大になりオーバーフローしてしまいます。そこでmod Kを利用して考えて見ます。
足し算や掛け算の途中でmodの計算を行っても計算結果は下記の通り同じになるため
数列の値が増える度にmod Kの計算を行う事でオーバーフローせずに計算を行う事が出来ます。
計算途中でmod Kの計算を行う事で、オーバーフローせずに計算を行えるようになりましたが、
数列にKの倍数が存在する・しないの判定をするためにはどのような条件で
処理を進める必要があるでしょうか。
下記のようにmod Kの計算で一度出現した値が出るとその後の値も同じ値の繰り返しとなります。
そのため、同じ値が出現するまでループを回しその間にmod Kの計算結果が
0になるか・ならないかでKの倍数であるかどうかを判定することが出来ます。
(mod Kで計算すれば行けそうなのは分かったんですが、判定部分がわかりませんでした、、、)
上記の条件で計算を進めて行くことで答えを求める事が可能です。
最後に
いやー、ほんとにC問題で緑パフォが出ると無理ですね(笑)
なんとなくアプローチが分かる問題もあるんですけど、問題を解くには至らないんですよね、、、
まぁでも少しずつではあるけど、この問題ではあれが使えそうとか引き出しは
少しずつ増えてきた実感はあるので引き続き頑張りまっしょい
エイシング プログラミングコンテスト 2020に参加してみた
初めに
レーティングがABC相当のようだったので企業コンに参加しました。
結果はABC完でしたので、ぼちぼちって感じですね。
今回はD問題について書きますが、解き方うんぬんって話では無く
解説を聞いていて今まで書いた事が無いようなテクニックがあったので
そこにフォーカスして次に似たような問題が出た際に活用できるように
メモとして書いて行きます。
https://atcoder.jp/contests/aising2020/
D - Anything Goes to Zero
この問題はf(n)を「n を popcount(n) で割ったあまりに置き換える」という操作を繰り返した際に
nが0になるまでの操作回数として、与えられたN桁の2進数Xの1桁目のビットを反転した値をX1、
2桁目のビットを反転した値をX2、・・・n桁目のビットを反転した値をXnとして、
それぞれの桁数を反転させた場合の数値でのf(n)を求める問題です。
(X=101の場合は、X1=001,X2=111,X3=100になります。)
計算例) n = 7 の場合はf(7) = 2となります。(2回の操作でnが0となるため)
popcount(7)=3 なので、7を3で割ったあまりである 1に置き換えます。
popcount(1)=1 なので、1を1で割ったあまりである 0に置き換えます。
解説で記載されていたコードにコメントを追記したもの
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
int pcnt(int x) {
//⑤popcountの計算を行うビルトイン関数
return __builtin_popcount(x);
}
int f(int x) {
//xの値が0の場合は0を返す
if (x == 0) return 0;
//操作回数を計算
return f(x%pcnt(x))+1;
}
int main() {
int n;
cin >> n;
string s;
cin >> s;
vector<int> x(n);
// ①配列xに数値として1と0を格納する。'1'-'0'= 1,'0'-'0' = 0
rep(i,n) x[i] = s[i]-'0';
// popcountを計算する。配列xに1or0が入っているので順番に足すだけで良い。
int pc = 0;
rep(i,n) pc += x[i];
//答えの格納用の配列ans
vector<int> ans(n);
//popcountが入力が反転して1増えるた場合と1減った場合を試す
rep(b,2) {
//popcountをnpcに格納する。
int npc = pc;
// 入力が反転してpopcountが1増えるパターン
if (b == 0) npc++;
// 入力が反転してpopcountが1減ったパターン
else npc--;
// npcが0以下になったらスキップ
if (npc <= 0) continue;
// 元の割った余りを求めていくための変数
int r0 = 0;
//元の数をnpc(pc+1 or pc-1)で割った数をr0としている。(掛け算・足し算・引き算の最中なら余りを求めても結果は変わらない)
//npc(pc+1 or pc-1)の2パターンでこれを行う。入力が011とかの場合は、101(5)や111(7)が考えられる
rep(i,n) {
// ②2進数Xの先頭桁から、桁が変わる毎に2を掛けていきXの値を計算し、その値をnpcで割っている
r0 = (r0*2)%npc;
r0 += x[i];
}
cout << "r0 = " << r0 << endl;
int k = 1;
for (int i = n-1; i >= 0; --i) {
//bが0のパターンと1のパターンで処理を分ける
if (x[i] == b) {
//元の数をnpc(pc+1 or pc-1)で割った数をr0としている。
//入力が011とかの場合は、101(5)や111(7)が考えられる
int r = r0;
//0が1に反転したと考えて、i桁目の値kを足す
if (b == 0) r = (r+k)%npc;
//③1が0に反転したと考えて、i桁目の値kを引く
else r = (r-k+npc)%npc;
ans[i] = f(r)+1;
}
//④i桁の目値をkに代入する。
k = (k*2)%npc;
}
}
rep(i,n) cout << ans[i] << endl;
return 0;
}
まずは①についてですね。(数字はソースコード内のコメントに記載されています。)
// ①配列xに数値として1と0を格納する。'1'-'0'= 1,'0'-'0' = 0 rep(i,n) x[i] = s[i]-'0';
入力された2進数文字列をint型配列に格納している処理ですが、
文字列sに格納されている各配列の値より文字列'0'を引いて数値を格納しています。
入力される文字列は'0'か'1'のみです。文字コード上の'0'と'1'は値が1しか差が無いので
文字列'0'を引くことで0 or 1をint型配列に格納することが出来ます。
解説聞くとなるほどと思いますけどやっている時には浮かばないんですよね。
お次は②についてです。
// 元の割った余りを求めていくための変数
int r0 = 0;
rep(i,n) {
// ②2進数Xの先頭桁から、桁が変わる毎に2を掛けていきXの値を計算し、その値をnpcで割っている
r0 = (r0*2)%npc;
r0 += x[i];
}
2進数の先頭ビットの値から変数に格納していき、次の桁数に移る際に現在の値に2を掛け、
移ったビットの値を足していく操作を繰り返していくと2進数の文字列の値を求める事が可能です。
※下記イメージのような感じ
これは、2進数に限らず10進数等でも同じように文字列から数字に変換することが可能です。
最初は解説を聞いた時にはピンと来なかったんですが、実際に書いてみたり10進数の場合で考えて
見たら理解出来ました。
③と④は関連しているのでまとめて書きます。
//③1が0に反転したと考えて、i桁目の値kを引く
else r = (r-k+npc)%npc;
//④i桁の目値をkに代入する。
k = (k*2)%npc;
④については、ループが回る毎にkに2を掛け1(20),2(21),4(22),8(23),16(24)・・・という形で
2進数の各桁の値をkで表す事が可能です。
③については、条件分岐によりrからkを引く際にマイナスになる可能性があるので、npcを足しています。
kについてもnpcで毎回割っているため、npcで余りを求めても問題ありません。
これは、掛け算・足し算・引き算の最中なら余りを求めても
結果は変わらないということがポイントですね。
※詳細については下記の記事を見てもらえると理解が深まると思います。
「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita
最後は⑤についてです。
int pcnt(int x) {
//⑤popcountの計算を行うビルトイン関数
return __builtin_popcount(x);
}
まぁこれはgccのビルトイン関数でint型の数値のポップカウントを求める方法が
ある事が解説を見て分かったので、忘れないようにメモしておこうって感じですね。
最後に
今回はABC完出来たので個人的には良かったのですが、まだD問題には全然歯が立たないですね。
解説聞けば解けそうと思うような問題もあるんですが、まだまだですねぇ。
まぁとりあえずはABC完をキープしてまずは茶色になりましょ！
ABC173に参加してみた
初めに
ABC173もまたまたAB完でした。大分ぐんにょりな感じですですね。
C問題は全探索のしかたが分からなくて摘んでしました。
なので、またまたC問題について書いていきます。(最近D問題について書いてない気がする、、、)
https://atcoder.jp/contests/abc173
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
C - H and V
以下のような入力があった場合にちょうど指定された数の黒いマスが残るような塗つぶし方が
いくつあるかを求める問題です。(「.」は白いマス、「#」は黒いマスを表しています。)
塗りつぶし方としては、選択した行または列に含まれるマスをすべて塗りつぶすことができます。
..# ###
解説を見てからの回答
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ll H,W,K;
ll ans = 0;
cin >> H >> W >> K;
vector<string> c(H);
for(ll i = 0;i < H;++i) cin >> c[i];
// 列のパターンを2進数で列挙する
// ex. H = 3の場合は1<<3で1000(8)となり000～111(8パターン)まで列挙可能
for(ll h = 0;h < (1<<H);++h) {
// 行のパターンを2進数で列挙する
// ex. W = 4の場合は1<<4で10000(16)となり0000～1111(15パターン)まで列挙可能
for(ll w = 0;w < (1<<W);++w) {
//黒マスの集計用変数
ll count = 0;
//すべてのマスを全探索
for(ll i = 0;i < H;++i){
for(ll j = 0;j < W;++j){
//既に列が塗りつぶされている場合は処理を以降の処理をスキップ
if(h>>i & 1) continue;
//既に行が塗りつぶされている場合は処理を以降の処理をスキップ
if(w>>j & 1) continue;
//塗りつぶされていない黒マスの数をカウント
if(c[i][j] == '#') ++count;
}
}
//黒マスのカウントがKと同様であればansのカウントを増やす
if(count == K) ++ans;
}
}
cout << ans << endl;
return 0;
}
まず、列と行の塗りつぶしパターンの全列挙ですが、bit全探索を利用します。
1の場合は行または列を塗りつぶす、0の場合は行または列を塗りつぶさない
と考えると全パターンの列挙を下記イメージのように行う事ができます。
塗りつぶしのパターンの列挙後に黒マスかどうかを各マス毎に確認していきます。
塗りつぶされた行または列の場合は処理をスキップし、
塗りつぶされていない黒マスだったら数をカウントします。
黒マスの数がKと同様だった場合は、ansのカウントを増やして行くことで、
条件を満たした塗りつぶしパターンがあるかを求めることが出来ます。
最後に
うーん、bit全探索を行えば出来る気はしたんですけどfor文を3重以上で書くことになりそうだなぁ
と思った時点で拒絶反応が出て別な方法が無いかという考えにシフトしちゃったんですよね。。。
(H,Wの入力が最高でも6なので、全然間に合いますが、、、)
前にもbit全探索の問題は解いていたので、解きたかったですね。。。頑張ります。。。
ABC172に参加してみた
初めに
ABC172もAB完でした。今回はそもそも参加が遅れてしまい
そのせいもありレートが結構下がったのでかなりテンションが下がりました。。。
くよくよせず今回もC問題について書いて行きます！
https://atcoder.jp/contests/abc172
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
C - Tsundoku
この問題は、机A,B上に積まれている本を決められた時間内に最大で何冊読めるか求める問題です。
それぞれの本を読むために掛かる時間は設定されており、本は上から順番に読むことが出来ます。
上にある本を読む時間が小さいものから順々に読んで行けばええんやない？と考えて
その方針で解こうと思い実装しサンプル通ったんでイケそう！と思いましたが、
WA出しまくって解けませんでした。。。
解説を見たところ今回の問題の解き方は2パターンあるそうなので両方実装しました。
解説を見てからの回答①
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ll N,M,K;
ll ans = -1;
cin >> N >> M >> K;
vector<ll> A(N);
vector<ll> B(M);
for(ll i = 0;i < N;++i) cin >> A[i];
for(ll j = 0;j < M;++j) cin >> B[j];
// 累積和を格納するための配列
vector<ll> sumA(N+1,0);
vector<ll> sumB(M+1,0);
// 累積和を計算し配列に格納
for(ll i = 0;i < N;++i) sumA[i+1] = sumA[i] + A[i];
for(ll i = 0;i < M;++i) sumB[i+1] = sumB[i] + B[i];
for(ll i = 0;i <= N;++i){
// 机Aからi冊読んだ時に残っている時間
ll t = K - sumA[i];
// 机Bから本を読み時間が無くなったらループを抜ける
if(t < 0) break;
// 2分探索用の変数(机Bに積んである本で2分探索)
ll left = 0;
ll right = M+1;
ll mid = 0;
while(right - left > 1){
// left と rightの中間地の計算
mid = (left + right)/2;
// 中間地よりも大きかった場合は、leftに中間地の値を格納
if(sumB[mid] <= t) left = mid;
// 中間地よりも小さかった場合は、rightに中間地の値を格納
else right = mid;
}
// 机Aから選択したi冊と机Bから選択したleft冊の本の合計
ll res = i + left;
// 読み事が可能な冊数を最大値で更新
ans = max(ans,res);
}
cout << ans << endl;
return 0;
}
1つ目は、累積和+2分探索を利用した解法です。
本を読むのに掛かる時間を愚直に2重ループで全探索を行おうとすると
N,Mがそれぞれ最大で2×105のためTLEになってしまいます。
そこで本を読みのに掛かる時間の計算時間を削減するために累積和を用いています。
下記のイメージのようにあらかじめ累積和を計算しておけば、
ループの中でいちいち計算しなくても<直ぐに本を読んだ時間を求める事ができます。
※累積和についてはこちらを見るとお勉強になります。
求めた累積和を利用して机Aから0冊読んだ場合に机Bから何冊読めるか、
1冊読んだ場合に机Bから何冊読めるか・・・と順々に計算し、
最大で読める冊数を更新していきますが、机Bから何冊読めるかは、
累積和を求めた配列を2分探索することにより高速に求める事が可能です。
机Bの本をすべて読む際にに掛かる読書時間の累積和は既に計算しており、
配列の値はインデックスが増えるごとに単調増加することは自明なため、
2分探索を行う事が可能です。
プログラム上では探索範囲の先頭(左端)をleft,末尾(右端)をright,中間をmid、
机AからN冊読んで残った時間をtとしており、midの値がtより大きい場合はleft = midで更新、
小さい場合はright = midと更新していき探索範囲を狭めていき、
right - left > 0を満たさなくなった時のleftの値が机Bから読む事ができる本の冊数となります。
そして、机A・Bで読むことが可能な冊数を最大値で更新していく
ことでK以内で読める最大の冊数が求められます。
解説を見てからの回答②
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL<<60;
typedef pair<ll,ll> Pair;
int main(){
ll N,M,K;
ll ans = 0;
cin >> N >> M >> K;
vector<ll> A(N);
vector<ll> B(M);
for(ll i = 0;i < N;++i) cin >> A[i];
for(ll j = 0;j < M;++j) cin >> B[j];
ll left = 0;
ll sum = 0;
for(ll i = 0;i < M;++i) sum += B[i];
for(ll right = M;right >= 0;--right){
//机Aの本を読み切るかsumがKを超えるまで机Aの本を読む。
while((sum + A[left]) <= K && left < N){
sum += A[left];
++left;
}
// Bの本が0冊の場合はsumから本を読む時間を引き事は出来ない
if(sum <= K && sum != 0) ans = max(ans,left + right);
// 机Bの本を1冊も読まない場合はsumから本を読む時間を引かない
if(right != 0) sum -= B[right - 1];
}
cout << ans << endl;
return 0;
}
2つ目は、尺取り法を利用した解法です。
尺取り法は長さのNの数列から条件を満たす区間の最大や最小を求める際に使用できる手法で、
区間の先頭(左端)をleft、末尾(右端)をrightとおきleftとrightを条件に従い移動させることで値を求めていきます。
この問題ではsumにあらかじめ机Bの本をすべて読んだ際の累積和を代入し、
机Bの本の冊数をright、机Aの本の冊数をleftとおきました
そして、机Bの本を読んだ際に掛かる読書時間を1冊分ずつsumから引いていき、
机AからK-sumの時間で読むことが可能な本の読書時間を1冊分ずつsumに足していく操作を
机Bのすべての本の読書時間を引くまで行います。
（机Bの本の読書時間を引く際にrightも引き、机Aの本の読書時間を足す際にleftも足します。)
その間に机A・Bで読むことが可能な冊数を最大値で
更新していくことでK以内で読める最大の冊数が求められます。
(下記イメージ)
尺取り法はこの問題で初めて触れましたが1つ目の解法より尺取り法の方が個人的には好きです。
※しゃくとり法についてはこちらを見るとお勉強になります！
しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ - Qiita
最後に
知らない手法が出ると詰んでしまいますが、ブログでまとめて次回以降に
類似問題が出てたら対応できるようにしたいですね。
あと、毎回書いていて思いますが日本語って難しいですね(笑)
ABC171に参加してみた
初めに
ABC171はAB完でした。うーん中々安定してABC完出来ないですね
今回のC問題は考察不足感が否めないかった。。。どうしたら考察力が付くんだろうか。。。
とゆうことで今回はC問題について書いて行きます。
https://atcoder.jp/contests/abc171
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
C - One Quadrillion and One Dalmatians
この問題は、1～26がそれぞれa～zに対応しており、入力で与えられた数値を
アルファベットの文字列に変換する問題です。
解説を見てからの回答
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL<<60;
vector<ll> load[100005];
typedef pair<ll,ll> Pair;
int main(){
ll i = 0,j = 0;
char answer[16];
ll N;
cin >> N;
// N--;
while(N > 0) {
//各桁の0-INDEX化
N--;
// 入力した数値を26で割り、その余りと商をだす
j = N % 26;
N = N / 26;
answer[i] = 'a' + j;
i++;
}
i--;
for(j=i; j>=0; j--) {
cout << answer[j];
}
cout << endl;
return 0;
}
まず、1～26まででがa～zに対応していて27からはaa,ab,ac・・・となるので26を超えると
桁上がりしていることが分かったので、26進数で考えれば問題が解けそうです。
問題では1～26がa～zに対応していますが、26進数で考えやすいように0-INDEXで考え
0～25をa～zにそれぞれ対応させるため、入力されたNから1を引きます。
最初は入力されたNを一度だけ引けば良いと思っていましたが、
27を入力したところ何故か"ba"と表示されてしまいました。。。(あれ？)
解説見てもピンと来なかったので、絵を書いた見たところ2桁目も0-INDEXに直す必要があるのに
プログラム上では1桁目しか0-indexを行っていないことに気が付きました。。。(下図青枠)
※とゆーかそもそも桁が上がる際はN/26 > 0であり、桁上がりした値は最低でも1から始まるので
そりゃずれますよね。(0-INDEXをしない限り0から始まることは無いので)
なので、1桁目以降の桁も0-INDEXに直すために桁上がりする場合もNから1を引いた状態で
計算を行い、最後は配列に格納した文字列を逆順で出力する事で答えを求められます。
最後に
うーん、今回は考察不足感が否めないですね。ブログ書くときに絵を描いていると
色々見えてきてくるんですけどね。競技中は頭の中だけで考えてやっているんですが
もっと解けるようになるまでは絵を描きがながらやろうと思います。。。ぐんにょり
ABC170に参加してみた
初めに
ABC170はABC完でした。D問題も解けそうな感じではあったんですが、
実装が間に合わず解けませんでした。CでWAを出してしまった影響か
レーティングも+2しかあがらずぐんにょりって感じでした。
今回はD問題について書いて行きます！
https://atcoder.jp/contests/abc170
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
D - Not Divisible
この問題は与えられたN個の数字のうち、ある数字を選択し、
選択した数字を残りの数字でそれぞれ割り算を行い、
選択した数字以外では割り切れないような数字の個数を集計します。
解説を見てからの回答
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL<<60;
typedef pair<ll,ll> Pair;
int main(){
ll N;
//Aの取りうる最大値(10^6)分の配列を確保します。
vector<ll> H(1e6,0);
cin >> N;
vector<ll> A(N);
for(ll i = 0;i < N;++i) cin >> A[i];
for(ll i : A){
// すでにふるい落ちている(1以上)場合はカウントをして、ふるいにかける処理をスキップします。
if(H[i] >= 1){
H[i]++;
continue;
}
//ふるい落とされた各整数の倍数をカウント
for(ll j = i;j <= H.size();j+=i) H[j]++;
}
ll ans = 0;
for(ll i = 0;i <A.size();++i) if(H[A[i]] == 1) ans++;
cout << ans << endl;
return 0;
}
この問題は素数判定で利用されるエラトステネスの篩と同じ処理を行うことで、
回答を導くことが出来ます。
エラトステネスのふるいとその計算量 | 高校数学の美しい物語
今回は与えられたN個の整数でふるいを掛けていき、
配列Hにふるいに落ちた各整数の倍数をカウントしていきます。
(下記イメージ参照)
最後に配列Hを確認し、与えられた整数のカウントが1のものを数える事で、
答えを求めることが出来ます。(1以外の場合は他の整数で割り切れてしまっているため)
最後に
んー基本的にはABC完をキープすれば茶色になれるってtwitterで優しい人が教えてくれたけど、
中々道のりは長いですね。なるべくABCでWAしないように慎重に回答してコツコツ上げていきます。
ABC169に参加してみた
初めに
ABC169に参加しました。いや～過去最高にWA出しましたね(笑)
やっていて辛くなりました、、、B、Cでやられました、、、
Bはオーバーフローさせないようにすれば良いことは分かったんですが、実装が出来ませんでした。
Cも誤差の影響でWAしてるってことはわかったんですが、実装が出来ませんでした。
B問題についてはケアレスミスで実装に失敗していただけだったので、
今回はC問題についてのみ書いて行こうと思います。(浮動小数点数のおさらいもしたいので)
https://atcoder.jp/contests/abc169
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
C - Multiplication 3
浮動小数点数とはなんぞや
まず問題の話に入る前に、この問題のきもとなる浮動小数点数とはなんぞやって話ですが
端的に言うと小数点を固定せずに表現された数です。(対義後は固定小数点数)
浮動小数点数は小数点が固定出ないため表現が無数に存在します。
表現の形式が統一されていないと計算等に不便なため、
コンピューターで使う浮動小数点数の表現形式は一般的に
IEEE754標準で決められた形式が使用されます。
表記例は以下のようになり、それぞれの箇所に名称がついています。
double型の場合は以下のような式であらわされ、内部構造は下記イメージのようになっています。
仮数部については、「1.・・・」というように表現するよう決められているため、
先頭の1以降の数字が変数に格納されます。
(-1)符号部 × 2指数部-1023×(1.仮数部)
式の(指数部-1023)の箇所で記載されている「1023」はバイアス値と呼ばれており、
バイアス値のおかげで指数がマイナスの場合も符号や2の補数表現を使わずに指数を表せます。
例）1.1 × 2-2 の場合
(-1)符号部 × 2指数部-1023×(1.仮数部) = (-1)0 × 21021-1023×(1.1)
= (-1)0 × 2-2×(1.1)
= 1.1 × 2-2
※詳しくは下記のサイトの説明や表がわかりやすかったので参照してみて下さい。
ここで、浮動小数点数を使う点で注意が必要なのが誤差です。
例えば10進数の0.1を2進数で表現すると以下のように循環小数であらわされる場合があります。
(同じ数字だけが繰り返し現れる小数を循環小数といいます)
0.1(10進数) = 0.000110011001100…(2進数)
コンピュータ内部では有限桁しか扱えないため、どこかで打ち切る必要があり、
それにより真の値との誤差が生じてしまいます。(他の誤差については下記サイトを参照してみて下さい)
※因みに10進数の1.5や1.75のように正確に表現出来る数もあります。
1.5 → 21+2-1 1.75 → 21 + 2 ^(-1) + 2-2
https://it-lab.com/column/floating-point-number/
解説を見てからの回答
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL<<60;
int main(){
double B;
ll LB,A,ans;
cin >> A >> B;
LB = ll(B*100 + 0.1);
//LB = lround(B*100 + 0.1);
ans = A*LB;
ans /= 100;
cout << ans << endl;
return 0;
}
それでは、ようやく問題の話になりますがこの問題は
整数Aと小数2桁まで与えられるBの掛け算の結果を出力する問題です。
AとBの入力の条件についてですが、以下のようになっています。
Aは整数
Bは小数点第2位まで与えられる
最初は、double型でAとBを計算してA×Bの計算をしたのですが、
double型で扱えるのは10進数で約15桁なので、精度(有効数字)が足りないため正確な計算が行えません。
そこで、「Bに100をかけ整数同士の掛け算を行えば誤差を考えずに計算が行えるはず！」
となるかもしれませんが、この計算でも誤差が発生する可能性があります。
前述で記載したように小数部分を2進数の有限桁数で表現出来無いようなケースの場合、
掛け算した結果が本来の値より大きい場合や小さくなる場合があります。(以下は例です。)
小さくなった場合は、C++の整数型に代入した場合は小数点以下が切り捨てられてしまうため、
間違った計算が行われてしまいます。
そこで、プログラムではB*100.0の計算結果は正しい値に近いはずなので、
本来の値より値が小さかった場合を考え、0.5を足してから
整数型にキャストを行いA×Bの計算を行っています。
こうすることで、整数型での計算に落とし込めるため、正しい答えを出力することが可能です。
他の解法については、浮動小数点数オタクさんの記事でわかりやすく記載されているので、
そちらを参照してみて下さい！
浮動小数点数オタクが AtCoder Beginner Contest 169 のC問題をガチで解説してみる - Qiita
最後に
今まではあまり誤差を意識せずにdouble型を使用していましたが、今回のブログを書くにあたり
色々調べるうちに「浮動小数点数こわい( ;∀;)」ってなりました。(笑)
と、同時にブログを書くと色々と調べて理解する必要が出てくるので、
お勉強には丁度良いかなぁと改めて思いました。(後で見返せますしね)
