LoginSignup
solocomedian
@solocomedian (みやけん)

Are you sure you want to delete the question?

Leaving a resolved question undeleted may help others!

AtCoder Beginner Contest 340のC問題について

解決したいこと

AtCoder Beginner Contest 340のC問題について教えていただきたいです。C問題で以下のようなコードを書いたところ一部WAとなってしまいました。解説を見て自分のコードでは上手くいかない場合があるのは理解したのですが実際にどのような場合に正しく出力されないのか分からなかったので、具体的な入力数値などを用いて説明して頂けると幸いです。

発生している問題・エラー

スクリーンショット 2024-02-11 002515.png

該当するソースコード(C++)

# include<iostream>
# include<cmath>
# include <vector>

using namespace std;

int main(){
    unsigned long x;
    unsigned long total = 0;
    unsigned long count = 0;
    cin >> x;
    unsigned long num = x;
    while(num > (unsigned long)1){
        count += 1;
        unsigned long upper = num/2 + num % 2;
        unsigned long lower = num/2 ;
        if(upper == 2){
            if(lower == 2){
                total += x;
            } else {
                unsigned long k = pow(2,count);
                total += (x % k) * 2;
            }
        } else if (upper == 1){
            break;
        } else{
            total += x;
        }
        num = upper;
    }
    cout << total+x << endl;
}

自分で試したこと

  • 問題文中に出てくる入力例を実際にコードテストで実行してみた→3つとも出力例と同じ値が出た
  • 解説を読み直した。→ユーザー解答の方の対数を取る方針と自分のコードが近いように感じたがなぜ上手くいかないのかはわからなかった
0

1Answer

7を入力した場合、正しくは以下の経路で合計20となります。

[7]
↓+7
[3,4]
↓+7
[1,2,2,2]
↓+6
[1,1,1,1,1,1,1]

しかし、ご提示のコードですと、以下の経路をたどり、合計21となってしまいます。

num=7,upper=4,lower=3
↓+7
num=4,upper=2,lower=2
↓+7
num=2,upper=1,lower=1
break
↓+7

upper=2となった時点のlowerが1か2かという条件だけでは、最終的に足される数の判定には不十分ということです。

0Like

Comments

  1. @solocomedian

    Questioner

    ご回答ありがとうございます!具体例を出して下さったので手元で確認して理解できました!

Your answer might help someone💌