初心者の方へ

• プログラミングの学習を始めたばかりで何から手をつけるべきかわからない方は、まずは practice contest の問題A「Welcome to AtCoder」をお試しください。言語ごとに解答例が掲載されています。
  
• また、プログラミングコンテストの問題に慣れていない方は、 AtCoder Beginners Selection の問題をいくつか試すことをおすすめします。
  
• C++入門 AtCoder Programming Guide for beginners (APG4b) は、競技プログラミングのための C++ 入門用コンテンツです。
  
• Python入門 AtCoder Programming Guide for beginners (APG4bPython) は、競技プログラミングのための Python 入門用コンテンツです。
  

---

原案: admin

「 \(2\) の \(N\) 乗 」と「 \(2 \times N\) 」とを計算し、それらの差を求めることができればこの問題に正解できます。
掛け算と引き算は比較的簡単そうです。では、「 \(2\) の \(N\) 乗 」を求めるにはどうすればよいでしょうか？

---

解法 \(1\) : for ループで求める

\(2\) の \(N\) 乗は for ループを利用して求めることができます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n;
  cin >> n;
  int p=1;
  for(int i=0;i<n;i++){
    p=p*2;
  }
  cout << p-2*n << "\n";
  return 0;
}

---

解法 \(2\): 繰り返し二乗法を利用する

累乗を高速に計算するアルゴリズムである「繰り返し二乗法」を利用しても構いません。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n;
  cin >> n;
  int a=1,b=2,p=n;
  while(p>0){
    if(p%2==1){ a*=b; }
    b*=b;
    p/=2;
  }
  cout << a-2*n << "\n";
  return 0;
}

---

解法 \(3\) : 標準の関数を利用する

例えば Python では ** を用いることで累乗を計算することができます。

実装例 (Python):

n = int(input())
print(2**n-2*n)

C++ でも pow を活用することでこの問題には正解できますが、int 型を用いて pow(int,int) を呼ぶと返答は double となり、無警戒に使うと精度落ちや出力形式ミスなどが発生するので十分注意してください。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n;
  cin >> n;
  cout << pow(2,n)-2*n << "\n";
  return 0;
}

---

解法 \(4\) : ビットシフト演算を利用する

ビットシフト演算を利用することで、 a<<k と書くと (オーバーフローが起きない範囲で) \(a \times 2^k\) の値を得ることができます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n;
  cin >> n;
  cout << (1<<n)-2*n << "\n";
  return 0;
}