zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC126-C「Dice and Coin」です。
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
int N=0, K=0, score=0;
double a, ans = 0;
int main(){
cin >> N >> K;
// 係数の計算をしておく
a = 1.0 / N;
rep(n, N){
// 0.5が何回掛けられるかを保存しておく変数
double b = 1.0;
// 現在のスコアを保存する変数
// 最初にn+1の目が出たという状況
score = n+1;
// すぬけ君が勝つのはscoreがKを上回ったとき
// それまでwhileを回し続ける
// 各試行に対してコインが表を出し続ける確率を求めるためにbに0,5をかけていく（2で割っていく）
while (score < K){
score *= 2;
b /= 2;
}
// n+1の目が出たときの確率を足しあげていく
ans += a * b;
}
// 出力するときには誤差に注意
// サンプルでは小数点以下12桁まで出力していたのでそれに習う
printf("%.12f\n", ans);
}ポイント
今回おさえるべき内容
出力の誤差に気を付ける
確率を求めるという数学的な問題でした。出力の際に誤差に気をつけることや，forループの中にすぬけ君のスコアに基づくwhile文を組み込む必要がありました。数学的な問題は式をコードに落とし込むだけですが，例えば誤差発生の観点から小数のかけ算を避ける練習をすると良いでしょう。例えば，「0.5をかけていく」のではなく「2で割っていく」のような転換ができればgoodです。
コメント