盆栽エンジニアリング日記

勉強したことをまとめるブログ

ABC166自分なりのまとめ

A-A?C

ABCならARC、ARCならABCと出力すれば良いです。

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

#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>;

int main()
{
  string s;
  cin >> s;
  if(s == "ABC") {
    cout << "ARC" << endl;
  }else{
    cout << "ABC" << endl;
  }
}

B-Trick or Treat

mapで受け取ったお菓子の枚数を記録して、0の人数を出力すれば良いです。

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

#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>;

int main()
{
  int n, k;
  cin >> n >> k;
  v memo(n, 0);
  rep(i, k) {
    int d;
    cin >> d;
    rep(j, d) {
      int a;
      cin >> a;
      memo[a - 1] = 1;
    }
  }
  int cnt = 0;
  rep(i, n) {
    if(memo[i] == 0) {
      cnt++;
    }
  }
  cout << cnt << endl;
}

C-Peaks

最初は連結している展望台の中で一番高いやつかと思いました。。。
距離1で行ける展望台の中で高い方を記録して行けばいいです。
高さが同じ場合に注意

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

#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>;

int main()
{
  int n, m;
  cin >> n >> m;
  vl h(n, 0);
  rep(i, n) {
    cin >> h[i];
  }
  vector<vector<int>> graph(n, vector<int>());
  rep(i, m) {
    int a, b;
    cin >> a >> b;
    graph[a - 1].push_back(b - 1);
    graph[b - 1].push_back(a - 1);
  }
  int result = 0;
  auto calc = [&](int start) {
    ll ma = h[start];
    map<int, int> memo;
    memo[ma]++;
    for(int i = 0; i < graph[start].size(); i++)
    {
      int ne = graph[start][i];
      if(ma <= h[ne]) {
        ma = h[ne];
        memo[ma]++;
      }
    }
    if(ma == h[start] && memo[ma] == 1) result++;
  };
  rep(i, n) {
    calc(i);
  }
  cout << result << endl;
}

D-I hate Factorization

そんなに広い範囲を調べなくても、解が見つかるだろうとエスパーしました。
A5 - B5をxを引数に取る関数f(x) = x5 - (x - 1)5と考えます。
この関数は明らかにx=0.5が最小値となる凹関数です。
f(x)はx=120, -119で109を超えます。
よってA,Bともにこの範囲で全探索をすれば良いです。
コードはエスパーの結果なので、1000になっています。

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

#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>;

ll calc(ll x) {
  return x * x * x * x * x;
}

int main()
{
  ll x;
  cin >> x;
  for(ll i = 0; i <= 1000; i++) {
    ll a5 = calc(i);
    ll b5 = a5 - x;
    if(b5 < 0) {
      for(ll j = 0; j <= 1000; j++){
        if(b5 == calc(-j)) {
          cout << i << " " << -j << endl;
          return 0;
        }
      }
    }else{
      for(ll j = 0; j <= 1000; j++){
        if(b5 == calc(j)) {
          cout << i << " " << j << endl;
          return 0;
        }
      }
    }
  }
}

E-This Message Will Self-Destruct in 5s

久しぶりにE問題が自力で解けました。
参加者が1~Nの順番で並んでいるとします。
このとき、順番iまでの参加者で条件を満たしている組み合わせ数がx個あるとします。
そうすると、順番i + iの参加者を新たに加えるとi + 1番目までの参加者で条件を満たしている組み合わせ数は
x + (i + 1番目を加えて時に新たに発生する組み合わせ数)となります。
よって、もしこの新たに発生する組み合わせ数を簡単に求めることができるならば、簡単な動的計画法を用いて
解を計算することが出来ます。
ここからは、新たに参加者を加えたときに条件を満たす組み合わせ数を計算する方法について考えます。
条件は、参加者i,jの場合、Ai + Aj = |i - j|でした。
今、1から順番に参加者を追加していっているため、上の式は以下のように変形できます。

  • Ai + Aj = j - i (j > i)

これを更に変形すると

  • Ai + i = j - Aj

となります。
よって、各i(i < j)について、自身の番号と身長の和をmapに保存していくことで
簡単に新たに発生する組み合わせ数を計算することができます。

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

#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>;

int n;
ll a[2 * 100000];
ll dp[2 * 100000 + 1];

int main()
{
  cin >> n;
  rep(i, n) {
    cin >> a[i];
  }
  map<ll, ll> m;
  for(ll i = 1; i <= n; i++) {
    ll want = i - a[i - 1];
    m[i + a[i - 1]]++;
    dp[i] = m.count(want) == 0 ? dp[i - 1] : dp[i - 1] + m[want];
  }
  cout << dp[n] << endl;
}