ABC169自分なりのまとめ

A- Multiplication 1

入力を受け取ってかけるだけです。

//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>
#include <limits>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
//エイリアス
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
  int a, b;
  cin >> a >> b;
  cout << a * b << endl;
}

B- Multiplication 2

コンテスト中に解けず。。。
簡単な問題でWA出すとパニックになってしまうのなんとかしたいです
解法としては、Aiの中に0が1つでもあったら0を出力
ない場合には、オーバーフローに注意しながら計算して答えを出力するだけです。
オーバーフローの検知はresultを解を格納する変数、limitを解の上限とすると

• result <= limit / Ai

でできます。(これが思いつかなかった。。。)

//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>
#include <limits>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
//エイリアス
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;
const ll limit = 1e18;

int main()
{
  int n;
  cin >> n;
  vl a(n, 0);
  rep(i, n) {
    cin >> a[i];
    if (a[i] == 0) {
      cout << 0 <<endl;
      return 0;
    }
  }
  ll result = 1;
  rep(i, n) {
    if (result <= limit / a[i]) {
      result *= a[i];
    } else {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << result << endl;
}

C- Multiplication 3

これも解けなかった。。
今回のコンテストはひどかったです。
浮動小数点の誤差がテーマの問題です。
知識としては知っていても、コンテスト中に活用するのはできませんでした。
この記事で詳しく解説されています。
誤差を回避する方法としては、文字列で受け取って小数点の前と後で分割するのが無難らしいです。

//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>
#include <limits>
#include <stdlib.h>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
//エイリアス
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
  ll a;
  string b;
  cin >> a >> b;
  int temp = b[0] - '0';
  int temp2 = stoi(b.substr(2, 2));
  cout << a * temp + (a * temp2) / 100 << endl;
}

D- Div Game

解けた。
体感、B,Cよりも簡単です。
任意の数は素数の積で表せます。
よって、素因数分解をして各素因数に対して同じ冪の肩を選ばないように何回操作を行えるかを数えていけば良いです。

//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>
#include <limits>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
//エイリアス
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

vl dc(ll n) {
  vl result;
  for(ll i = 2; i * i <= n; i++) {
    while( n % i == 0 ) {
      result.push_back(i);
      n = n / i;
    }
  }
  if(n > 1) {
    result.push_back(n);
  }
  return result;
}

ll calc(ll n) {
  ll start = 1;
  ll sum = 0;
  int count = 0;
  while(sum < n) {
    sum += start;
    if(sum > n) break;
    start++;
    count++;
  }
  return count;
}

int main()
{
  ll n;
  cin >> n;
  vl cand = dc(n);
  cand.push_back(0);
  int count = 1;
  int total = 0;
  for(int i = 0; i < cand.size() - 1; i++) {
    if(cand[i] == cand[i + 1]) {
      count++;
    }else{
      total += calc(count);
      count = 1;
    }
  }
  cout << total << endl;
}

E- Count Median

コンテスト後に考えてたけど解けませんでした。
解説呼んだ後のなるほど感がすごい。
最初にNが奇数の場合を考えます。 まず、各Xiで取りうる一番小さい数(Ai)を選んだとします。
この時の中央値をAmとします。 次に、反対にXiで取り得る一番大きい数(Bi)を選んだとします。 この時の中央値をBmとします。 実は、Am~Bmの範囲すべてを中央値とすることができます。 証明は以下のような感じでできるはずです。

• ベースケース
• Amが中央値となるようなケースで、Amを取る項に1加算できるならAm + 1が中央値となるようなケースを作ることができる
• もしAm + 1 > Bならば、Am + 1を取ることができる任意の項をAm + 1とすることでAm + 1を中央値とすることができる
• 数学的帰納法の仮定
• Am + 1 < x < Bmが中央値となるようなケースを作ることができる
• 帰納ステップ
• xが中央値ならばベースケースと同様にx + 1を中央値とするようなケースを作ることができる。

偶数の場合は、中央値をx(N / 2) + x((N / 2) + 1)とすると奇数の場合と同様に求めることができます。

//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>
#include <limits>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
//エイリアス
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

ll median(vl &target) {
  int size = target.size();
  if (size % 2 == 0) {
    size--;
    return target[size / 2] + target[(size / 2) + 1];
  } else {
    return target[size / 2];
  }
}

int main()
{
  int n;
  cin >> n;
  vl as(n, 0);
  vl bs(n, 0);
  rep(i, n) {
    ll a, b;
    cin >> a >> b;
    as[i] = a;
    bs[i] = b;
  }
  sort(as.begin(), as.end());
  sort(bs.begin(), bs.end());
  ll amedian = median(as);
  ll bmedian = median(bs) + 1;
  cout << bmedian - amedian << endl;
}